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<T> 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