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

do góry

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.

do góry

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

do góry

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?

do góry

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

do góry

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

do góry

> Dlaczego nie jakies hashowanie ?


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

do góry

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

do góry

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

do góry

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

Ale byyyyk :(. Przepraszam bardzo. szewc

do góry