Path: csiph.com!goblin3!goblin.stu.neva.ru!wsisiz.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.POSTED!not-for-mail From: bartekltg Newsgroups: pl.comp.programming Subject: =?UTF-8?Q?Re:_Tablica_int_i_usuwanie_duplikat=c3=b3w?= Date: Fri, 18 Sep 2015 21:36:40 +0200 Organization: ATMAN - ATM S.A. Lines: 113 Message-ID: References: <3aivb8qrco1q$.13cffg23pn4pg.dlg@40tude.net> <50609ffa-fe60-473f-8adc-5be498ec3dc2@googlegroups.com> <1f8412e7-1873-4b19-9439-bcb269b9af3f@googlegroups.com> <1ozh9732tw6vb.1k80ivwsjct79.dlg@40tude.net> <13goui39dxzb2.1kw5grc7j0y14.dlg@40tude.net> NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: node2.news.atman.pl 1442605000 15151 89.73.81.145 (18 Sep 2015 19:36:40 GMT) X-Complaints-To: usenet@atman.pl NNTP-Posting-Date: Fri, 18 Sep 2015 19:36:40 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0 In-Reply-To: <13goui39dxzb2.1kw5grc7j0y14.dlg@40tude.net> Xref: csiph.com pl.comp.programming:27552 On 18.09.2015 21:01, szemrany wrote: > On Fri, 18 Sep 2015 20:47:42 +0200, bartekltg wrote: > >>>> Właśnie nie pamiętam ile to było. Oryginalny pytacz będzie >>>> testował, to pewnie nam powie jakie miał benchmarki :) Ja >>>> strzelam że pomiędzy 500-1000. >>> >>> Pytacz nie będzie chyba aż tak złożonych testów robił. Poza tym pytacz >>> wszystkich opisanych algorytmów nie kuma >> >> To trzeba pytać. Milczy, znaczy rozumie. >> ;-) >> >> Zwłaszcza po tym, jak marudziłeś, że za proste rozwiązania >> dostałeś;-) > > Nie proste tylko niepełnosprytne ;-) > A potem się zaczęło ...zbyt sprytnie :-) > > Gdy pytałem o algorytmy myślałem o czymś bardziej opartym o matematykę, ale > jak się okazuje akurat ten problem jest mało matematyczny. > >>> lub nie może zrobić, bo w Delphi >>> nie ma niektórych potrzebnych językowych patentów, jak np. sety. Tzn. są >>> sety, ale ograniczone do 256 elementów. >> >> Przez set mieliśmy na myśli kontener (u nas trzymający inty) oparty na >> zrównoważonych drzewach binarnych. Nie ma to nic wspolengo "set of" >> z (delphi) pascala. Unordered_set to kontener (zawierający u nas inty) >> który trzyma je w tablicy hashującej. > > 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. > nie ma milionów > kontenerów jak C++. Muszę część rzeczy wydłubać sam. Po prostu nie wierzę. 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ą. 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. >> Nie mam pojęćia, jak to się w Pascalu nazywa. (Googlem znalazłem tylko >> jakieś paskudzctwa bawięce się wskaźnikami do obiektów, ze świecą >> szukać informacji, co siedzi pod spodem i jaka jest złożoność operacji) >> Pewnie Tcośtamcośtam. :) >> Skoro jest to język nadal używany, na pewno gdzieś 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. ;] > >>> Zrobiłem na razie klasyczny algorytm z dwoma pętlami i porównaniem (z tym, >>> że zrobiłem dwie różne wersje) oraz teraz konwertuje algorytm, który podał >>> AK napisany w C. Na razie utknąłem na składni niektórych poleceń, czekam w >>> innym wątku aż AK mi odpowie. >>> Jeszcze zrobię werję z Hash Table, która jest zaimplementowana w Delphiowym >>> TDictionary (hash jest oparty o algorytm Jenkinsa). >>> I to chyba wszystko. >> >> Bez sensu. Tablicę hashującą robisz na tablicy. >> TDictionary to odpowiednik std::map, obiekt bardzo podobny do zbioru. >> Mając TDictionary nie musisz nic na nim budować, korzystasz z niego >> bezpośrednio, trzymając informację, int->ilosć wystyępień. >> Szczegoły już padły. > > Jak już pisałem wcześniej piszę generyczny moduł, który operuje na > tablicach TArray i potrafi z nich: > - usuwać dowolne elementy > - usuwać duplikaty > - porównywać dwie tablice > - itd. > > Stąd potrzebuję algorytmów niskopoziomowych, które sobie w tymże module > zaimplementuję. Jeśli okaże się, że użycie TDictionary da jakiś zysk na Przecież ni o tym pisałem. Wewnętrz algorytmu wyznaczajacego duplikaty używasz dołego TDictionary tak, jak w praktycznie wszystkich opisanych tu sposobach. > dużych tablicach względem algorytmu naiwnego z pętlami to tej wersji też > będę używał. Da. A jeszcze szybsze byłoby zrobienie kopii i sortowanie ;-) pzdr bartekltg