-
Data: 2017-08-22 00:27:44
Temat: Re: Drzewa AA
Od: "M.M." <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]On Monday, August 21, 2017 at 10:58:34 PM UTC+2, bartekltg wrote:
> On Monday, August 21, 2017 at 2:09:05 AM UTC+2, M.M. wrote:
> > Pierwszy raz się z czymś takim spotykam. Podobno są tak samo wydajne jak drzewa
czerwono czarne, ale są prostsze w implementacji.
> >
> > Cytat ze stacka:
> > [
> > An alternative to all these trees are AA-Trees. As this PDF paper suggests,
AA-Trees (which are in fact a sub-group of RB-Trees) are almost equal in performance
to normal RB-Trees, but they are much easier to implement than RB-Trees, AVL-Trees,
or B-Trees. Here is a full implementation, look how tiny it is (the main-function is
not part of the implementation and half of the implementation lines are actually
comments).
> > ]
>
>
> Zapomniałeś dać linka do źródła cytatu:>
>
> >
> > Prawda czy fałsz?
>
> Które są szybsze zależy od tego, co będziesz robił.
> https://stackoverflow.com/questions/22435912/red-bla
ck-trees-versus-andersson-trees
>
> pzdr
> bartekltg
Racja:
[
So there's a trade-off here: when comparisons are cheap but updates are frequent, a
red-black tree might outperform an AA tree; otherwise, when comparisons are expensive
but lookups are more frequent than updates, the AA tree might win.
]
Myślę jednak, że te różnice są niewielkie. Gdy jest naprawdę dużo
porównań, to jak już pisałem, można zaimplementować rb-tree na
tablicy i posortować w czasie O(N) przed długą serią wyszukiwań.
Gdy są dosłownie wyszukiwania (dosłownie, czyli nie ma lowerBound, ani
upperBound), to można też w czasie O(N) zbudować hash-table - ale
to wymaga dodatkowej pamięci.
Oczywiście jest jeszcze i taka możliwość, że w losowej chwili
robimy jedną modyfikację na 5-30 wyszukiwań. Gdy jest to 5, to
może lepsze będą rb-tree, gdy 30, to może AA-tree. Trudno
powiedzieć bez zmierzenia.
Chwilowo mam taką sytuację w której mogę przewidzieć, że po jednej
modyfikacji będą miliony wywołań lowerBound, więc rb-tree na tablicy z
sortowaniem wydaje się najlepsze. A w dodatku modyfikacja czasami
może nie zaburzać porządku drzewa, więc chyba już nic lepszego
nie znajdę - aczkolwiek trochę mi się zrobiło głupio, że można
podobny efekt do rb-tree uzyskać przy pomocy króciutkiego kodu :)
Pozdrawiam
P.S.
Wrzuciłem na bloga ulepszony program do przetestowania:
https://drzewa-czerwono-czarne.blogspot.ch/p/kod-zro
dowy-programu-testujacego.html
A także skrypt automatyzujący test:
https://drzewa-czerwono-czarne.blogspot.ch/p/skrypt-
do-wykonania-testu-implementacji.html
Kod drzewka pod starym adresem:
https://drzewa-czerwono-czarne.blogspot.ch/p/kod-zro
dowy-c-drzewa-czerwono-czarne.html
Następne wpisy z tego wątku
- 22.08.17 00:29 M.M.
- 22.08.17 12:22 bartekltg
- 22.08.17 14:43 M.M.
- 22.08.17 15:34 bartekltg
- 22.08.17 16:15 M.M.
- 22.08.17 16:39 bartekltg
- 22.08.17 20:19 M.M.
Najnowsze wątki z tej grupy
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
- Ideologia Polskiego Programisty wer.3
Najnowsze wątki
- 2024-04-27 Katowice => Administrator IT - Wirtualizacja i Konteneryzacja <=
- 2024-04-27 Bażanowice => Inżynier Industrializacji - Elektronik <=
- 2024-04-27 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-04-27 Zadaszenie tarasu, a wymagany spadek
- 2024-04-27 Warszawa => Senior Account Manager <=
- 2024-04-27 Wrocław => Head of Sales (IT services/products field) <=
- 2024-04-27 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-04-27 wymiana ekranu w laptopie
- 2024-04-27 DC blocker i buczące toroidy
- 2024-04-26 Warszawa => Kierownik Działu Spedycji Międzynarodowej <=
- 2024-04-26 Berlin => IT Network Engineer <=
- 2024-04-26 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-04-26 Warszawa => Senior PHP Developer (Symfony) <=
- 2024-04-26 Białystok => Business Development Manager - obszar bezpieczeństwa IT
- 2024-04-26 Bieruń => Administrator i wdrożeniowiec Lotus Notes/Domino <=