On Friday, September 18, 2015 at 12:18:57 AM UTC+2, bartekltg wrote:
> On 17.09.2015 14:37, M.M. wrote:
> > On Thursday, September 17, 2015 at 12:23:43 AM UTC+2, bartekltg wrote:
> >> On 16.09.2015 23:27, AK wrote:
> >>> Użytkownik "bartekltg" napisał:
> >>>
> >>>> No właśnie, niekiedy. A w standardowym przypadku jesteśąmy do tyłu.
> >>>> Jeden przebieg zajmie zauważalną cześć czasu proponowanych tu
> >>>> rozwiązań.
> >>>> To wydaje się zbyt lekki problem na wstępną analizę danych.
> >>>
> >>> Zalezy. Zalkezy co sie rozumie pod terminem "przypadek standardowy".
> >>> IMHO standardowy przypadek do dane "merytoryczne"/dziedzinowe.
> >>
> >> Przecież o tym piszę. Coś można wyciagnać i wykalibrować
> >> algorytm, jeśli wiadoom, jakich danych statystycznie się spodziewać.
> >
> > Jak już przeciągamy, to ja ciekawy jestem, dla jakich danych najszybszy
> > będzie będzie algorytm O(N^2). Jakie N, jaki procent duplikatów i jaki
> > rozstęp, aby był najszybszy. Coś w ten deseń (z góry sory za błędy):
> >
> > bool exists( int t[] , int N, int v ) {
> > for( i=0 ; i<N ; i++ )
> > if( t[i] == v )
> > return true;
> > return false;
> > }
> >
> > int uniq( int t[] , int N ) {
> > for( i=j=0 ; i<N ; i++ ) {
> > if( ! exist( t , j , t[i] ) )
> > t[j++] = t[i];
> > }
> > return j;
> > }
> >
> > Dla N=100 mamy około 2500 operacji. Przy N*LogN mamy
> > tylko 600, ale implementacja algorytmu kwadratowego
> > jest zabójczo wydajna.
>
> Pewnie jak przy sortowaniu. Tam granica to kilkadziesiąt
> elementów.
> Z tablicą hashującą jeszcze mniejsza. Kilka?
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.
Pozdrawiam

do góry

On 18.09.2015 18:07, M.M. wrote:
> On Friday, September 18, 2015 at 12:18:57 AM UTC+2, bartekltg wrote:

>>> bool exists( int t[] , int N, int v ) {
>>> for( i=0 ; i<N ; i++ )
>>> if( t[i] == v )
>>> return true;
>>> return false;
>>> }
>>>
>>> int uniq( int t[] , int N ) {
>>> for( i=j=0 ; i<N ; i++ ) {
>>> if( ! exist( t , j , t[i] ) )
>>> t[j++] = t[i];
>>> }
>>> return j;
>>> }
>>>
>>> Dla N=100 mamy około 2500 operacji. Przy N*LogN mamy
>>> tylko 600, ale implementacja algorytmu kwadratowego
>>> jest zabójczo wydajna.
>>
>> Pewnie jak przy sortowaniu. Tam granica to kilkadziesiąt
>> elementów.
>> Z tablicą hashującą jeszcze mniejsza. Kilka?
> Właśnie nie pamiętam ile to było.

std::sort w gcc przełącza przerywa rekunrencję qsorta
na rzecz sortowania przez wstawianie dla podtablic
mniejszych niż 16 elementów.

> Oryginalny pytacz będzie
> testował, to pewnie nam powie jakie miał benchmarki :) Ja
> strzelam że pomiędzy 500-1000.

Na pewno nie aż tyle.

pzdr
bartekltg

do góry

On Fri, 18 Sep 2015 09:07:34 -0700 (PDT), M.M. wrote:

>> Pewnie jak przy sortowaniu. Tam granica to kilkadziesiąt
>> elementów. Z tablicą hashującą jeszcze mniejsza. Kilka?
> 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 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.
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.

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

On 18.09.2015 20:22, szemrany wrote:
> On Fri, 18 Sep 2015 09:07:34 -0700 (PDT), M.M. wrote:
>
>>> Pewnie jak przy sortowaniu. Tam granica to kilkadziesiąt
>>> elementów. Z tablicą hashującą jeszcze mniejsza. Kilka?
>> 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ś;-)

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

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.


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

pzdr
bartekltg

do góry

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
kontenerów jak C++. Muszę część rzeczy wydłubać sam.

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

>> 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
dużych tablicach względem algorytmu naiwnego z pętlami to tej wersji też
będę używał.
Na razie węszę i w wolnych chwilach dopisuję kolejne kawałki kodu.

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

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

do góry

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

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

> 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, jest podobne do tego co ma C#:
http://interactiveasp.net/blogs/spgilmore/archive/20
09/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

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.

I to WSZYSTKO w standardzie.
Uwierzysz, że nia ma nawet prostej linked listy? Wszak to ją się pisze na 3
zajęciach z programowania, także kiedyś w pascalu. Nie wiem dlaczego tak
jest, ale widać rynek tego nie potrzebował.

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.

>> 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ę.
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. 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

>> 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 ;-)

Taką wersję też mam w roadmapie ;-)

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

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/associat
ive-array-in-delphi-array-with-string-key-is-possibl
e
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/20
09/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-dicti
onary-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-jud
ge-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

do góry

On Sat, 19 Sep 2015 03:08:27 +0200, bartekltg wrote:

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

Aplikacja bazodanowa =/= serwer bazy danych ;-)

>> 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 to jest zrozumiałe, założenia były jakie były i rozwijano w pierwszej
kolejności to co było powszechniej potrzebne. Do tego dochodzi zawierucha
związana z Borlandem, który 10 lat temu odpuścił sobie rozwój Delphi i
skończyło się prawie jego śmiercią. Po kilku latach znalazła i kilku
próbach jego utrzymania, znalazł się w końcu inwestor, firma Embarcadero,
producent narzędzi bazodanowych, który zaczął dość dynamiczny rozwój
zarówno środowiska jak i języka (unicode, x64, generyki, funkcje anonimowe,
bogate RTTI, kompilatory na platformy mobilne i OSX, itd.). Ale to wszystko
jest z dużym opóźnieniem względem świata. Poza tym ceny lecą w kosmos, a
bugi wraz z nimi.

> 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ć).
Dokumentacja jest tu:
http://docwiki.embarcadero.com/RADStudio/XE8/en/Main
_Page

np. dla kontenerów podstawowych:
http://docwiki.embarcadero.com/RADStudio/XE8/en/Work
ing_with_Lists

dla generyków:
http://docwiki.embarcadero.com/Libraries/XE8/en/Syst
em.Generics.Collections

> 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++.

Drzewa to jeden z tematów mniej przeze mnie rozpoznanych ;-)

>>> 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/associat
ive-array-in-delphi-array-with-string-key-is-possibl
e
> 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;)

No niestety, świadomość algorytmiki wśród delphiarzy jest nikła... sam
staram się wyjść poza schemat, ale to wiąże się z ...dłubaniem ;-)
A paradoksalnie to właśnie twórca Pascala napisał wszak klasyczną pozycję o
algorytmach i strukturach danych :-)

>> 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? ;-)

Tak, tak... i znam dobrze tego przyczyny. Czasem zresztą biorę udział w
poprawianiu takich aplikacji i nagle się okazuje, że da się prosto
zniwelować zamulenie GUI do zera :-)

>> 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/20
09/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-dicti
onary-hash-tables-in-delphi.htm

No właśnie tu miałem lekki dysonans, bo nie mogłem zrozumieć co do mnie
rozmawiasz z tym Dictionary i przyjałem, że m za głupi ;-)
A wszak pisałem kilka postów wyżej:

"Jeszcze zrobię werję z Hash Table, która jest zaimplementowana w
Delphiowym TDictionary (hash jest oparty o algorytm Jenkinsa)."

>> oraz starsze:
>> 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-jud
ge-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.

Hmm... czyli tego mógłbym użyć w algorytmie w którym wspominaliście o set?

>> 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 ;-)

A ja niedawno chciałem...

>> 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:(

Uhm... właśnie, a szkoda, bo lubię jego czytelność, która znacznie ułatwia
refaktoring, np. w stosunku do nieszczęsnej składni C++ (no ofense
siplusowcy! ;-)

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

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

Przecież jest:
https://bitbucket.org/sglienke/spring4d/wiki/Home
i stąd odnośniki.

Poza tym ja już od dawna jako najlepszej dokumentacji używam samych źródeł
oraz źródeł testów jednostkowych ;-) Choć rozumiem, że dla kogoś spoza
świata Object Pascala kod może być trudniejszy do czytania, tak jak dla
mnie potworki C++ :-P

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

O pracującym kodzie, a własne zabawki są podbudową tego pracującego kodu
:-)

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

No tak, tu mnie masz... Ale gdybym jednak się już miał zajmować czymś innym
to nie będzie to na pewno C++... nie lubię tej skomplikowanej składni i
asemblerowej niskopoziomowości. Ale z ciekawości poszukam kiedyś czy są w
nim te wszystkie struktury dostępne o jakich piszecie.
Chyba, że ktoś na tej grupie to wie i się podzieli?

>> 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;-)

To chyba zaleta, że lepiej zaprojektowana? :-)
Btw wiesz, że C# zaprojektował twórca Delphi, którego MS podkupił pod
Borlanda? I ideologicznie C# jest bardzo bliski Delphi, łatwo się
przerzucić.

> Trochę wyników opisywanych algorytmów.
>
> http://pastebin.com/Bd53Qj2e

Za kod dzięki, prześledzę uważnie.

> 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

No to mam dane do rozkminy na dłuższe posiedzenie, dzięki :-)

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

On Saturday, September 19, 2015 at 3:08:29 AM UTC+2, bartekltg wrote:
> 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.
Jeśli algorytmy się przełączają na inne wersje gdy jest
mało elementów, to moja intuicja nie ma tutaj zastosowania :)




> 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 ;-)
Tylko nie byłem pewny, czy nie sortujesz już częściowo posortowanych
elementów. Lekko zmieniłem Twój kod i dodałem moją samoróbkę. Moją
samoróbkę można jeszcze ze dwa razy przyspieszyć przez:
1) lepszą kompilację
2) profilowanie
3) lepszą funkcję hash
4) lepsze rozwiązanie if( zero )
Rzecz jasna, też nie wiem czy nic nie spartoliłem, macie kod do
sprawdzenia:
http://pastebin.com/uRAqi8iv

Wyniki:

samorobka
poprawność:
12 457 1 56 89 11 55
100 zajelo 4.551e-06s
1000 zajelo 2.9805e-05s
10000 zajelo 0.000306844s
100000 zajelo 0.004824s
1000000 zajelo 0.050433s
10000000 zajelo 0.564702s
100000000 zajelo 6.84356s // najlepszy wynik

hashmapa budowana
poprawność:
12 457 1 56 89 11 55
100 zajelo 2.5173e-05s
1000 zajelo 0.000193544s
10000 zajelo 0.00218883s
100000 zajelo 0.0375231s
1000000 zajelo 0.797666s
10000000 zajelo 9.25089s
zbior budowany
poprawność:
12 457 1 56 89 11 55
100 zajelo 2.7255e-05s
1000 zajelo 0.000254757s
10000 zajelo 0.00330752s
100000 zajelo 0.0667916s
1000000 zajelo 1.46435s
10000000 zajelo 23.8021s
hashmapa usuwana
poprawność:
12 457 1 56 89 11 55
100 zajelo 2.0964e-05s
1000 zajelo 0.000203064s
10000 zajelo 0.002271s
100000 zajelo 0.0400408s
1000000 zajelo 0.68298s
10000000 zajelo 7.91133s
sortowanie
poprawność:
1 11 12 55 56 89 457
100 zajelo 4.154e-06s
1000 zajelo 5.4322e-05s
10000 zajelo 0.00068978s
100000 zajelo 0.00846882s
1000000 zajelo 0.100396s
10000000 zajelo 1.16484s
100000000 zajelo 13.3129s

sortowanie stab
poprawność:
12 457 1 56 89 11 55
100 zajelo 1.2285e-05s
1000 zajelo 0.000156857s
10000 zajelo 0.00193924s
100000 zajelo 0.023655s
1000000 zajelo 0.394504s
10000000 zajelo 7.24644s


> 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


Pozdrawiam

do góry