Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #32099 > unrolled thread

Bisekcja...

Back to article view | Back to pl.comp.programming

Contents

  Bisekcja... DMR <mezzogm@gmail.com> - 2018-12-10 15:48 -0800
    Re: Bisekcja... Wojciech Muła <wojtek.mula@gmail.com> - 2018-12-11 00:51 -0800
      Re: Bisekcja... DMR <mezzogm@gmail.com> - 2018-12-11 03:20 -0800
        Re: Bisekcja... Borneq <borneq@antyspam.hidden.pl> - 2018-12-11 13:40 +0100
          Re: Bisekcja... DMR <mezzogm@gmail.com> - 2018-12-11 05:33 -0800
        Re: Bisekcja... AK <nobody@nowhere.net> - 2018-12-11 14:48 +0100
          Re: Bisekcja... DMR <mezzogm@gmail.com> - 2018-12-11 10:35 -0800
            Re: Bisekcja... AK <nobody@nowhere.net> - 2018-12-11 20:25 +0100
              Re: Bisekcja... AK <nobody@nowhere.net> - 2018-12-11 20:35 +0100
                Re: Bisekcja... DMR <mezzogm@gmail.com> - 2018-12-12 05:27 -0800
                  Re: Bisekcja... Wojciech Muła <wojtek.mula@gmail.com> - 2018-12-12 11:53 -0800
                    Re: Bisekcja... DMR <mezzogm@gmail.com> - 2018-12-12 14:46 -0800
          Re: Bisekcja... AK <nobody@nowhere.net> - 2018-12-11 19:35 +0100
          Re: Bisekcja... DMR <mezzogm@gmail.com> - 2018-12-14 00:28 -0800
            Re: Bisekcja... DMR <mezzogm@gmail.com> - 2018-12-14 00:37 -0800
            Re: Bisekcja... Borneq <borneq@antyspam.hidden.pl> - 2019-08-09 09:27 +0200

#32099 — Bisekcja...

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.
A jeśli nie będą, to... Nie wiem, co by się musiało stać, żeby drzewo się jakoś specjalnie zdegradowało. :-)
Szybkie testy pokazały, że drzewo wczytane z losowo ułożonych danych wychodzi wyższe około ~2.5 raza od "logarytmicznego", więc wynalazki typu drzewa czerwono-czarne, czy AVL (na razie) sobie odpuściłem.

Dumny ze swojego rozumu postanowiłem wprowadzić światłą ideę w czyn i... Zupa! Utknąłem.
Jak "kulturalnie" wyznaczyć kolejność indeksów?
Trochę nie bardzo widzi mi się puścić to w rekurencję...

[toc] | [next] | [standalone]

#32100

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.

[toc] | [prev] | [next] | [standalone]

#32101

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

[toc] | [prev] | [next] | [standalone]

#32102

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?

[toc] | [prev] | [next] | [standalone]

#32103

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

[toc] | [prev] | [next] | [standalone]

#32104

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

[toc] | [prev] | [next] | [standalone]

#32105

> Dlaczego nie jakies hashowanie ?


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

[toc] | [prev] | [next] | [standalone]

#32107

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

[toc] | [prev] | [next] | [standalone]

#32108

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

Ale byyyyk :(. Przepraszam bardzo. szewc

[toc] | [prev] | [next] | [standalone]

#32115

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

[toc] | [prev] | [next] | [standalone]

#32117

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.

[toc] | [prev] | [next] | [standalone]

#32118

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

[toc] | [prev] | [next] | [standalone]

#32106

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

[toc] | [prev] | [next] | [standalone]

#32120

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

[toc] | [prev] | [next] | [standalone]

#32121

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

[toc] | [prev] | [next] | [standalone]

#32824

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?

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web