Tablica int i usuwanie duplikatów

[szemrany]

Hejka,

Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
sortowania.
Jak to zrobić wydajnie? Jakiś algorytm sprytny?

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

[Adam Klobukowski]

W dniu poniedziałek, 14 września 2015 21:56:08 UTC+2 użytkownik szemrany napisał:
> Hejka,
>
> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
> sortowania.
> Jak to zrobić wydajnie? Jakiś algorytm sprytny?

Trochę mało informacji. Jeżeli dziedzina wartości intów jest ograniczona, można zliczać występowanie każdej wartości. Jeśli nie, to bez czegoś co przypomina sortowanie sie nie obędzie.

AdamK

[witek]

szemrany wrote:
> Hejka,
>
> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
> sortowania.
> Jak to zrobić wydajnie? Jakiś algorytm sprytny?
>

collection zamiast tablicy?

[bartekltg]

On 14.09.2015 21:56, szemrany wrote:
> Hejka,
>
> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
> sortowania.
> Jak to zrobić wydajnie? Jakiś algorytm sprytny?

Wpakuj do tablicy hashującej, takiej bez powtórzeń
(unordered_set<> w cpp). [To, jak się zastanowić,
bardzo podobne rozwiązanie do proponowanego przez Adama]

Może być nawet szybsze niż sortowanie (oczekiwaną złożoność
ma liniową), ale za to pamięci zeżre trochę.

Czemu nie chcesz sortowania?

pzdr
bartekltg

[bartekltg]

A co to?

pzdr
bartekltg

[szemrany]

On Tue, 15 Sep 2015 04:10:29 +0200, bartekltg wrote:

>> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
>> sortowania.
>> Jak to zrobić wydajnie? Jakiś algorytm sprytny?
>
> Wpakuj do tablicy hashującej, takiej bez powtórzeń
> (unordered_set<> w cpp). [To, jak się zastanowić,
> bardzo podobne rozwiązanie do proponowanego przez Adama]
>
> Może być nawet szybsze niż sortowanie (oczekiwaną złożoność
> ma liniową), ale za to pamięci zeżre trochę.

I naprawdę algorytmika niczego lepszego nie wymyśliła?

> Czemu nie chcesz sortowania?

W zasadzie w przypadku jaki tu i teraz potrzebuję sortowanie jest
dopuszczalne, ale chciałem to zrobić generycznie i mieć do wykorzystania w
innych przypadkach, a nie zawsze zmiana kolejności elementów będzie
dopuszczalna.

[AK]

Użytkownik "szemrany" <szem...@offline.off> napisał:

> I naprawdę algorytmika niczego lepszego nie wymyśliła?

Ano wymyslila, ale "to zalezy" (a nawet bardzo zalezy).

Jesli roznica max - min nie jest za duza to "funkcja hashujaca"
sprowadzi sie do "indeksowania wartoscią" w rodzaju
uniques[x - min] = x

Jesli np wartosci mogace wystapic w tablicy sa z gory znane
i niezbyt liczne to np. "perfect hash" nie jest najgorszym wyborem.

Ogolnie to podpowiedz: specjalizowany _pod inty_ kontener typu set
(zwykle "hashujacy" lub b-drzewiasty).
powinna wystarczyc.

AK


---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe Avast.
https://www.avast.com/antivirus

[szemrany]

On Tue, 15 Sep 2015 10:50:15 +0200, AK wrote:

>> I naprawdę algorytmika niczego lepszego nie wymyśliła?
>
> Ano wymyslila, ale "to zalezy" (a nawet bardzo zalezy).
>
> Jesli roznica max - min nie jest za duza to "funkcja hashujaca"
> sprowadzi sie do "indeksowania wartoscią" w rodzaju
> uniques[x - min] = x
>
> Jesli np wartosci mogace wystapic w tablicy sa z gory znane
> i niezbyt liczne to np. "perfect hash" nie jest najgorszym wyborem.
>
> Ogolnie to podpowiedz: specjalizowany _pod inty_ kontener typu set
> (zwykle "hashujacy" lub b-drzewiasty).
> powinna wystarczyc.

To nie jest algorytmika, to brute force :-)
Ale chyba rzeczywiście nie ma sprytniejszej metody lub jeszcze jej nie
wymyślono.

[bartekltg]

On 15.09.2015 09:32, szemrany wrote:
> On Tue, 15 Sep 2015 04:10:29 +0200, bartekltg wrote:
>
>>> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
>>> sortowania.
>>> Jak to zrobić wydajnie? Jakiś algorytm sprytny?
>>
>> Wpakuj do tablicy hashującej, takiej bez powtórzeń
>> (unordered_set<> w cpp). [To, jak się zastanowić,
>> bardzo podobne rozwiązanie do proponowanego przez Adama]
>>
>> Może być nawet szybsze niż sortowanie (oczekiwaną złożoność
>> ma liniową), ale za to pamięci zeżre trochę.
>
> I naprawdę algorytmika niczego lepszego nie wymyśliła?

A co byś chciał lepszego?

>
>> Czemu nie chcesz sortowania?
>
> W zasadzie w przypadku jaki tu i teraz potrzebuję sortowanie jest
> dopuszczalne, ale chciałem to zrobić generycznie i mieć do wykorzystania w

Sortowanie jest bardzo generyczne.

> innych przypadkach, a nie zawsze zmiana kolejności elementów będzie
> dopuszczalna.

Tak podejrzewałem, że nie chcesz zamieniać kolejności,
ale tego NIE NAPISAŁEŚ ;p

Przechodząc tablicę trzymaj kontener (drzewo zrównoważone - set,
lub tablice hashującą - unordered set) z elementami już
przetworzonymi, obrabiasz element z tablicy jeśli nie ma go
w pomocniczym kontenerze. Po obrobieniu wsadzasz go tam.

pzdr
bartekltg

[AK]

Użytkownik "szemrany" <szem...@offline.off> napisał:

> To nie jest algorytmika, to brute force :-)

Jakie brute force ? Zastanow sie.
Perfect hash (powszechnie stosowany np w kompilatorach,
roznych dispatcherach i nie tylko),

https://en.wikipedia.org/wiki/Perfect_hash_function
http://homepages.dcc.ufmg.br/~nivio/papers/cikm07.pdf
https://en.wikipedia.org/wiki/Dynamic_perfect_hashing

czy mapowania wartosc-index/indeksowanie wartoscią
(patrz chocby Bentley "Perelki programowania") to brute force ?

To przeciez _najwydajniejsze_ z mozliwych sposobow
znaljdowania/separacji (w tym wartosci unikalnych).

[slawek]

On Tue, 15 Sep 2015 09:32:50 +0200, szemrany <szem...@offline.off>
wrote:

> I naprawdę algorytmika niczego lepszego nie wymyśliła?

Po prostu zlicz wystąpienia. Dla skończonego zbioru int'ów złożoność
obliczeniowa O(N).

[bartekltg]

To jest ogólnie nienajgorszy pomysł (padł w wątku trzeci raz),
ale pomijasz koszmarną ilość szczegółów, jak zliczać ;-)

pzdr
bartekltg

[slawek]

On Wed, 16 Sep 2015 07:38:10 +0200, bartekltg <bart...@gmail.com>
wrote:

> ale pomijasz koszmarną ilość szczegółów, jak zliczać ;-)

Normalnie; zero, mnóstwo. ;)

[AK]

Użytkownik "bartekltg" <bart...@gmail.com> napisał:

> jak zliczać ;-)

Właśnie. W tym cały ambaras :)

[bartekltg]

Dlatego proponowałem (unordered_)set zamiast (...)map.
Jest/nie ma w pomocniczym zbiorze.

> ;)

Ty już nie udawaj, ze nie wiesz, o co pytam ;-)

pzdr
bartekltg

[bartekltg]

On 16.09.2015 11:05, AK wrote:
> Użytkownik "bartekltg" <bart...@gmail.com> napisał:
>
>> jak zliczać ;-)
>
> Właśnie. W tym cały ambaras :)

Przejrzałem pobieżnie Twoje linki o idealnym minilalnym hashu,
to wygląda na sporo roboty dla procesora (porównujemy do
sortowania i zwykłego haszowania z jakimś prostym rozwiązywaniem
kolizji), jeśli potem każdy element odczytamy ~raz.


pzdr
bartekltg

[AK]

Użytkownik "bartekltg" <bart...@gmail.com> napisał:

> Przejrzałem pobieżnie Twoje linki o idealnym minilalnym hashu,
> to wygląda na sporo roboty dla procesora (porównujemy do
> sortowania i zwykłego haszowania z jakimś prostym rozwiązywaniem
> kolizji), jeśli potem każdy element odczytamy ~raz.

Nie no zgadza sie. Dlatego to sie nadaje glownie do ("statycznych") setow
typu slowa kluczowe j.prog czy jakis dispatrzer po nazwie dla z gory
okreslonych nazw itp.

Co nie zmienia faktu ze jest to rozwiazanie "prawie idelane" w sensie
zlozonosci O(x)

[M.M.]

On Wednesday, September 16, 2015 at 11:34:13 AM UTC+2, bartekltg wrote:
> Dlatego proponowałem (unordered_)set zamiast (...)map.
> Jest/nie ma w pomocniczym zbiorze.

To jest najszybsza metoda w praktyce. Czasami możemy trafić na
dane, dla których funkcja hash da mnóstwo kolizji. Problem
kolizji trochę rekompensuje odpowiednia implementacja hash-table,
ponieważ można ją przeglądać tak jak lubi pamięć cache. W
przypadku RBTree nigdy nie jest przyjaźnie dla cache, ale
jest gwarancja N*Log(N) dla każdych danych.

Pozdrawiam

P.S.
Chyba w popularnych bibliotekach nie ma implementacji hash-table
która jest przyjazna dla pamięci cache, chyba trzeba samemu
wyrzeźbić. Szczególnie warto samemu, gdy wiemy z góry ile
będzie danych liczb.

[bartekltg]

w STD jest metoda łańcuchowa. Kiedyś nawet czyałem, że
za tym, że nie sosją jakiergoś adresowania otwartego
stoi za jakaś idealogia.

Parę razy natknąłem się na googlowe tablice mieszające
https://github.com/sparsehash/sparsehash
Kilka gatnków, do wyboru.

Stare, ale ciekawe porównanie:
http://incise.org/hash-table-benchmarks.html


Za to jakiś czas temu złapałem się na tym, że std:hash na intach
... zwraca argument. Jest różnowartośćiowa, ale dość słabo miesza:(



pzdr
bartekltg

[M.M.]

Dzięki za benchmarki. Widzę, że QHash ładnie tam wypada. Pamiętam właśnie, że
kiedyś wydziargałem swoją specjalistyczną hash-table i działała tylko
odrobinę szybciej niż qhash.

Pozdrawiam

[bartekltg]

On 16.09.2015 12:31, M.M. wrote:

> On Wednesday, September 16, 2015 at 11:34:13 AM UTC+2, bartekltg wrote:
>> Dlatego proponowałem (unordered_)set zamiast (...)map.
>> Jest/nie ma w pomocniczym zbiorze.
> To jest najszybsza metoda w praktyce. Czasami możemy trafić na
> dane, dla których funkcja hash da mnóstwo kolizji. Problem
> kolizji trochę rekompensuje odpowiednia implementacja hash-table,
> ponieważ można ją przeglądać tak jak lubi pamięć cache. W
> przypadku RBTree nigdy nie jest przyjaźnie dla cache, ale
> jest gwarancja N*Log(N) dla każdych danych.

A, jeszcze jedno, tutaj nie musimy używać set<int>, bo to rzeczywiście
nam nieźle zwolni.
Weźmy trudniejszą wersję, czyli pytacz chce przetwarzać liczby
w takiej kolejności w jakiej są w tablicy, tylko pominąć już raz
przetworzone. Ale skoro liczby mamy dane z góry, możemy je sobie
skopiować, posortować, (opcjonalnie machnąć std::unique aby pozbyć
\się duplkatów z posortowanej wersji). Do tego trzymamy tablicę
booli (vector<bool>) o tej samej długości.

Dostając liczbę, wyszukujemy ją binarnie w pomoczniczej posortowanej
tablicy, sprawdzamy czy bit w teblicy booli jest zapalony.

Będzie szybsze niż operacja na drzewach, i prawdopodobnie zajmie
mniej pamięci niż obie pozostałe wersje.
Prawdopodobnie, bo dla złośliwego przypadku - bardzo dużo podobnych
danych, ale niewiele różnych liczb, lepiej jest tworzyć
pomocniczy zbiór na żywo.

pzdr
bartekltg

[AK]

Użytkownik "bartekltg" <bart...@gmail.com> napisał:

> A, jeszcze jedno, tutaj nie musimy używać set<int>, bo to rzeczywiście
> nam nieźle zwolni.
> Weźmy trudniejszą wersję, czyli pytacz chce przetwarzać liczby
> w takiej kolejności w jakiej są w tablicy, tylko pominąć już raz
> przetworzone. Ale skoro liczby mamy dane z góry, możemy je sobie
> skopiować, posortować, (opcjonalnie machnąć std::unique aby pozbyć
> \się duplkatów z posortowanej wersji). Do tego trzymamy tablicę
> booli (vector<bool>) o tej samej długości.
>
> Dostając liczbę, wyszukujemy ją binarnie w pomoczniczej posortowanej
> tablicy, sprawdzamy czy bit w teblicy booli jest zapalony.
>
> Będzie szybsze niż operacja na drzewach, i prawdopodobnie zajmie
> mniej pamięci niż obie pozostałe wersje.
> Prawdopodobnie, bo dla złośliwego przypadku - bardzo dużo podobnych
> danych, ale niewiele różnych liczb, lepiej jest tworzyć
> pomocniczy zbiór na żywo.

Po co tak skomplikowanie ?
Mozna bardzo prosto.
1. Pytacz tworzy (pustego) seta (np.hash-seta)
2. Pytacz idzie/iteruje sobie po tablicy intow.
Dla kazdego inta sprawdza czy jest w secie
jesli tak to: vec[i] := wartosc markujaca "nic" (jakies MAX_UINT albo cus)
jesli nie to: dodaje wartosc vec[i] do seta
3. i += 1

Ma zarowno wektor zmodyfikowany "w miejscu" (rozumiem, ze tak chcial), a i kolejnosc zachowana.
Wydajne, proste, niezalezne od postaci/implementacji seta.

PS: Oczywiscie mozna jeszcze inaczej: nie markujac "nic" tylko biezacy kompiujac
vec[i] za ostatni niepowtarzalny (pamietajac wczesniej jego indeks) ale po co/to zalezy ?
Byc moze lepiej/prosciej pozniej odfiltrowac przy iteracji te elementy z "nic"

[bartekltg]

On 16.09.2015 17:31, AK wrote:
> Użytkownik "bartekltg" <bart...@gmail.com> napisał:
>
>> A, jeszcze jedno, tutaj nie musimy używać set<int>, bo to rzeczywiście
>> nam nieźle zwolni.
>> Weźmy trudniejszą wersję, czyli pytacz chce przetwarzać liczby
>> w takiej kolejności w jakiej są w tablicy, tylko pominąć już raz
>> przetworzone. Ale skoro liczby mamy dane z góry, możemy je sobie
>> skopiować, posortować, (opcjonalnie machnąć std::unique aby pozbyć
>> \się duplkatów z posortowanej wersji). Do tego trzymamy tablicę
>> booli (vector<bool>) o tej samej długości.
>>
>> Dostając liczbę, wyszukujemy ją binarnie w pomoczniczej posortowanej
>> tablicy, sprawdzamy czy bit w teblicy booli jest zapalony.
>>
>> Będzie szybsze niż operacja na drzewach, i prawdopodobnie zajmie
>> mniej pamięci niż obie pozostałe wersje.
>> Prawdopodobnie, bo dla złośliwego przypadku - bardzo dużo podobnych
>> danych, ale niewiele różnych liczb, lepiej jest tworzyć
>> pomocniczy zbiór na żywo.
>
> Po co tak skomplikowanie ?

Przecież napisałem jakie są wady i zalety tamtej metody w stosunku
do tej najprostszej. ;-)
Jeśli unikalnych elementów jest praie n, to ta metoda jest szybsza od
set i mniej pamieciożerna od seta i unordered_set.

Pytacz narzekał na niedobór algorytmów, to dajmu mu do wyboru;-)

> Mozna bardzo prosto.
> 1. Pytacz tworzy (pustego) seta (np.hash-seta)
> 2. Pytacz idzie/iteruje sobie po tablicy intow.
> Dla kazdego inta sprawdza czy jest w secie

...

> jesli nie to: dodaje wartosc vec[i] do seta

To co opisałeś to z grubsza dwie ostatnie linijki mojego postu.
Nie rozpisywałem się, bo już było w wątku.
Trzeba było te algorytmiki nazywać. I będzie
[1] szemrany 10:40
[2] A.K 11:34
[3] M.M 14:56

;-)

> Ma zarowno wektor zmodyfikowany "w miejscu" (rozumiem, ze tak chcial), a
> i kolejnosc zachowana.

To nie jest algorytm działający w miejscu. Średnio potrzebuje
on O(n) pamięci.

> Wydajne, proste, niezalezne od postaci/implementacji seta.

> PS: Oczywiscie mozna jeszcze inaczej: nie markujac "nic" tylko biezacy
> kompiujac
> vec[i] za ostatni niepowtarzalny (pamietajac wczesniej jego indeks) ale
> po co/to zalezy ?
> Byc moze lepiej/prosciej pozniej odfiltrowac przy iteracji te elementy z
> "nic"

Myślałem że autor chce tylko odpalić jakąś funkcję dla unikalnych
elementów. Jeśli chce zamienić zawartosć tablicy,
to jest to raczej standardowy sposób niż przekombinowanie, wszelkie
unique czy remove_if tak działają. Jedziemy dwoma iteratorami,
"zapisującym" i "odczytującym".
while (odczytujący!=end)
jeśli ( odczytujący pokazuje na pierwsze wystąpienie),
{wartość zapisujemy pod iterator "zapisyjący"
i przesuwamy 'zap.' o oczko. }
"Odczytujący" robi krok.
//zabawa z obsługą pomocniczego zbior jak poprzednio,

pzdr
bartekltg

[AK]

Użytkownik "bartekltg" <bart...@gmail.com> napisał:

> To nie jest algorytm działający w miejscu. Średnio potrzebuje
> on O(n) pamięci.

Gdzie n to ilosc unikalnych w zbiorze, a nie rozmiar calego zbioru.

[bartekltg]

On 16.09.2015 18:25, AK wrote:
> Użytkownik "bartekltg" <bart...@gmail.com> napisał:
>
>> To nie jest algorytm działający w miejscu. Średnio potrzebuje
>> on O(n) pamięci.
>
> Gdzie n to ilosc unikalnych w zbiorze, a nie rozmiar calego zbioru.

Pesymistycznie n=~=N.

Nieżależnie od tego - nie ejst to algorytm działajacy w miejscu ;-)

pzdr
bartekltg

[Sebastian Biały]

On 2015-09-14 21:56, szemrany wrote:
> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
> sortowania.
> Jak to zrobić wydajnie? Jakiś algorytm sprytny?

http://stackoverflow.com/questions/1453333/how-to-make-elements-of-vector-unique-remove-non-adjacent-duplicates

Sporo tam odpowiedzi.

Możesz też, jesli twoje zgadnienie spełnia dodatkowe warunki,
zainteresować się np. pierwszym zadaniem z "Perełki Oprogramowania"
gdzie coś zbliżonego rozwiązano na wektorze bitowym (przy okazji
sortując "za darmo").

[M.M.]

On Wednesday, September 16, 2015 at 6:26:00 PM UTC+2, AK wrote:
> Użytkownik "bartekltg" napisał:

>
> > To nie jest algorytm działający w miejscu. Średnio potrzebuje
> > on O(n) pamięci.
>
> Gdzie n to ilosc unikalnych w zbiorze, a nie rozmiar calego zbioru.

Przy perfect-hash ilość bitów * ( max_value - min_value + 1). Dla
małej rozpiętości można łatwo zrobić perfect-hash.

Dróg jest wiele, a jaką wybrać, to zależy od konkretnych danych.

Pozdrawiam

[M.M.]

Właśnie, dzięki tej metodzie, mamy za półdarmo sortowanie w czasie
O(max_value-min_value+1).

Pozdrawiam

[bartekltg]

Radixsort?

pzdr
bartekltg

[AK]

Użytkownik "M.M." <mmar...@gmail.com> napisał:

> Gdzie n to ilosc unikalnych w zbiorze, a nie rozmiar calego zbioru.
> Przy perfect-hash ilość bitów * ( max_value - min_value + 1). Dla
> małej rozpiętości można łatwo zrobić perfect-hash.
>
> Dróg jest wiele, a jaką wybrać, to zależy od konkretnych danych.

Ano wlasnie, a to jest czesto omijana sprawa ana rzecz "generycznosci".
Zawsze warto przeanalizowac dane (chocby tylko po min i max).
Koszt maly. Tylko jeden przebieg.
Zysk (niekiedy) ogromny

[bartekltg]

On 16.09.2015 19:57, AK wrote:
> Użytkownik "M.M." <mmar...@gmail.com> napisał:
>
>> Gdzie n to ilosc unikalnych w zbiorze, a nie rozmiar calego zbioru.
>> Przy perfect-hash ilość bitów * ( max_value - min_value + 1). Dla
>> małej rozpiętości można łatwo zrobić perfect-hash.
>>
>> Dróg jest wiele, a jaką wybrać, to zależy od konkretnych danych.
>
> Ano wlasnie, a to jest czesto omijana sprawa ana rzecz "generycznosci".
> Zawsze warto przeanalizowac dane (chocby tylko po min i max).
> Koszt maly. Tylko jeden przebieg.
> Zysk (niekiedy) ogromny

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.

Za to jeśli wiemy coś o rozkładzie od początku, można dobrać
algorytm, choćby czy tworzyć zbiór dynamicznie zaczynając od
małej pamięći dla tej tablicy, powiększając, a więc realokując i
rehaszując w mairę potrzeby (jeśli liczba unikalnych wpisów jest
mała) czy budować od razu w tablicy hashującej wielkośći 2n (dla k=~=n).

Sprawdzanie min/max ma jedną neidogodność. Unikalnych wpisów może
być mało, a rozpiętość ich wartośći duża.


pzdr
bartekltg

[AK]

Użytkownik "bartekltg" <bart...@gmail.com> 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.
Jesli to sa dane "merytoryczne" to max -min << MAX_UINT
a wtedy mozna "zjechac" zznacznie z pamiecia gdyz zamiast hasha pelnego
uinta mozna uzyc bitseta na rzeczywiscie uzywawanej maxymalnej ilosci bitow
/czyli bits(max - min)/.

> Za to jeśli wiemy coś o rozkładzie od początku, można dobrać
> algorytm, choćby czy tworzyć zbiór dynamicznie zaczynając od
> małej pamięći dla tej tablicy, powiększając, a więc realokując i rehaszując w mairę potrzeby
> (jeśli liczba unikalnych wpisów jest
> mała) czy budować od razu w tablicy hashującej wielkośći 2n (dla k=~=n).

I taki wlasnie jest (mniej wiecej) algorytm pythonowy ktory podalem szemranemu.

[bartekltg]

On 16.09.2015 23:27, AK wrote:
> Użytkownik "bartekltg" <bart...@gmail.com> 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ć.

> Jesli to sa dane "merytoryczne" to max -min << MAX_UINT

Bardzo dziwne załozenie. Pewnie prawdziwe, w _neiktórych_
dziedzinach.

> a wtedy mozna "zjechac" zznacznie z pamiecia gdyz zamiast hasha pelnego
> uinta mozna uzyc bitseta na rzeczywiscie uzywawanej maxymalnej ilosci bitow
> /czyli bits(max - min)/.

Główny spadek zapotrzebowania pamięciowego bierze się stąd,
że tablica będzie nie większa niż O(max-min).
Jak max-min zejdzie do zakresu bajta-dwóch, to w ogole
nie bawiłbym się w hashowanie, tylko zliczał. A to było
opisane jako pierwsza metoda w tym wątku.
Jest to jednak bardzo sztuczny przypadek (tak, tak, są
"dziedziny" gdzie to przypadek standardowy).



pzdr
bartekltg

[slawek]

On Wed, 16 Sep 2015 11:34:13 +0200, bartekltg <bart...@gmail.com>
wrote:

> Dlatego proponowałem (unordered_)set zamiast (...)map.

A jest set w Fortranie?

[M.M.]

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.

Pozdrawiam

[bartekltg]

A w Formula Translator jest coś poza macierzami zespolonymi? ;-)

Jak nie ma, to trzeba napisać.
Albo użyć języka, który lepiej nadaje się do naszych zadań.

pzdr
bartekltg

[AK]

Użytkownik "bartekltg" <bart...@gmail.com> napisał:

> Jak nie ma, to trzeba napisać.

Juz dawno napisane. Np:

http://flibs.sourceforge.net/sets.html

[bartekltg]

Pewnie jak przy sortowaniu. Tam granica to kilkadziesiąt
elementów.
Z tablicą hashującą jeszcze mniejsza. Kilka?

pzdr
bartyekltg

[slawek]

On Thu, 17 Sep 2015 15:14:54 +0200, bartekltg <bart...@gmail.com>
wrote:

> A w Formula Translator jest coś poza macierzami zespolonymi? ;-)

Są coarray. Jest OMP i ACC. BLAS. Jest operator potęgowania.

[bartekltg]

Czyli możesz mnożyć zespolone macierze równolegle i na GPU ;-)

FORTRAN jest bardzo dobrym językiem, ale jednek też o dość wąskiej
specjalizacji. Można tworzyć tam odpowiednik wszystkich struktur STLa.
Tylko po co skoro jest to bardzo upierdliwe i niewygodne. W COBOLu też
można ;-)


pzdr
bartgekltg

[M.M.]

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

[bartekltg]

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

[szemrany]

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

[bartekltg]

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

[szemrany]

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.

[bartekltg]

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

[szemrany]

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

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

[bartekltg]

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

[szemrany]

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

dla generyków:
http://docwiki.embarcadero.com/Libraries/XE8/en/System.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/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;)

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

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

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.

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

[M.M.]

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

Pozdrawiam

[M.M.]

On Saturday, September 19, 2015 at 1:35:59 PM UTC+2, M.M. wrote:
> 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ą,
>
>

> Pozdrawiam

Bym zapomniał. Co z wersją multiprocesorową tego algorytmu?
Mergesort jest najlepszy?
Pozdrawiam

[szemrany]

On Sat, 19 Sep 2015 04:35:57 -0700 (PDT), M.M. wrote:

> Rzecz jasna, też nie wiem czy nic nie spartoliłem, macie kod do
> sprawdzenia:
> http://pastebin.com/uRAqi8iv

W jakim kompilatorze to kompilujecie? Czy to zgodne z MS VS C++?
A jest może jakieś proste IDE dla Windows, żeby można pod debugerem to
odpalić i krokowo "zbadać"?

Pytanie drugie:

return ( (xx*67523u + 31237u) ^ (xx*78529u + 96285u) ) % s2;

Skąd akurat takie wartości w hashu? To wynika z jakichś matematycznych
założeń czy statystycznie wyliczone?

[M.M.]

On Saturday, September 19, 2015 at 2:43:47 PM UTC+2, szemrany wrote:
> W jakim kompilatorze to kompilujecie?

Chyba dowolny C++11

> Czy to zgodne z MS VS C++?

Chyba tak.

> A jest może jakieś proste IDE dla Windows, żeby można pod debugerem to
> odpalić i krokowo "zbadać"?

Może qtcreator?

> Pytanie drugie:
> return ( (xx*67523u + 31237u) ^ (xx*78529u + 96285u) ) % s2;
>
> Skąd akurat takie wartości w hashu? To wynika z jakichś matematycznych
> założeń czy statystycznie wyliczone?

Wpisałem na oko :)


Pozdrawiam

[szemrany]

On Sat, 19 Sep 2015 05:50:02 -0700 (PDT), M.M. wrote:

> qtcreator?

Pogooglałem i qtCreator jest ponoć wielki i ciężki, ale jest kilka
lżejszych środowisk, jeśli możesz to rzuć okiem i oceń, które z poniższych
sprawia dobre wrażenie:

http://www.codeblocks.org/features
http://sourceforge.net/projects/orwelldevcpp/
http://www.bloodshed.net/dev/

Dzięki

[M.M.]

On Saturday, September 19, 2015 at 3:08:04 PM UTC+2, szemrany wrote:
> On Sat, 19 Sep 2015 05:50:02 -0700 (PDT), M.M. wrote:
>
> > qtcreator?
>
> Pogooglałem i qtCreator jest ponoć wielki i ciężki, ale jest kilka
> lżejszych środowisk, jeśli możesz to rzuć okiem i oceń, które z poniższych
> sprawia dobre wrażenie:
>
> http://www.codeblocks.org/features
> http://sourceforge.net/projects/orwelldevcpp/
> http://www.bloodshed.net/dev/
>

Przepraszam, nie mogę, mam za dużo własnej roboty.
Pozdrawiam

[szemrany]

On Sat, 19 Sep 2015 06:23:04 -0700 (PDT), M.M. wrote:

>> Pogooglałem i qtCreator jest ponoć wielki i ciężki, ale jest kilka
>> lżejszych środowisk, jeśli możesz to rzuć okiem i oceń, które z poniższych
>> sprawia dobre wrażenie:
>>
>> http://www.codeblocks.org/features
>> http://sourceforge.net/projects/orwelldevcpp/
>> http://www.bloodshed.net/dev/
>
> Przepraszam, nie mogę, mam za dużo własnej roboty.
> Pozdrawiam

Oki, no problem, może ktoś inny przeczyta features list i oceni.
Dzięki za udział w wątku i modyfikacje kodu Bartka.

[bartekltg]

On 19.09.2015 13:35, M.M. wrote:
> 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.

Przecież tablica była losowana, dlaczego miałaby być posorotwana?

random_device rd;
mt19937 gen(rd());
....
generate(tab.begin(), tab.end(), gen);

Przez każdym pojedyńczym pomiarem.

> 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

Napisać to w c++, nie C ;->

> 4) lepsze rozwiązanie if( zero )

No tak, zero to całkiem poprawna wartość inta;>
Dorzuć kilka zer do testowej tablicy, nie działa.

> Rzecz jasna, też nie wiem czy nic nie spartoliłem, macie kod do
> sprawdzenia:
> http://pastebin.com/uRAqi8iv
>
> Wyniki:

Nagmatwałeś troche z różną ilośćią zer;-)
po odgmatwaniu widać, że ręczna hashmapa jest kilkanaście(!)*
razy szybsze. No to śledztwo:

Tochę porównujemy jakbłka z gruszkami.
"
(unsigned int)(size/2*5+2);

cout<<"s2 "<<s2<<endl;

int *u = new int[s2];
"

OK, to ja też mogę wpisać:
iter stable_unique_1 ( iter first, iter last )
{
unordered_set<int> temp; //zbiór użytych
temp.rehash ( distance(first, last)*5/2+2 ); // alokuje wstępnie
nieco pamieci.

i wtedy nie musimy co chwila robić realokacji i rehashowania,
gotowa hashmapa jest 2.5 raza wolniejsza. I to jest spodziewany
wynik, bo tamta hashmapa rozwiązuje kolizje tworząc listę,
a Twoja stosuje sztuczkę z wartośćią specjalną . Jeśli informację
o zajętości będziesz trzymał w osobnej tablicy, różnica ciut spadnie.


samorobka
100 zajelo 3.4711e-05s
1000 zajelo 0.000145689s
10000 zajelo 0.000330489s
100000 zajelo 0.00406414s
1000000 zajelo 0.0826325s
10000000 zajelo 0.97905s

hashmapa budowana
10 zajelo 1.18089e-06s
100 zajelo 1.31643e-05s
1000 zajelo 0.000130519s
10000 zajelo 0.00139489s
100000 zajelo 0.0192994s
1000000 zajelo 0.233072s
10000000 zajelo 2.65135s

zbior budowany
10 zajelo 6.43753e-07s
100 zajelo 1.03399e-05s
1000 zajelo 0.000142441s
10000 zajelo 0.00209884s
100000 zajelo 0.0432259s
1000000 zajelo 0.777911s
10000000 zajelo 14.2428s

hashmapa usuwana
10 zajelo 1.90731e-06s
100 zajelo 1.9725e-05s
1000 zajelo 0.000195841s
10000 zajelo 0.00210182s
100000 zajelo 0.0296034s
1000000 zajelo 0.389643s
10000000 zajelo 4.44893s

sortowanie
10 zajelo 5.58256e-08s
100 zajelo 8.79121e-07s
1000 zajelo 1.12299e-05s
10000 zajelo 0.000183867s
100000 zajelo 0.00352831s
1000000 zajelo 0.0571969s
10000000 zajelo 0.732117s

sortowanie stab
10 zajelo 2.3127e-07s
100 zajelo 4.69011e-06s
1000 zajelo 8.10539e-05s
10000 zajelo 0.00110062s
100000 zajelo 0.0153352s
1000000 zajelo 0.256625s
10000000 zajelo 5.16851s



*) Domyślnie unordered set ma load_factor 1!
Po zmianie go na przyzwoitszy:
temp.max_load_factor(2.0/5.0);
czas spadł do 4.5 sekund z hakiem. Z grubsza 2 razy więcej
niż z przygotowaną tablicą (tyle się należy spodziewać).
Wiekszosć zwolnienia poprzednio było więc z podowu dużej
liczby kolizji.


pzdr
bartekltg

[bartekltg]

On 19.09.2015 14:50, M.M. wrote:
> On Saturday, September 19, 2015 at 2:43:47 PM UTC+2, szemrany wrote:
>> W jakim kompilatorze to kompilujecie?
> Chyba dowolny C++11
>
>
>> Czy to zgodne z MS VS C++?
> Chyba tak.
>
>
>> A jest może jakieś proste IDE dla Windows, żeby można pod debugerem to
>> odpalić i krokowo "zbadać"?
> Może qtcreator?

+1

>
>
>
>> Pytanie drugie:
>> return ( (xx*67523u + 31237u) ^ (xx*78529u + 96285u) ) % s2;
>>
>> Skąd akurat takie wartości w hashu? To wynika z jakichś matematycznych
>> założeń czy statystycznie wyliczone?
> Wpisałem na oko :)

I dzieki temu wyniki sa parzyste ;-)

pzdr
barteklt

[bartekltg]

On 19.09.2015 15:08, szemrany wrote:
> On Sat, 19 Sep 2015 05:50:02 -0700 (PDT), M.M. wrote:
>
>> qtcreator?
>
> Pogooglałem i qtCreator jest ponoć wielki i ciężki, ale jest kilka

Lżejszy niż VS:)

Na razie chcesz tylko użyć kompilatora, nie ich środowiska
graficznego (new project-> non-QT project-> plain c++ project).

Jeśli coś się nie kompiluje, trzeba dodać do pliku *.pro linijkę

QMAKE_CXXFLAGS += -std=c++11

> lżejszych środowisk, jeśli możesz to rzuć okiem i oceń, które z poniższych
> sprawia dobre wrażenie:
>
> http://www.codeblocks.org/features

Podobno niezły.

> http://sourceforge.net/projects/orwelldevcpp/

Lata temu używałem (zanim zdechło a potem się odrodziło).

> http://www.bloodshed.net/dev/

Pierwsze słyszę.

pzdr
bartekltg

[M.M.]

On Saturday, September 19, 2015 at 6:10:59 PM UTC+2, bartekltg wrote:
> Przecież tablica była losowana, dlaczego miałaby być posorotwana?
>
> random_device rd;
> mt19937 gen(rd());
> ....
> generate(tab.begin(), tab.end(), gen);
>
> Przez każdym pojedyńczym pomiarem.

Tutaj miałem te obawy:
for (int i=0; i<100000/size+1;i++)
tab.erase( f( tab.begin(),tab.end() ), tab.end() );

> > 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
>
>
> Napisać to w c++, nie C ;->

Etam :)

> > 4) lepsze rozwiązanie if( zero )
>
> No tak, zero to całkiem poprawna wartość inta;>
> Dorzuć kilka zer do testowej tablicy, nie działa.

To się gdzieś rypłem, ale na wydajność to zbytnio nie
wpływa.

> Nagmatwałeś troche z różną ilośćią zer;-)

Był błąd, powinno być tak:
for( int i=0 ; i<size ; i++ ) {
if( t[i] != 0 ) {
if( ! exist_mm( t[i] , u , s2) )
t[size2++] = t[i];
} else if( !zero ) {
t[size2++] = 0;
zero = true;

}
}



> po odgmatwaniu widać, że ręczna hashmapa jest kilkanaście(!)*
> razy szybsze. No to śledztwo:
>
> Tochę porównujemy jakbłka z gruszkami.

No ale jaka wygoda w programowaniu :D

> OK, to ja też mogę wpisać:
> iter stable_unique_1 ( iter first, iter last )
> {
> unordered_set<int> temp; //zbiór użytych
> temp.rehash ( distance(first, last)*5/2+2 ); // alokuje wstępnie
> nieco pamieci.
>
> i wtedy nie musimy co chwila robić realokacji i rehashowania,
> gotowa hashmapa jest 2.5 raza wolniejsza. I to jest spodziewany
> wynik,

Hmmm ja bym się spodziewał się max 1.5 raza.

> bo tamta hashmapa rozwiązuje kolizje tworząc listę,
> a Twoja stosuje sztuczkę z wartośćią specjalną . Jeśli informację
> o zajętości będziesz trzymał w osobnej tablicy, różnica ciut spadnie.

Nie wiem co jest bardziej kosztowne. Ciągły if(zero), czy dodatkowa
tablica bitów. Z tablicą bitów, w przypadku mocno zapełnionej
tablicy, można przeskoczyć 64 zapełnienia w jednym ifie.

U mnie samoróbka (po zmianie funkcji hash i poprawieniu zer) działa
około 3 razy szybciej niż sortowanie i uniq.

http://pastebin.com/bEat8KH2

samorobka
poprawność:
12 457 0 1 56 89 11 55
100 zajelo 2.794e-06s
1000 zajelo 1.986e-05s
10000 zajelo 0.000210824s
100000 zajelo 0.00289853s
1000000 zajelo 0.0475682s
10000000 zajelo 0.460168s
100000000 zajelo 4.75097s

hashmapa budowana
poprawność:
12 457 1 56 89 11 55

100 zajelo 2.5469e-05s
1000 zajelo 0.000191005s
10000 zajelo 0.00231907s
100000 zajelo 0.0382351s
1000000 zajelo 0.791762s
10000000 zajelo 9.07928s

zbior budowany
poprawność:
12 457 1 56 89 11 55

100 zajelo 2.4478e-05s
1000 zajelo 0.000254404s
10000 zajelo 0.00330699s
100000 zajelo 0.0680503s
1000000 zajelo 1.4365s
10000000 zajelo 23.5209s

hashmapa usuwana
poprawność:
12 457 1 56 89 11 55

100 zajelo 2.6489e-05s
1000 zajelo 0.000204336s
10000 zajelo 0.00230099s
100000 zajelo 0.0386139s
1000000 zajelo 0.687652s
10000000 zajelo 7.9165s

sortowanie
poprawność:
1 11 12 55 56 89 457

100 zajelo 6.077e-06s
1000 zajelo 5.4831e-05s
10000 zajelo 0.000708904s
100000 zajelo 0.00844671s
1000000 zajelo 0.100287s
10000000 zajelo 1.16515s
100000000 zajelo 13.3513s

sortowanie stab
poprawność:
12 457 1 56 89 11 55

100 zajelo 1.053e-05s
1000 zajelo 0.000133041s
10000 zajelo 0.00170499s
100000 zajelo 0.0232212s
1000000 zajelo 0.395624s
10000000 zajelo 7.17122s

> *) Domyślnie unordered set ma load_factor 1!
> Po zmianie go na przyzwoitszy:
> temp.max_load_factor(2.0/5.0);
> czas spadł do 4.5 sekund z hakiem. Z grubsza 2 razy więcej
> niż z przygotowaną tablicą (tyle się należy spodziewać).
> Wiekszosć zwolnienia poprzednio było więc z podowu dużej
> liczby kolizji.

Możne domyślnie ma też kiepską funkcje hash? QT ma bardzo
kiepską. std - nie wiem.

Pozdrawiam

[bartekltg]

On 19.09.2015 18:58, M.M. wrote:
> On Saturday, September 19, 2015 at 6:10:59 PM UTC+2, bartekltg wrote:
>> Przecież tablica była losowana, dlaczego miałaby być posorotwana?
>>
>> random_device rd;
>> mt19937 gen(rd());
>> ....
>> generate(tab.begin(), tab.end(), gen);
>>
>> Przez każdym pojedyńczym pomiarem.
> Tutaj miałem te obawy:
> for (int i=0; i<100000/size+1;i++)
> tab.erase( f( tab.begin(),tab.end() ), tab.end() );

Aj!
Racja.
Na szczęśćie dla wyników, na które patrzyłem, czyli najdłuższych,
i tak była jedna pętla, te wyniki wiec się nie znieniły.

>
>
>>> 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
>>
>>
>> Napisać to w c++, nie C ;->
> Etam :)
>
>
>>> 4) lepsze rozwiązanie if( zero )
>>
>> No tak, zero to całkiem poprawna wartość inta;>
>> Dorzuć kilka zer do testowej tablicy, nie działa.

> To się gdzieś rypłem, ale na wydajność to zbytnio nie
> wpływa.


>
>
>> Nagmatwałeś troche z różną ilośćią zer;-)
> Był błąd, powinno być tak:
> for( int i=0 ; i<size ; i++ ) {
> if( t[i] != 0 ) {
> if( ! exist_mm( t[i] , u , s2) )
> t[size2++] = t[i];
> } else if( !zero ) {
> t[size2++] = 0;
> zero = true;
> }
> }

Tak, teraz działą.

Hackerstwo ;-)
Ale ładne. TEraz tylko osobny kubełek dla zer i mamy
szybką hastablicę (bez usuwania).

>
>
>> po odgmatwaniu widać, że ręczna hashmapa jest kilkanaście(!)*
>> razy szybsze. No to śledztwo:
>>
>> Tochę porównujemy jakbłka z gruszkami.
> No ale jaka wygoda w programowaniu :D
>
>
>> OK, to ja też mogę wpisać:
>> iter stable_unique_1 ( iter first, iter last )
>> {
>> unordered_set<int> temp; //zbiór użytych
>> temp.rehash ( distance(first, last)*5/2+2 ); // alokuje wstępnie
>> nieco pamieci.
>>
>> i wtedy nie musimy co chwila robić realokacji i rehashowania,
>> gotowa hashmapa jest 2.5 raza wolniejsza. I to jest spodziewany
>> wynik,
> Hmmm ja bym się spodziewał się max 1.5 raza.

Pamiętaj, żę nie napisałeś ogolnej tablicy hashującej, tylko
uży≤eś jednej specyficznej wartości do oznaczenia pustego pola
w tablicy (i jakbyś tworzył pełną tablicę hashującą, miałbyś
osobny kubełek na zera) Zrobienie tego w ogolności (dla dowolnego typu)
jest dość trudne.
Nie masz usuwania z tablicy - dopisane w tej wersji byłoby
kosztowne.

Jak się buduje pałną talicę hashującą, aż takiej poprawy nie ma:
http://incise.org/hash-table-benchmarks.html

Googlowa jest neicałe 2 razy szybsza od unordered set.

I teraz pytanie, na ile użycie własnej konstrukcji opłaca się
w strosunku do gotowca. Przyszpieszenie ejst bardzo wyraźne, ale
musiałeś to napsiać i jeszczer błąd się wkradł.

>> bo tamta hashmapa rozwiązuje kolizje tworząc listę,
>> a Twoja stosuje sztuczkę z wartośćią specjalną . Jeśli informację
>> o zajętości będziesz trzymał w osobnej tablicy, różnica ciut spadnie.
> Nie wiem co jest bardziej kosztowne. Ciągły if(zero), czy dodatkowa
> tablica bitów. Z tablicą bitów, w przypadku mocno zapełnionej
> tablicy, można przeskoczyć 64 zapełnienia w jednym ifie.

W przypadku hashmapy bardzon ważne jest cache. Jak masz dwie tablice,
to masz dwa razy więcej dostępów.

> U mnie samoróbka (po zmianie funkcji hash i poprawieniu zer) działa
> około 3 razy szybciej niż sortowanie i uniq.

Bardzo ładny wynik.

>> *) Domyślnie unordered set ma load_factor 1!
>> Po zmianie go na przyzwoitszy:
>> temp.max_load_factor(2.0/5.0);
>> czas spadł do 4.5 sekund z hakiem. Z grubsza 2 razy więcej
>> niż z przygotowaną tablicą (tyle się należy spodziewać).
>> Wiekszosć zwolnienia poprzednio było więc z podowu dużej
>> liczby kolizji.
> Możne domyślnie ma też kiepską funkcje hash? QT ma bardzo
> kiepską. std - nie wiem.

Stadndard nie precyzuje, gcc implementuje... identyczność ;-)
Tu nie będzie miało to znaczenia, bo dane sa losowe.

pzdr
bartekltg

[slawek]

On Fri, 18 Sep 2015 15:15:32 +0200, bartekltg <bart...@gmail.com>
wrote:

> FORTRAN jest bardzo dobrym językiem, ale jednek też o dość wąskiej

Do 77 nie ma wsparcia dla strukturalnego programowania. Błędna
koncepcja I/O. Bardzo zły do przetwarzania tekstów.

[bartekltg]

On 19.09.2015 11:34, szemrany wrote:
> On Sat, 19 Sep 2015 03:08:27 +0200, bartekltg wrote:

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

10-15 lat temu był i stl, i boost.
;-)

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

Płatny kompilator. W momencie, gdy M$ wypuszcza darmowego visuala
z (pewnemi) prawami komercyjnymi. NIe wróżę im za dobrze.
CHoć z drugiej strony COBOL dalej funkcjonuje, bo pewne
rzeczy 'pisze sie od trzech pokolej w COBOLU' ;-)

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

Ja też sie na wstępnych latach studiów (wstep do programowania,
ASD) uczyłem na turbopascalu. Pewnie nadal jakiegoś freepascala używają.
BTW, freepescal też się rozwija i tworzy swoje kontenery, mozę
delphi je za jakiś czas zaadoptuje.

>>> 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-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.
>
> Hmm... czyli tego mógłbym użyć w algorytmie w którym wspominaliście o set?

Tak. Tak mi sie wydaje:
http://docwiki.embarcadero.com/Libraries/XE8/en/System.Contnrs.TIntegerBucketList

Nie jestem pewien, bo to jest ujnia nie dokumentacja :(

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

W c++ możesz pisać równie czytelnie jak w pascalu.
Tylko w c++ mozesz też pisać nieczytelnie, nawet bardzo nieczytelnie.

Ale to ta sama zasada co z używaniem niskopoziomowych kostrukcji,
to, że są dostępne, nie oznacza, zę zawsze powinno się z nich
korystać.

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

No jak nie masz porządnej dokumentacji, to musisz się męczyć;-)

> Choć rozumiem, że dla kogoś spoza
> świata Object Pascala kod może być trudniejszy do czytania, tak jak dla
> mnie potworki C++ :-P

Kod biblioteczny c++ jest ciężki do czytania. Bo używa się tam
ość skompilkowanyvch konstrukjic, by potem _używanie_ tych bibliotek
było łatwe.

Dokumentacja powinna wyglądać tak:
http://en.cppreference.com/w/cpp/container/unordered_map

Krótki opis co to jest, lista metod i pól, do każdej opis
co robi (jakie sa argumentry, co wypluwa) i przykład.

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

W c++ jest jezykiem wyskiego poziomu. IMHO jest tam więcej
wysokopoziomowych konstrukcji niż w Pascalu (generyczne, funkcyjne...).
Chyba mylisz c++ z c.
Tak, w C+ można dobrać się do bebechów, ale nie jest to normalny
sposób pisania.
To, że jezyk daje więcej możliwosćie najczęśćiej jest zaletą.
A, że programiści to często bałąganiarze, to ta zaleta czasem
wychodzi bokiem ;-)

.....

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

Poza najwyższym wynikiem czasy są nieco zepsute (kolejne odpalenia
szły dla tablicy z samymi unikatami). Porównanie algorytmów dla
tej samej liczby powtórzeń nadal ma sens*), ale porówanie różnych
do siebie może nieść pewien błąd.

testy dla 10000000 miały tylko jeedn obrót pętli i są OK.

*) można mieć wątpliwosći co do wersji z sortowaniem + unique,
bo wynik jest posortowany, ale gcc używa qsorte (introsorta dokładniej)
z medianą z trzech, a nie timsorta, więc posortowaną tablicę sortuje
się własciwie tak samo długo jak losową.


Jak będize mi sie chciało zrobić porządek, poprawie kod i wyniki.


pzdr
bartekltg

[bartekltg]

W 77 to już chyba nawet fizycy*) nie piszą ;-)

Do przetwarzania tesktów to i c++ się średnio nadaje (chociaż
gdzieśtam rope siedzi, regexpy są, ale nadal...)


*) Anegdota. Znajoma liczy jakieś kwanty z dużą precyzją.
"odziedziczyła" spory kod fortranowy. W tym była biblioteka
do liczb wysokiej precyzji (poczwórna i większe).
Parę lat w tym pracowała, ale w końcu postanowili powoli
przenieść się na c++. Zachęcani m.in zdanaimi jak
'będzie mniej babrania się' czyt "nawet jak będzie dwa razy
wolniej, to dasz radę napisać subtelniejszy algorytm".

Jako wersja próbna parę podstawowych klocków zostało napsianych
z użyciem mpfr (bardzo niewydajen pamięciowo jak chce się
tylko 4 cxzy 8 krotną precyzję) i eigen (bo trzeba jakoś
tabelkę tem mpfrów traktować jak macierz).

I wszyscy byli zaskoczeni, jak ta wersja liczyła grube
kilka razy szybciej. FORTRAN bardzo szybki jest, ale
bibliotekę wysokiej precyzji ktoś schrzanił.

Nie byłoby w tym nic złego, w końcu wszędzie zdarzają się
źle napisane rzeczy, to nie wina języka, ale dłużej
trzymali się FORTRANa 'bo ten jest szybszy do numeryki'.


pzdr
bartekltg

[slawek]

On Sat, 19 Sep 2015 21:01:16 +0200, bartekltg <bart...@gmail.com>
wrote:

> W 77 to już chyba nawet fizycy*) nie piszą ;-)

Piszą.

> trzymali się FORTRANa 'bo ten jest szybszy do numeryki'.

Jest szybszy ale programy wolniej działają. Tzn. C nadrabia
zarządzaniem pamięcią itp., więc przewaga w ewaluacji wyrażeń
arytmetycznych Fortranu jest marnowana.

Nota bene brak hardwareowego wsparcia dla poczwórnej precyzji to
trochę dziwne.

[bartekltg]

On 20.09.2015 16:27, slawek wrote:
> On Sat, 19 Sep 2015 21:01:16 +0200, bartekltg <bart...@gmail.com> wrote:
>> W 77 to już chyba nawet fizycy*) nie piszą ;-)
>
>
> Piszą.

Eee, większość dogrzebała się conajmniej do 95;-)

>
>> trzymali się FORTRANa 'bo ten jest szybszy do numeryki'.
>
> Jest szybszy ale programy wolniej działają. Tzn. C nadrabia zarządzaniem
> pamięcią itp., więc przewaga w ewaluacji wyrażeń arytmetycznych Fortranu
> jest marnowana.
> Nota bene brak hardwareowego wsparcia dla poczwórnej precyzji to trochę
> dziwne.

Dawno temu obiecywali na... 2015 ;-) W kompilatorach interfejs się
pojawia, __float128 w gcc, _Quad w intelu. Ale tych kilku doadtkowych
rozkazów w SSE nadal nie ma:(

Jako zamiennik poziom wyżej można użyć sztuczek z dodawaniem
dwóch lub 4 doubli.
http://crd-legacy.lbl.gov/~dhbailey/mpdist/
biblioteczka QD.
ośmokrotna precyzje (quad double) ma już jednek bardzo podobną
wydajnośc jak mpfr z odpowiednią liczbą bitów (choć nadal używa
znacznie mniej pamięci, ta sama wydajnosć, czyli koszmarnie wolno
w porównaniu do double).
Jej działenie opiera się na założeniach o zaokrąglaniu
liczb zmiennoprzecinkowych (dodawanych i odejmowanych w odpowenidniej
kolejności), więc np -ffast-math psuje jej działania.

pzdr
bartekltg

[Tomasz Kaczanowski]

W dniu 2015-09-19 18:20, bartekltg pisze:
>> http://www.bloodshed.net/dev/
>
> Pierwsze słyszę.

to devc++ - wersja bardzo leciwa, wiem, że gdzieś jest jakis fork -
trochę uaktualniony.

--
Kaczus
http://kaczus.ppa.pl

[M.M.]

On Saturday, September 19, 2015 at 8:44:44 PM UTC+2, bartekltg wrote:
> Aj!
> Racja.
> Na szczęśćie dla wyników, na które patrzyłem, czyli najdłuższych,
> i tak była jedna pętla, te wyniki wiec się nie znieniły.

Tak

> >> Nagmatwałeś troche z różną ilośćią zer;-)
> > Był błąd, powinno być tak:
> > for( int i=0 ; i<size ; i++ ) {
> > if( t[i] != 0 ) {
> > if( ! exist_mm( t[i] , u , s2) )
> > t[size2++] = t[i];
> > } else if( !zero ) {
> > t[size2++] = 0;
> > zero = true;
> > }
> > }
>
> Tak, teraz działą.
>
> Hackerstwo ;-)
> Ale ładne.

Dziękuję :)

> TEraz tylko osobny kubełek dla zer i mamy
> szybką hastablicę (bez usuwania).

To jest tylko głupia hash-table, a ile można usprawnień i wersji
zaimplementować. Do konkretnych danych można lepiej funkcję hash
dopasować. Do losowych faktycznie nie ma sensu. Można wyzbyć się
operacji modulo, na rzecz bitowego and. Można testować na 64
pozycje w przód w jednym ifie lub jednej pętli.

> >> i wtedy nie musimy co chwila robić realokacji i rehashowania,
> >> gotowa hashmapa jest 2.5 raza wolniejsza. I to jest spodziewany
> >> wynik,
> > Hmmm ja bym się spodziewał się max 1.5 raza.
>
> Pamiętaj, żę nie napisałeś ogolnej tablicy hashującej,

Mimo to powinno być 1.5 raza. Nie mam czasu na zabawę, ale
coś czuję, żebym napisał ogólną ze współczynnikiem 1.5.

> tylko
> uży≤eś jednej specyficznej wartości do oznaczenia pustego pola
> w tablicy (i jakbyś tworzył pełną tablicę hashującą, miałbyś
> osobny kubełek na zera) Zrobienie tego w ogolności (dla dowolnego typu)
> jest dość trudne.
> Nie masz usuwania z tablicy - dopisane w tej wersji byłoby
> kosztowne.

Jest jeszcze jedna sztuczka, czasami się opłaca. Zamiast kubełka na
wartość zero, robi się tablicę bitów z info o zajętych pozycjach.
W trakcie dodawania, zliczasz ile maksymalnie było przeskoczonych
zapełnionych pozycji. Potem, w trakcie usuwania i wyszukiwania, tyle
samo wykonujesz iteracji. Ilość iteracji może wzrosnąć do
dużej wartości przy złym rozproszeniu i małym zapełnieniu. Ale można
takich wartości zapamiętać wiele, np. jedna dla każdych 1-10tys
entry point w hash-table... niby to tylko głupia hash-table ;-)

> Jak się buduje pałną talicę hashującą, aż takiej poprawy nie ma:
> http://incise.org/hash-table-benchmarks.html
>
> Googlowa jest neicałe 2 razy szybsza od unordered set.
>
> I teraz pytanie, na ile użycie własnej konstrukcji opłaca się
> w strosunku do gotowca. Przyszpieszenie ejst bardzo wyraźne, ale
> musiałeś to napsiać i jeszczer błąd się wkradł.

Cóż, albo bierzemy gotowca, albo rzeźbimy sami, narażając się na
błędy i stratę czasu. Każdy wyboru musi dokonać sam.

> >> bo tamta hashmapa rozwiązuje kolizje tworząc listę,
> >> a Twoja stosuje sztuczkę z wartośćią specjalną . Jeśli informację
> >> o zajętości będziesz trzymał w osobnej tablicy, różnica ciut spadnie.
> > Nie wiem co jest bardziej kosztowne. Ciągły if(zero), czy dodatkowa
> > tablica bitów. Z tablicą bitów, w przypadku mocno zapełnionej
> > tablicy, można przeskoczyć 64 zapełnienia w jednym ifie.
>
> W przypadku hashmapy bardzon ważne jest cache. Jak masz dwie tablice,
> to masz dwa razy więcej dostępów.

Teoretycznie tak, ponieważ są dwa strzały w losowe miejsce RAM. Jednak z
tego co pamiętam z pomiarów własnych, to nie spowalniało wyraźnie.

> Stadndard nie precyzuje, gcc implementuje... identyczność ;-)
> Tu nie będzie miało to znaczenia, bo dane sa losowe.

Racja.

Pozdrawiam