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

do góry

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.

do góry

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

do góry

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

do góry

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

do góry

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?

do góry