🚀 go-pugleaf

On Tuesday, December 11, 2018 at 12:48:05 AM UTC+1, DMR wrote:
> Mam w tablicy dane (kilkadziesiąt tysięcy elementów).
> Jako, że będę z nich gęsto wyszukiwał, to wykombinowałem sobie, że wczytam je teraz do drzewa (takiego quasi-drzewa, ze stablicowanymi węzłami, no i oczywiście same wskaźniki), w "bisekcyjny" sposób.
> Jeśli dane będą uporządkowane, to tym lepiej - drzewo wyjdzie idealnie wyważone.

Dlaczego po prostu ich nie posortujesz? Przecież kilkadziesiąt tysięcy
elementów to jest nic. I wtedy możesz użyć wyszukiwania binarnego na
zwykłej tablicy.

w.

> Dlaczego po prostu ich nie posortujesz?


Bo ja starej daty jestem... :-)
Kilkadziesiąt tysięcy elementów, to jest... Ho, ho! ;-)

A poza tym, to tak na chłopski rozum, można posortować dane w czasie "kwadratowym" - ale wtedy nie odbiega to zbytnio od idei wyszukiwania liniowego, więc w ogóle nie ma sensu, albo w czasie "logarytmicznym" - ale wtedy trzeba kombinować z kopcami, albo rekurencją, więc też nie ma to żadnego sensu, bo zasadniczym celem nie jest posortowanie zbioru danych, tylko szybkie w nim wyszukiwanie, a wtedy lepiej poświęcić ten sam koszt na zbudowanie struktury do tego specjalizowanej.

Wydaje mi się, że mój problem polega na próbie zlekceważenia twórców wspomnianych algorytmów - nie bez powodów są one takie jakie są, a coś, co daje z pozoru porównywalne rezultaty, a na pierwszy rzut oka wydaje się o wiele prostsze, finalnie wcale nie musi takie być.



Pzdr.

W dniu 11.12.2018 o 12:20, DMR pisze:
> A poza tym, to tak na chłopski rozum, można posortować dane w czasie "kwadratowym" - ale wtedy nie odbiega to zbytnio od idei wyszukiwania liniowego, więc w ogóle nie ma sensu, albo w czasie "logarytmicznym" - ale 

Co łatwiejsze: użyć QSort wbudowaną procedurą czy używać specjalnie 
drzew czerowno-czarnych czy AVL?

Życie, to w ogóle nie jest łatwe. Trudne jest. :-)

Jeszcze łatwiejsze może być zassanie danych do Excela i przemielenie, ale trudniejsze może być potem zasypianie z wątpliwościami, czy rozwiązanie problemu zepchnąłeś na i7 z odpowiednio pojemnym "kejszem", czy też wziąłeś temat na klatę, nabywając przy okazji fajowego skilla (bo niby - czemu nie?)

On 2018-12-11 12:20, DMR wrote:
>> Dlaczego po prostu ich nie posortujesz?
> 
> 
> Bo ja starej daty jestem... :-)
> Kilkadziesiąt tysięcy elementów, to jest... Ho, ho! ;-)

...a po co od razu drzewa? Dlaczego nie jakies hashowanie ?
Liniowe toto i w przypadku gdy elementy rzadko sie powtarzaja
moze byc wcale szybkie/wydajne?

AK

> Dlaczego nie jakies hashowanie ?


Wykombinowanie dobrej funkcji, kolizje, kupa danych... Nie wiem, czy to ogarnę.
Ale zgłębiam temat. Bo niby - czemu nie? ;-)

On 2018-12-11 14:48, AK wrote:
> Liniowe toto
Poprawka: Oczywiscie przy tworzeniu hashy.
Przy szukaniu to liniowe w skrajnym przypadku,
lub nawet bezposrednie - w drugim skrajnym (perfect hash).

AK

On 2018-12-11 19:35, DMR wrote:
>> Dlaczego nie jakies hashowanie ?
> 
> 
> Wykombinowanie dobrej funkcji, kolizje, kupa danych... Nie wiem, czy to ogarnę.
> Ale zgłębiam temat. Bo niby - czemu nie? ;-)
> 

...a nie lepiej uzyc cus gotowego/sprawdzonego ?
Np takie cos w Pythonie (na dosc slabym kompie-szefc bez butow chodzi:)
dla 10 000 000 'rekordow':

import timeit

dictionary = { key: str(key).zfill(6) for key in range(10000000) }
print(timeit.timeit('temp = { key: str(key).zfill(6) for key in 
range(10000000) }', number=1))

print(dictionary[9999999], timeit.timeit('dictionary[9999999]', 
number=10000, globals=globals()) / 10000)
print(dictionary[1],       timeit.timeit('dictionary[1]', 
number=10000, globals=globals()) / 10000)
print(dictionary[5000009], timeit.timeit('dictionary[5000009]', 
number=10000, globals=globals()) / 10000)
print(dictionary[100000],  timeit.timeit('dictionary[100000]', 
number=10000, globals=globals()) / 10000)

daje takie czasy:
D:\>py zzz.py
5.356959160756147
9999999 7.252555713392894e-08
000001 5.5035608509168556e-08
5000009 7.855509932497284e-08
100000 8.065047214307341e-08

i to dla teoretycznie dosc slabych hashy, bo dla liczb naturalnych.
Oczywiscie szybkosc hashowania liniowa wzgledem rozmiaru,
a szybkosc szukania praktycznie niezalezna od rozmiaru.

PS: Oczywiscie to klasyczny dict/set (czyli klucz jest unikalny)
Istnieja oczywiscie: multidict i multiset, choc w Py niestandardowo.
W/w ma glownie obrazowac ze kilkadziesiat tysiecy to dzis raczej
"pryszcz" dla klasycznych/gotowych rzeczy.

AK

On 2018-12-11 20:25, AK wrote:
> (na dosc slabym kompie-szefc bez butow chodzi:)

Ale byyyyk :(. Przepraszam bardzo. szewc

Pythona, to ja... Wiem, że coś takiego jest. :-)



> Dlaczego nie jakies hashowanie ? 


Postudiowałem temat, bardzo fajna sprawa jeśli klucze występują według... klucza. :-)

A skoro o tym mowa, to wyszła zmiana założeń.
Klucze mają być jednak 120-bitowe (16 znakowe stringi, zera nie liczę).


Czyli teraz muszę zrobić:

A -> B -> A -> CKI
A -> B -> A -> DROWICZ
A -> B -> A -> FIUK

B -> A -> BACKI
B -> A -> CEWICZ
B -> E -> CIKOWSKI

itd.

Czyli skorowidz. :-)

Biorąc pod uwagę to, że do stworzenia klucza dozwolone będzie użycie niecałej setki znaków, nawet jeśli kolejne znaki-klucze wrzucę na zwykłe listy, to w najbardziej perfidnym przypadku dotarcie do właściwego klucza będzie wymagało co najwyżej 15*100 porównań - przy czym przypadek taki NIGDY nie nastąpi, z uwagi na ilość elementów znikomą w porównaniu z liczbą możliwych kombinacji znaków w kluczu.

Ale na pewno da się coś tu poprawić... Drzewo drzew? ;-]

On Wednesday, December 12, 2018 at 2:27:12 PM UTC+1, DMR wrote:
> Pythona, to ja... Wiem, że coś takiego jest. :-)
> 
> 
> 
> > Dlaczego nie jakies hashowanie ? 
> 
> 
> Postudiowałem temat, bardzo fajna sprawa jeśli klucze występują według... klucza. :-)
> 
> A skoro o tym mowa, to wyszła zmiana założeń.
> Klucze mają być jednak 120-bitowe (16 znakowe stringi, zera nie liczę).
> 
> 
> Czyli teraz muszę zrobić:
> 
> A -> B -> A -> CKI
> A -> B -> A -> DROWICZ
> A -> B -> A -> FIUK
> 
> B -> A -> BACKI
> B -> A -> CEWICZ
> B -> E -> CIKOWSKI
> 
> itd.
> 
> Czyli skorowidz. :-)
> 
> Biorąc pod uwagę to, że do stworzenia klucza dozwolone będzie użycie niecałej setki znaków, nawet jeśli kolejne znaki-klucze wrzucę na zwykłe listy, to w najbardziej perfidnym przypadku dotarcie do właściwego klucza będzie wymagało co najwyżej 15*100 porównań - przy czym przypadek taki NIGDY nie nastąpi, z uwagi na ilość elementów znikomą w porównaniu z liczbą możliwych kombinacji znaków w kluczu.
> 
> Ale na pewno da się coś tu poprawić... Drzewo drzew? ;-]

W jakim języku masz to napisać?

w.

> W jakim języku masz to napisać?

C/C++

Ale nie o język tu chodzi, tylko o podejście do problemu.
Takie w sumie szkolne. :-)

Program już dawno działa, teraz próbuję się bez spiny czegoś mądrego nauczyć.
Np. okazało się, że w poprzednim wpisie odkryłem drzewa trie, nawet takie wybajerzone, z listami wskaźników w postaci drzew... ;-)

> ...a po co od razu drzewa? Dlaczego nie jakies hashowanie ?


No, ktoś ma tu browara! :-)

Postudiowałem, przespałem się z tematem i jest!
Pierwszym krokiem do uniknięcia kolizji jest zadbanie o unikalność klucza każdego elementu.
Jako że identyfikatorem ma być łańcuch 15 z dozwolonych 63 znaków, to najłatwiej potraktować go jako zapis liczby w systemie "63-kowym" i przeliczyć na dziesiętny.
Daje to zakres 63^15 = ~10^27... Trochę dużo, nawet, jak na 64 bity. :-)
Żeby się wstrzelić w zakres 32 bitowego int-a można zrobić co najwyżej 63^5...

No i się wszystko zgadza - można przecież przeliczać piątkami. :-)
Da to co najwyżej jedną bardzo teoretyczną kolizje z samego identyfikatora (dobrze kombinuję?)

A dalej, to już klasyka gatunku - indeks leci jako modulo z rozmiaru tablicy haszującej (daję ~2x większą, przy kilkudziesięciu tysiącach elementów nie wylazło mi nigdy więcej niż 5 powtórzeń na ~10% kluczy), do szybkiego odcedzenia w kolizji używam identyfikatora.

No i gra! :-)


Dzięki!

> przy kilkudziesięciu tysiącach elementów nie wylazło mi nigdy więcej
> niż 5 powtórzeń na ~10% kluczy


Na ~1% kluczy, pardon.

Bloga se chyba założę, tylko brakuje sweet-foci z dziubkiem...... ;-)

On 12/14/18 9:28 AM, DMR wrote:
> Jako że identyfikatorem ma być łańcuch 15 z dozwolonych 63 znaków, to najłatwiej potraktować go jako zapis liczby w systemie "63-kowym" i przeliczyć na dziesiętny.
> Daje to zakres 63^15 = ~10^27... Trochę dużo, nawet, jak na 64 bity. :-)
> Żeby się wstrzelić w zakres 32 bitowego int-a można zrobić co najwyżej 63^5...

Nie lepiej dodać jeden znak dozwolony i mieć system 64-kowy?