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

do góry

On Fri, 18 Sep 2015 15:15:32 +0200, bartekltg <b...@g...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.

do góry

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

Tak. Tak mi sie wydaje:
http://docwiki.embarcadero.com/Libraries/XE8/en/Syst
em.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

do góry

On 19.09.2015 20:45, slawek wrote:
> On Fri, 18 Sep 2015 15:15:32 +0200, bartekltg <b...@g...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.

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

do góry

On Sat, 19 Sep 2015 21:01:16 +0200, bartekltg <b...@g...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.

do góry

On 20.09.2015 16:27, slawek wrote:
> On Sat, 19 Sep 2015 21:01:16 +0200, bartekltg <b...@g...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

do góry

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

do góry

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

do góry