Re: Tablica int i usuwanie duplikatów

From	bartekltg <bartekltg@gmail.com>
Newsgroups	pl.comp.programming
Subject	Re: Tablica int i usuwanie duplikatów
Date	2015-09-19 03:08 +0200
Organization	ATMAN - ATM S.A.
Message-ID	<mticic$1e6$1@node2.news.atman.pl> (permalink)
References	(17 earlier) <1ozh9732tw6vb.1k80ivwsjct79.dlg@40tude.net> <mthm8f$p6g$1@node1.news.atman.pl> <13goui39dxzb2.1kw5grc7j0y14.dlg@40tude.net> <mthp48$epf$1@node2.news.atman.pl> <1amtzmln34a1o$.kdovd8ebh5p5$.dlg@40tude.net>

Show all headers | View raw

On 18.09.2015 22:50, szemrany wrote:
> On Fri, 18 Sep 2015 21:36:40 +0200, bartekltg wrote:
>
>>> Tak, tylko, że Delphi miało inne założenia produkcyjne i nie ma milionów
>>
>> Założenia miało te same. A nawet bardziej nastawione na biblioteki,
>> bo było to tzw RAD. Miałeś szbyko budować aplikacje z klocków,
>> nie pisać własny standardowy kontener.
>
> Specjalnie nie napisałem założenia projektowe tylko produkcyjne, choć może
> to też nieszczęśliwe słowo. Chodziło mi o to, że Delphi służy głównie do
> pisania aplikacji bazodanowych z GUI, a nie wysoko wydajnych aplikacji do
> przetwarzania danych.


Baza danych kojarzy mi się z wysoikowydajnym rpzetwarzaniem danych ;-)
OK, rozumiem, zę chodziło o korzystanie z niej, nie pisanie.

> Te klocki o których piszesz są na wyższym poziomie niż struktury danych i
> algorytmy, to moduły typu system raportów, warstwa DAL, kontrolki wizualne
> itd.



>
>>   > nie ma milionów
>>> kontenerów jak C++. Muszę część rzeczy wydłubać sam.
>>
>> Po prostu nie wierzę.
>
> Kilka lat temu znany tu Sebastian Biały wpadł na sąsiednią grupę delphi, bo
> coś zrobić w Delphi musiał i pytał m.in. o hash table. Gdy się dowiedział,
> że nie ma to dostał nomen omen białej gorączki i zbluzgał zarówno samo
> Delphi jak i kilka postronnych osób ;-) Fakt, że pytał o Delphi 5, które
> było z poprzedniego wieku. Teraz dodano kilka kontenerów, ale to jest
> dosłownie KILKA.

Jezusmariamisiek, jak za fortrana łupanego ;]


Ale w sumie te kilka kontenerów to już niezły start.
Zbiór, mapa, lista, kolejka, stos, kolejka piorytetowa.
Poza zbiorem wszystko znalazłem. Chyba większy problem
niż brak kontenerów jest kiepska dokumentacja (albo
to, że do przyzwoitej nie mogłem się dokopać).

Porządnego drzewa (takeigo, by mieć dostęp do wierzchołków
i po zmianie, w tym balansowaniu, moc poprawić jakeij informacje,
zależne od poddrzew - przydatna sprawa czasem) nie ma
i w bibliotece standardowej c++.

>> Tak, pascal jest mentalnie związany z uczeniem programowania,
>> i każdy nowy programista koniecnzie musi pisać własnego
>> qsorta i drzewo AVL, ale to szybko przechodzi, a jeśli
>> język jest więcej niż parę osób używany komenrcyjnie (a Delphi
>> jak mówisz, nadal jest, a jakis czas temu było bardzo poważnie
>> używane),  na pewno biblioteki są.
>
> Mało, malutko, jeszcze mniej... bo 90% delphiarzy nie potrzebuje. Bo i po


Potrzebują, potrzebują, przeceiż to tylko oczko wyżęj niż
sortowanie. Tylko nie wiedzą czego naprawdę potrzebują
i robią dookoła. Zerknij na pierwsza odpowiedź
http://stackoverflow.com/questions/13765606/associative-array-in-delphi-array-with-string-key-is-possible
https://www.prestwood.com/ASPSuite/KB/Document_View.asp?QID=101517
Object Pascal doesn't have a native associative array, but you can use a 
TStringList the same way.

I zaraz ktoś będzie trzytmał inty jako stringi;)


> co? Żeby robić szybką listę buttonów na formie czy ...szybko czekać na
> odpowiedź serwera SQL? ;-)

Nie zauważyłeś, że moc obliczeniowa wzrosła niemiłosiernie od czasów
pierwszych interfejdsów graficznych, a ich responsywność
nadal bywa neizadowalająca? ;-)


>> Zresztą, sam w poprzednim poście znalazłeś TDictionary,
>> odpowiednik mapy, i to w wersja która wygląda na szablonową.
>> Pewnie obok jest i zwykły zbiór, i tablica hashuhjąca.
>> TDictionary wystarczy.
>
> TDictionary<K, V> jest od 2009 roku w standardzie, jest generyczne (czy to
> odpowiednik szablonów to nie wiem,


To praktycznie synonimy. Pewnie jakaś subtelna różnica
jest, typu, zę sablony to rodzaj programowania generycznego,
ale mało to istotne.

> jest podobne do tego co ma C#:
> http://interactiveasp.net/blogs/spgilmore/archive/2009/12/23/using-generics-in-delphi.aspx
.
> Obok, rzeczywiście, jest jeszcze kilka:
> TList<T> - oparty o array of T
> TThreadList<T> - to samo tylko thread safe
> TQueue<T> - oparte o array of T
> TThreadedQueue<T> - j.w. thread safe
> TStack<T> - oparte o array of T
>


Hmm, wygląda na to, zę nie zrozumiałęm, myślaęłm, zę 'piszesz tablicę 
hashującą' na bazie Tdictionary, a to on sam jest tablicą hashującą
(a nie drzewem zrównoważonym).
http://delphi.about.com/od/beginners/a/using-t-dictionary-hash-tables-in-delphi.htm

> oraz starsze:
> THashedStringList - lista typu key-value, gdzie hash jest liczony w ten
> sposób:
>
> function TStringHash.HashOf(const Key: string): Cardinal;
> var
>    I: Integer;
> begin
>    Result := 0;
>    for I := 0 to Key.Length - 1 do
>      Result := ((Result shl 2) or (Result shr (SizeOf(Result) * 8 - 2))) xor
>        Ord(Key.Chars[I]);
> end;
>
> nie potrafię ocenić ile to warte.
>
> TBucketList - hash lista na pointery oparta o array of array of pointer,
> gdzie pierwsza tablica zawiera kubełki zbudowane przez proste przesunięcie
> bitów w prawo, a druga zawiera już wartości dla konkretnego kubełka.


O, i z tego co czytem, to jest odpowiednik std::set.
http://stackoverflow.com/questions/547879/how-to-judge-number-of-buckets-for-tbucketlist
"Aside from that, TBucketList is just an ordinary hash table like you 
learned about in your data-structure class."

I zaraz wspomina o TIntegerBucketList. Super, nie musisz bawić
się wskaźnikami, od razu ejst to, co trzeba.


> I to WSZYSTKO w standardzie.
> Uwierzysz, że nia ma nawet prostej linked listy? Wszak to ją się pisze na 3

Akurat takiej listy prawie nigdy nie używam ;-)

> zajęciach z programowania, także kiedyś w pascalu. Nie wiem dlaczego tak
> jest, ale widać rynek tego nie potrzebował.

Albo brak takiego wsparcia doprowadził do tego, że język stał
się niszą do robienia interfejsów do bazy danych:(


> Są co prawda fajne zewnętrzne projekty, a jeden z nich się rozwija od lat
> poważnie i wygląda na to, że już nie padnie, jest nim Spring for Delphi:
>
> https://bitbucket.org/sglienke/spring4d

> ale jeszcze nie zdążyłem go produkcyjnie użyć, bo już raz się wpakowałem w
> tego typu projekt, który potem zdechł i miałem dużo kłopotu z wymiksowaniem
> się z niego. Teraz dmucham na zimne.

Mi się nie udało na szybko nawet doikumentacji znaleźć, żeby
zobaczyć, co tam jest ;-)


>>> Nie chcę używać dziesiątek obcych bibliotek, bo to co teraz robię pakuję do
>>> swojego frejmworka do użycia także w przyszłości, więc nie chcę mieć zbyt
>>> wielu ogonów.
>>
>> Przejdź na ciemną stronę.
>> C++, java, nawet python.
>> Mniej czasu poświeceisz na  nowy język niż na pokonywanie
>> takich problemów. ;]
>
> Gdybym zaczynał od zera to pewnie tak bym zrobił, ale mam mnóstwo
> pracującego kodu już w Delphi i przy nim zostaję.

Ale mówisz o pracującym firmowym kodzie, czy własnych zabawkach?
Jak to drugie, to aż tyle tego jest?


> Poza tym C++, Java i Python odpadają, bo ja potrzebuję w dużej mierze pisać
> aplikację okienkowe pod Windows, a żaden z nich nie jest konkurencyjny w
> tym aspekcie dla Delphi.

Jasne, visual studio czy QT ma nieco inną filozofię okienkowania, ale
zaraz, za czasów borlanda był c++ builder. Bawiłęm się inm zaraz po tym,
jak bawiełm sie delphi. I był praktycznie identyczny (całę VCL było).
Google twierdzi, że Embarcadero też wypuszcza tę linię kompilatórów.

> Zerkam na C# i czekam co będzie teraz z
> Microsoftem i jego nowymi pomysłami. Otwarcie źródeł .NETa jest dobrym
> początkiem:
> https://github.com/Microsoft/dotnet

"C# to java, tylko lepiej zaprojektowana" jak mawiają złośliwi;-)


>> Da. A jeszcze szybsze byłoby zrobienie kopii i sortowanie ;-)
>
> Taką wersję też mam w roadmapie ;-)

Trochę wyników opisywanych algorytmów.

http://pastebin.com/Bd53Qj2e

cztery wersje, z hashmapą, ze zbiorem na drzewie, z hashmapą,
ale wstepnie wypelnioną i opróżnianą, oraz wersja naiwna.
Do tego wersja z sortowaniem, która biła na głowę wszystko;-)

Dalej w kodzie nie ma nic ciekawego a jest brzydki:]

M.M jednak miał niezłą intuicję, algorytm naiwny trzyma się jako
tako do 1000 liczb! Przynajmniej w porównaniu do kontenerowych,
w stosunku do sortowania to przebija już dla 10.


Sortowanie diała tak dobrze, że dorzuciłem gdzieś wpominaną wersję,
gdzie kopiuję tablice, sortuję, wyszukuję w niej przetwarzanego
elementu i indeksu tego elementu używam na tablicy 'czy już było'.
Szybsze, ale nie tak jak samo sortowanie i 'unique'.

Czy gdzieś nie ma błędów, nie wiem, specjalnie mocno nie testowałem ;-)

pzdr
bartekltg



hashmapa budowana
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 1.35577e-06s
100 zajelo 2.10569e-05s
1000 zajelo 0.000194975s
10000 zajelo 0.00224433s
100000 zajelo 0.0317218s

zbior budowany
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 6.0001e-07s
100 zajelo 1.06281e-05s
1000 zajelo 0.000148967s
10000 zajelo 0.002129s
100000 zajelo 0.0464341s

hashmapa usuwana
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 1.66747e-06s
100 zajelo 1.94978e-05s
1000 zajelo 0.00021605s
10000 zajelo 0.00233336s
100000 zajelo 0.0327335s

naiwne n^2
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 6.37173e-08s
100 zajelo 2.99953e-06s
1000 zajelo 0.000201813s
10000 zajelo 0.0190117s
100000 zajelo 2.0126s

sortowanie
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
1 11 12 55 56 89 457
szybkość
10 zajelo 5.71213e-08s
100 zajelo 8.9025e-07s
1000 zajelo 1.22392e-05s
10000 zajelo 0.000193209s
100000 zajelo 0.00364856s

sortowanie stab
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 2.15298e-07s
100 zajelo 4.51064e-06s
1000 zajelo 8.12086e-05s
10000 zajelo 0.00110467s
100000 zajelo 0.0156081s

**********************większe tablice, bez naiwnego*************

hashmapa budowana
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 1.206e-06s
100 zajelo 2.12195e-05s
1000 zajelo 0.00019574s
10000 zajelo 0.00224614s
100000 zajelo 0.0319085s
1000000 zajelo 0.447895s
10000000 zajelo 7.09252s

zbior budowany
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 6.55151e-07s
100 zajelo 1.02252e-05s
1000 zajelo 0.000142235s
10000 zajelo 0.00210293s
100000 zajelo 0.0458803s
1000000 zajelo 0.809938s
10000000 zajelo 14.873s

hashmapa usuwana
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 1.7566e-06s
100 zajelo 2.02052e-05s
1000 zajelo 0.000217613s
10000 zajelo 0.00229402s
100000 zajelo 0.0311955s
1000000 zajelo 0.484313s
10000000 zajelo 5.8356s

sortowanie
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
1 11 12 55 56 89 457
szybkość
10 zajelo 5.79164e-08s
100 zajelo 8.72629e-07s
1000 zajelo 1.14487e-05s
10000 zajelo 0.000183957s
100000 zajelo 0.00351675s
1000000 zajelo 0.0574259s
10000000 zajelo 0.73433s

sortowanie stab
poprawność:
12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
12 457 1 56 89 11 55
szybkość
10 zajelo 2.14358e-07s
100 zajelo 3.83037e-06s
1000 zajelo 7.91519e-05s
10000 zajelo 0.00108764s
100000 zajelo 0.0153062s
1000000 zajelo 0.267471s
10000000 zajelo 5.37913s

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-14 21:56 +0200
  Re: Tablica int i usuwanie duplikatów Adam Klobukowski <adamklobukowski@gmail.com> - 2015-09-14 13:50 -0700
  Re: Tablica int i usuwanie duplikatów witek <witek7205@gazeta.pl.invalid> - 2015-09-14 20:23 -0500
    Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 04:10 +0200
  Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 04:10 +0200
    Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-15 09:32 +0200
      Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-15 10:50 +0200
        Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-15 12:01 +0200
          Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-15 14:53 +0200
      Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 14:16 +0200
      Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-16 07:21 +0200
        Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 07:38 +0200
          Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-16 10:57 +0200
            Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 11:34 +0200
              Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 03:31 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 12:52 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 05:03 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 16:49 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 17:31 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 17:58 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 18:25 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 18:28 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 10:41 -0700
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 19:57 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 22:46 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 23:27 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-17 00:23 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-17 05:37 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 00:18 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-18 09:07 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 18:20 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 20:22 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 20:47 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 21:01 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 21:36 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 22:50 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 03:08 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 11:34 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 20:52 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 04:35 -0700
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 04:57 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 14:43 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 05:50 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 15:08 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 06:23 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 15:44 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:20 +0200
                Re: Tablica int i usuwanie duplikatów Tomasz Kaczanowski <kaczus@dowyciecia_poczta.onet.pl> - 2015-09-21 08:09 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:13 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:10 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 09:58 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 20:44 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-22 04:43 -0700
              Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-17 08:12 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-17 15:14 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-17 16:37 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-18 07:22 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 15:15 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-19 20:45 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 21:01 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-20 16:27 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-20 17:14 +0200
          Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 11:05 +0200
            Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 11:40 +0200
              Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 12:05 +0200
  Re: Tablica int i usuwanie duplikatów Sebastian Biały <heby@poczta.onet.pl> - 2015-09-16 19:11 +0200
    Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 10:46 -0700
      Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 19:55 +0200

csiph-web