-
X-Received: by 10.31.142.14 with SMTP id q14mr731vkd.19.1503397379593; Tue, 22 Aug
2017 03:22:59 -0700 (PDT)
X-Received: by 10.31.142.14 with SMTP id q14mr731vkd.19.1503397379593; Tue, 22 Aug
2017 03:22:59 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.unit
0.net!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.
iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!border2.nntp.dca1.giganew
s.com!nntp.giganews.com!e2no1522009qta.1!news-out.google.com!i9ni49312qte.0!nnt
p.google.com!e2no1522006qta.1!postnews.google.com!glegroupsg2000goo.googlegroup
s.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Tue, 22 Aug 2017 03:22:59 -0700 (PDT)
In-Reply-To: <d...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=89.70.120.200;
posting-account=CvUQzQoAAABvVQmR58QmR6N4Cev1qhAS
NNTP-Posting-Host: 89.70.120.200
References: <1...@g...com>
<5...@g...com>
<d...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f...@g...com>
Subject: Re: Drzewa AA
From: bartekltg <b...@g...com>
Injection-Date: Tue, 22 Aug 2017 10:22:59 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 129
Xref: news-archive.icm.edu.pl pl.comp.programming:211226
[ ukryj nagłówki ]On Tuesday, August 22, 2017 at 12:27:45 AM UTC+2, M.M. wrote:
> 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.
> ]
I jest jeszcze to, że RB mają mniejszy rozrzut czasów.
Nieraz też to jest istotne.
> 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.
Miałem o tym pisać jak wróce do wątku z implementacją RB, ale
tu też będzie dobrze. Nie, to sortowanie to dość mało
przydatna rzecz;-)
Jeśli mam serię wstaweń (i ewentialnie usuwań) a potem wyszukiwania
to wstawiam w nieposortowany vector, potem go sortuję (jeśli coś
usuwam to do osobnej listy, sortuję, a potem std::set_difference)
i teraz wyszukuję na posortowanym wektorze.
Wstawianie mam liniowo (i znacznie szybciej niż Ty), sortowanie
też nieco szybciej.
Jeśli mówię, że drzewo będzie używane z przewagę wstawień/usunieć,
albo wyszukiwań, to znaczy, że np 5 jednych będzie przeplatane tym drugim,
nie, że wystąpią one po kolei.
Uporządkowanie tych działań to bardzo spacyficzne zastosowanie,
i, jak widać powyzej, da sie je zrobić nawet szybciej.
A tu dyskutujemy o uniwersalnych drzewkach.
> 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.
Jeśli masz miliardy elementów - niekoniecznie;-)
A jeśli Ci się opłaca sortować po wstawieniu jednego elementu,
to tym bardziej opłaca Ci się... wstawić liniowo element do posortowanego
ciagu.
Chyba dokładnie to robi flat_set z boosta. Wyszukujesz właściwe miejsce,
wstawiasz tam nowy element, a wszytkie kolejne przesuwasz o oczko w prawo.
Wstawienie jest O(n), ale szybkie (tylko raz dotykasz pamieci, i to średnio
tylko połowy), w porównaniu do Twojego, gdzie efektywnie masz wstawienie
o koszcie O(n log n).
> Wrzuciłem na bloga ulepszony program do przetestowania:
> https://drzewa-czerwono-czarne.blogspot.ch/p/kod-zro
dowy-programu-testujacego.html
Widziałem, nadal nie mam kiedy czytac.
> 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
pzdr
bartekltg
Następne wpisy z tego wątku
- 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
- 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
- Ada-Europe Conference - 6 March Extended Final Deadline
Najnowsze wątki
- 2024-04-19 Wrocław => Lider Serwisu/Programista PLC z językiem niemieckim <=
- 2024-04-19 uczcie się Anglicy
- 2024-04-19 Co sciaga kretynow
- 2024-04-19 Uziom
- 2024-04-18 Prokurator Wrzosek jest już w porządku [Bodnatura po-praworządności]
- 2024-04-18 Warszawa => Sprzedawca usług rekrutacyjnych <=
- 2024-04-18 Jak uszkodzona sonda lambda wpływa na dawkowanie paliwa?
- 2024-04-18 Warszawa => Spedytor międzynarodowy <=
- 2024-04-18 Warszawa => International freight forwarder <=
- 2024-04-18 Warszawa => Regular Data Analytics/SQL Specialist <=
- 2024-04-18 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-04-18 (U)EFI - ksiązka, dokument
- 2024-04-18 Wrocław => Dyrektor Handlowy (branża usług/produktów IT) <=
- 2024-04-18 (Ponownie) odkryto, że ładowanie pulsacyjne robi dobrze
- 2024-04-18 Warszawa => Inżynier DevOps (Kubernetes, AWS) <=