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

Prawda czy fałsz?

do góry

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

do góry

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

do góry

On Monday, August 21, 2017 at 10:58:34 PM UTC+2, bartekltg wrote:
> Zapomniałeś dać linka do źródła cytatu:>
Oż skleroza:
https://stackoverflow.com/questions/647537/b-tree-fa
ster-than-avl-or-redblack-tree

do góry

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

do góry

On Tuesday, August 22, 2017 at 12:23:00 PM UTC+2, bartekltg wrote:
> I jest jeszcze to, że RB mają mniejszy rozrzut czasów.
> Nieraz też to jest istotne.
Tak, to prawda, choć rzadka sytuacja, np. gdy urządzenie ma limit
czasu oczekiwania na odpowiedź.


> 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.
Ale chyba teraz piszesz o metodzie zaproponowanej przeze mnie, tyle
że wolniej działającej i zajmującej więcej pamięci. Gdy rb-tree
jest zaimplementowane na tablicy, to nie trzeba osobnego wektora, a
samo rb-tree zajmuje mniej ramu.


> Wstawianie mam liniowo (i znacznie szybciej niż Ty), sortowanie
> też nieco szybciej.
Nie rozumiem. Ja mam wstawianie w O(Log(N)) < O(N). Sortowanie
mam w O(N).


> 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.
Tak zrozumiałem, ale dla benchamrku na jedno wychodzi.



> Uporządkowanie tych działań to bardzo spacyficzne zastosowanie,
> i, jak widać powyzej, da sie je zrobić nawet szybciej.
Może coś ze mną nie tak, nie widzę na razie nic szybszego.


> A tu dyskutujemy o uniwersalnych drzewkach.
W różnorodnym teście moja implementacja też działa szybciej niż
std::set i QMap. Specjalnie na potrzeby naszej rozmowy napisałem
drzewko tak, aby było uniwersalne. Nie wiem o co chodzi.



> > 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;-)
Miliardy w sensie, że więcej elementów w drzewie niż wyszukiwań? Tak, wtedy
się nie opłaca sortować nawet w czasie liniowym. Miliardy w sensie, że
trzy miliardy już się nie zmieszczą w int32 i trzeba indeksować tablicę
typem int64... nie wiem ile to spowolni, nie sprawdzałem.


> 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.
Tak. Ale wtedy bym musiał w jednym algorytmie zastosować kilka
wyspecjalizowanych struktur. A tak mam JEDNĄ strukturę uniwersalną
(drzewo rb-tree), zaimplementowaną na tablicy, czyli już
szybszą ze dwa razy niż std::set bez żadnych sortowań. A gdy
przewiduję duży ciąg wyszukiwania, to mogę zrobić sort
przed tym ciągiem i uzyskać przyspieszenie z 3-4 razy, może
nawet 5. Po sortowaniu i wyszukiwaniu drzewo działa jak uniwersalne
rb-tree, nic nie trzeba naprawiać, nic nie trzeba odzyskiwać, można
od razu robić remove i insert. Dzięki temu mam JEDNĄ strukturę która
zarazem może pomieścić 50tys elementów (posortowanie tego w
wektorze to około 1.25mld samych porównań, a gdzie przestawianie
danych), z której niskim kosztem obliczeniowym i pamięciowym mogę
zrobić posortowany wektor.

Pewnie że lepiej byłoby mieć pięć wyspecjalizowanych struktur, a
algorytm byłby nadal elegancki, bo można to załatwić metodą wirtualną.

Jedna struktura to drzewko z sortowaniem w miejscu - takie jakie
zrobiłem. Potem dwie odmiany: z wyszukiwaniem binarnym i interpolacyjnym.
To by miało sens gdzieś od 150 elementów w górę.

Druga struktura to uporządkowany wektor z wyszukiwaniem binarnym lub
interpolacyjnym. To by miało sens gdzieś od 30 elementów w górę.

W końcu wektor nieuporządkowany, to by mogło do około 30 elementów
działać najlepiej.

Można też zrobić tak, że gdy zbiór przekroczy N elementów, to przechodzi
automatycznie na lepszą asymptotycznie strukturę, gdy przekroczy M, to
na kolejną lepszą, a po remove wraca na strukturę gorszą. ALe to jest
już jakość na którą chwilo nie mogę sobie pozwolić. Myślę, że drzewko z
na tablicy jest bardzo dobrą implementacją, a z sortowaniem jest
optymalne gdy spodziewamy się długiej serii wyszukiwania.


> 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.
Tak. Nie wiem jakie ma bebechy. Można taką strukturę zrobić i z pewnym
procentem dziur, zwiększy się czas wyszukiwania, zmniejszy czas wstawiania,
ale dziury można usunąć, jeśli się przewiduje długą serię wyszukiwań, a
potem można dziury wstawić przed serią wstawień.

> Wstawienie jest O(n), ale szybkie (tylko raz dotykasz pamieci, i to średnio
> tylko połowy),
Tak, tutaj się zgadzam całkowicie. Jedno wstawianie jest w czasie O(N).


> w porównaniu do Twojego, gdzie efektywnie masz wstawienie
> o koszcie O(n log n).
Nie wiem dlaczego tak myślisz, coś źle wytłumaczyłem, czy pomyliłeś
się po prostu? Może ja czegoś nie rozumiem? Mam, nawet po posortowaniu,
wstawianie, usuwanie i modyfiakcję w czasie O(Log(N)) < O(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.
Ok.

Pozdrawiam

do góry

On Tuesday, August 22, 2017 at 2:43:29 PM UTC+2, M.M. wrote:
> On Tuesday, August 22, 2017 at 12:23:00 PM UTC+2, bartekltg wrote:
> > I jest jeszcze to, że RB mają mniejszy rozrzut czasów.
> > Nieraz też to jest istotne.
> Tak, to prawda, choć rzadka sytuacja, np. gdy urządzenie ma limit
> czasu oczekiwania na odpowiedź.
>
>
> > 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.
> Ale chyba teraz piszesz o metodzie zaproponowanej przeze mnie, tyle
> że wolniej działającej i zajmującej więcej pamięci. Gdy rb-tree
> jest zaimplementowane na tablicy, to nie trzeba osobnego wektora, a
> samo rb-tree zajmuje mniej ramu.


Nie. Przeczytaj raz jeszcze.
Opisałem, jakich struktur i algorytmów użyć aby zrealizować to,
co było w teście (dodać kupę elementów, potem zrobić kupę wyszukań)
szybciej niż za pomocą tego czasem spłaszczanego drzewa.


>
> > Wstawianie mam liniowo (i znacznie szybciej niż Ty), sortowanie
> > też nieco szybciej.
> Nie rozumiem. Ja mam wstawianie w O(Log(N)) < O(N). Sortowanie
> mam w O(N).


Dodanie masz w log, ale zaraz puszczasz sortowanie.
Więc efektywnie, w sytuacji, którą opisałeś
-modyfikacja drzewa,
-O(n) zapytań
-modyfikacja
...
modyfikacja zajmuje efektywnie tyle, co sortowanie.


> > 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.
> Tak zrozumiałem, ale dla benchamrku na jedno wychodzi.

Tak? Sortowanie co 6 ruchów nie odbije się na wydajności? ;-)


> > Uporządkowanie tych działań to bardzo spacyficzne zastosowanie,
> > i, jak widać powyzej, da sie je zrobić nawet szybciej.
> Może coś ze mną nie tak, nie widzę na razie nic szybszego.

Masz opisane w poście.

Twój test wyglądał tak:

for (...)
insert(coś)

for (...)
delete(coś)

for (...)
find(coś)

Tworzysz dwa wektory, pierwszy V wypełniasz w pierwszej
pętli, drugi, Ve, w drugiej,
Sortuejsz oba, odpalasz na nich set_difference czy coś podobnego.
Wyniku używasz w trzeciej pętli.

Zbudowałeś specjalny test, w którym wychodza zalety Twojego
drzewa z sortowaniem. Ale do tego samego testu można zbudować
skuteczniejszą strukturę - zwykły wektor.


> > A tu dyskutujemy o uniwersalnych drzewkach.
> W różnorodnym teście moja implementacja też działa szybciej niż
> std::set i QMap. Specjalnie na potrzeby naszej rozmowy napisałem
> drzewko tak, aby było uniwersalne. Nie wiem o co chodzi.


Ale ja nie odpowiadam w miejscu gdzie mówisz o uniwersalnej
wydajności, tylko tam, gdzie zaczynasz: "a jak się posortuje".


> > > 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;-)
> Miliardy w sensie, że więcej elementów w drzewie niż wyszukiwań? Tak, wtedy
> się nie opłaca sortować nawet w czasie liniowym.

Tak.



> > 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.
> Tak. Ale wtedy bym musiał w jednym algorytmie zastosować kilka
> wyspecjalizowanych struktur. A tak mam JEDNĄ strukturę uniwersalną

Ale ja się z tym zgadzam i


> > 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.
> Tak. Nie wiem jakie ma bebechy. Można taką strukturę zrobić i z pewnym
> procentem dziur, zwiększy się czas wyszukiwania, zmniejszy czas wstawiania,
> ale dziury można usunąć, jeśli się przewiduje długą serię wyszukiwań, a
> potem można dziury wstawić przed serią wstawień.
>
> > Wstawienie jest O(n), ale szybkie (tylko raz dotykasz pamieci, i to średnio
> > tylko połowy),
> Tak, tutaj się zgadzam całkowicie. Jedno wstawianie jest w czasie O(N).
>
>
> > w porównaniu do Twojego, gdzie efektywnie masz wstawienie
> > o koszcie O(n log n).
> Nie wiem dlaczego tak myślisz, coś źle wytłumaczyłem, czy pomyliłeś
> się po prostu? Może ja czegoś nie rozumiem? Mam, nawet po posortowaniu,
> wstawianie, usuwanie i modyfiakcję w czasie O(Log(N)) < O(N).

Po wstawieniu chcesz znów korzystać z "szybszego" wyszukiwania.
Więc znów sortujesz.

pzdr
bartekltg

do góry

On Tuesday, August 22, 2017 at 3:34:37 PM UTC+2, bartekltg wrote:
> On Tuesday, August 22, 2017 at 2:43:29 PM UTC+2, M.M. wrote:
> > On Tuesday, August 22, 2017 at 12:23:00 PM UTC+2, bartekltg wrote:
> > > I jest jeszcze to, że RB mają mniejszy rozrzut czasów.
> > > Nieraz też to jest istotne.
> > Tak, to prawda, choć rzadka sytuacja, np. gdy urządzenie ma limit
> > czasu oczekiwania na odpowiedź.
> >
> >
> > > 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.
> > Ale chyba teraz piszesz o metodzie zaproponowanej przeze mnie, tyle
> > że wolniej działającej i zajmującej więcej pamięci. Gdy rb-tree
> > jest zaimplementowane na tablicy, to nie trzeba osobnego wektora, a
> > samo rb-tree zajmuje mniej ramu.
>
>
> Nie. Przeczytaj raz jeszcze.
> Opisałem, jakich struktur i algorytmów użyć aby zrealizować to,
> co było w teście (dodać kupę elementów, potem zrobić kupę wyszukań)
> szybciej niż za pomocą tego czasem spłaszczanego drzewa.

Czytałem, zrozumiałem tak. Dodajesz do drzewa N (N>1mln)
elementów. Czas dodawania O( N * Log(N) ). Ilość pamięci
N * (dane + narzut węzła wskaźnikowego + narzut allocatora). Potem
tworzysz posortowany wektor. Czas wyniesie O(N). Zajęta
dodatkowa pamięć N * dane. Potem wyszukujesz M (M dużo
większe od N) razy na wektorze. Czas M * Log(N). Potem
można zwolnić wektor i znowu modyfikować dane w drzewie w
czasie Log(N).

Łączny czas: O( N * Log(N)) + O(N) + M * Log(N).
Łączna pamięć: N * (2 * dane + narzut węzła wskaźnikowego + narzut allocatora)

U mnie to samo zajmuje (asymptotycznie) tyle samo czasu, ale
znacznie mniej pamięci: N * (dane + narzut węzła indeksowego )






> Dodanie masz w log, ale zaraz puszczasz sortowanie.
> Więc efektywnie, w sytuacji, którą opisałeś
> -modyfikacja drzewa,
> -O(n) zapytań
> -modyfikacja
> ...
> modyfikacja zajmuje efektywnie tyle, co sortowanie.
Nie rozumiem. W Twoim rozwiązaniu też jest sortowanie.

W moim drzewku czasy wyglądają tak (w tej kolejności):
1) wstawianie N elementów: O(N*Log(N))
2) sortowanie drzewa: O(N):
3) wyszukanie M razy: M * Log(N)
4) wstawianie K elementów O( K * Log(N+K) )

Jest identycznie, tylko implementacja szybsza i mniej pamięci
zajmuje.





> > > 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.
> > Tak zrozumiałem, ale dla benchamrku na jedno wychodzi.
>
> Tak? Sortowanie co 6 ruchów nie odbije się na wydajności? ;-)
Ale w mojej wersji nie trzeba sortować i bez sortowania
działa wiele szybciej niż std::set. Sortowanie to tylko
ekstra możliwość na wypadek długiego ciągu wyszukiwania.



> > > Uporządkowanie tych działań to bardzo spacyficzne zastosowanie,
> > > i, jak widać powyzej, da sie je zrobić nawet szybciej.
> > Może coś ze mną nie tak, nie widzę na razie nic szybszego.
>
> Masz opisane w poście.
>
> Twój test wyglądał tak:
>
> for (...)
> insert(coś)
>
> for (...)
> delete(coś)
>
> for (...)
> find(coś)
>
> Tworzysz dwa wektory, pierwszy V wypełniasz w pierwszej
> pętli, drugi, Ve, w drugiej,
> Sortuejsz oba, odpalasz na nich set_difference czy coś podobnego.
> Wyniku używasz w trzeciej pętli.

Ok, ale przez moment w pamięci są dwa niepotrzebne wektory i potrzebny
std::set. To jest to samo, tylko jest wolniejsza implementacja i
więcej pamięci zajmuje.


> Zbudowałeś specjalny test, w którym wychodza zalety Twojego
> drzewa z sortowaniem. Ale do tego samego testu można zbudować
> skuteczniejszą strukturę - zwykły wektor.
Nie sądzę. Zwróć uwagę, że te trzy operacje są zapętlone. Po
serii find, jest znowu seria insert i remove. TO jest raczej
coś takiego:

for( ... ) {
for (...)
insert(coś)

for (...)
delete(coś)

for (...)
find(coś)
}

Wektor insertów rozrośnie się niepotrzebnie, gdy będą wstawiane
te same elementy. Wektor elementów do usuniecia też niepotrzebnie
się rozrośnie w przypadku powtórzeń i w przypadku elementów których
nie ma w insertach.


> > > A tu dyskutujemy o uniwersalnych drzewkach.
> > W różnorodnym teście moja implementacja też działa szybciej niż
> > std::set i QMap. Specjalnie na potrzeby naszej rozmowy napisałem
> > drzewko tak, aby było uniwersalne. Nie wiem o co chodzi.
>
>
> Ale ja nie odpowiadam w miejscu gdzie mówisz o uniwersalnej
> wydajności, tylko tam, gdzie zaczynasz: "a jak się posortuje".

Gdy jest dużo wyszukiwania, Ty proponujesz zrzut danych do
osobnego wektora. Ja sortuję w tej samej pamięci w której
są węzły drzewa. Moje rozwiązanie jest lepsze o to, że
nie potrzeba dodatkowej pamięci. Poza tym asymptotycznych
różnic nie ma. Moja implementacja z tego co na razie
widzę, jest dużo szybsza, ale np. set_difference jeszcze
nie sprawdzałem.

> Po wstawieniu chcesz znów korzystać z "szybszego" wyszukiwania.
> Więc znów sortujesz.
Sortuję tylko gdy zapowiada się długi ciąg wyszukiwania w
porównaniu do ilości elementów w drzewie. Gdy np.:

ilość węzłów * 1.5 < ilość wyszukiwań

Może się opłacać nawet gdy:
ilość węzłów * 1.1 < ilość wyszukiwań

I tak samo można postępować na zewnętrznym wektorze, w
rozwiązaniu w które Ty zaproponowałeś.

Gdy ilość wyszukiwań jest relatywnie mała, to wyszukuję bez
uprzedniego sortowania i mam wydajność w mojej implementacji
około 1.5 - 3.0 raza szybszą niż std::set.



Pozdrawiam

do góry

On Tuesday, August 22, 2017 at 4:15:30 PM UTC+2, M.M. wrote:
> On Tuesday, August 22, 2017 at 3:34:37 PM UTC+2, bartekltg wrote:
> > On Tuesday, August 22, 2017 at 2:43:29 PM UTC+2, M.M. wrote:
> > > On Tuesday, August 22, 2017 at 12:23:00 PM UTC+2, bartekltg wrote:
> > > > I jest jeszcze to, że RB mają mniejszy rozrzut czasów.
> > > > Nieraz też to jest istotne.
> > > Tak, to prawda, choć rzadka sytuacja, np. gdy urządzenie ma limit
> > > czasu oczekiwania na odpowiedź.
> > >
> > >
> > > > 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.
> > > Ale chyba teraz piszesz o metodzie zaproponowanej przeze mnie, tyle
> > > że wolniej działającej i zajmującej więcej pamięci. Gdy rb-tree
> > > jest zaimplementowane na tablicy, to nie trzeba osobnego wektora, a
> > > samo rb-tree zajmuje mniej ramu.
> >
> >
> > Nie. Przeczytaj raz jeszcze.
> > Opisałem, jakich struktur i algorytmów użyć aby zrealizować to,
> > co było w teście (dodać kupę elementów, potem zrobić kupę wyszukań)
> > szybciej niż za pomocą tego czasem spłaszczanego drzewa.
>
> Czytałem, zrozumiałem tak. Dodajesz do drzewa N (N>1mln)
> elementów. Czas dodawania O( N * Log(N) ). Ilość pamięci
> N * (dane + narzut węzła wskaźnikowego + narzut allocatora). Potem
> tworzysz posortowany wektor. Czas wyniesie O(N). Zajęta
> dodatkowa pamięć N * dane. Potem wyszukujesz M (M dużo
> większe od N) razy na wektorze. Czas M * Log(N). Potem
> można zwolnić wektor i znowu modyfikować dane w drzewie w
> czasie Log(N).
>
> Łączny czas: O( N * Log(N)) + O(N) + M * Log(N).
> Łączna pamięć: N * (2 * dane + narzut węzła wskaźnikowego + narzut allocatora)
>
> U mnie to samo zajmuje (asymptotycznie) tyle samo czasu, ale
> znacznie mniej pamięci: N * (dane + narzut węzła indeksowego )

A dlaczego masz mieć dane dwa razy? Przecież każdy
obiekt istnieje tylko raz, nie robisz żadnych kopii*).
W maksymalnym momencie masz Ni+Ne, gdzie Ni to liczba
elementów dodanych w pierwszej iteracji, Ne w drugiej.

Jeśli Ni jest duże, np rzędu Ni, to rzeczywiście na raz trzymasz dwa
razy więcej elementów niż w przypadku drzewa, ale jeśli elementy
nie sa za duże, to i tak jesteś do przodu, to nie potrzebujesz
żadnych wskaźników.

*) set_difference robi kopię. Ale wersję która modyfikuje źródło
nie jest ciężko napisać.



>
>
>
>
> > Dodanie masz w log, ale zaraz puszczasz sortowanie.
> > Więc efektywnie, w sytuacji, którą opisałeś
> > -modyfikacja drzewa,
> > -O(n) zapytań
> > -modyfikacja
> > ...
> > modyfikacja zajmuje efektywnie tyle, co sortowanie.
> Nie rozumiem. W Twoim rozwiązaniu też jest sortowanie.

Tylko raz, na poczatku, nie po każdej modyfikacji.
Wstawienie/usunięcie jednego elementu w posortowany ciag
jest O(n)

> W moim drzewku czasy wyglądają tak (w tej kolejności):
> 1) wstawianie N elementów: O(N*Log(N))
> 2) sortowanie drzewa: O(N):
> 3) wyszukanie M razy: M * Log(N)
> 4) wstawianie K elementów O( K * Log(N+K) )

W tej części postu mówiliśmy o wersji "tablicowej",
gdzie drzewko posortowałeś. Więc tam modyfikacja
zajmuje O(sortowanie). Albo tracisz bonus od szybkiego
wyszukiwania i wtedy nie ma tematu.


>
>
> > > > Uporządkowanie tych działań to bardzo spacyficzne zastosowanie,
> > > > i, jak widać powyzej, da sie je zrobić nawet szybciej.
> > > Może coś ze mną nie tak, nie widzę na razie nic szybszego.
> >
> > Masz opisane w poście.
> >
> > Twój test wyglądał tak:
> >
> > for (...)
> > insert(coś)
> >
> > for (...)
> > delete(coś)
> >
> > for (...)
> > find(coś)
> >
> > Tworzysz dwa wektory, pierwszy V wypełniasz w pierwszej
> > pętli, drugi, Ve, w drugiej,
> > Sortuejsz oba, odpalasz na nich set_difference czy coś podobnego.
> > Wyniku używasz w trzeciej pętli.
>
> Ok, ale przez moment w pamięci są dwa niepotrzebne wektory i potrzebny
> std::set.

Jaki, kurde, std::set?
std::set_difference to algorytm działajacy na dwóch posortowanych
zakresach (np wektorach).
Ale racja, trzeba go zmodyfikować, by działał w miejscu.


>
> > Zbudowałeś specjalny test, w którym wychodza zalety Twojego
> > drzewa z sortowaniem. Ale do tego samego testu można zbudować
> > skuteczniejszą strukturę - zwykły wektor.
> Nie sądzę. Zwróć uwagę, że te trzy operacje są zapętlone. Po
> serii find, jest znowu seria insert i remove. TO jest raczej
> coś takiego:
>
> for( ... ) {
> for (...)
> insert(coś)
>
> for (...)
> delete(coś)
>
> for (...)
> find(coś)
> }
>
> Wektor insertów rozrośnie się niepotrzebnie, gdy będą wstawiane
> te same elementy. Wektor elementów do usuniecia też niepotrzebnie
> się rozrośnie w przypadku powtórzeń i w przypadku elementów których
> nie ma w insertach.



Wektor elementów do usunięcia nie rośnie, musisz go czyścić.
Jeśli w pierwszej petli skasowałeś '13', a potem w piątej dodałeś
13, to 13 ma być w kontenerze.

Liczac róznicę rób od razu odpowiednik unique.

>
>
> > > > A tu dyskutujemy o uniwersalnych drzewkach.
> > > W różnorodnym teście moja implementacja też działa szybciej niż
> > > std::set i QMap. Specjalnie na potrzeby naszej rozmowy napisałem
> > > drzewko tak, aby było uniwersalne. Nie wiem o co chodzi.
> >
> >
> > Ale ja nie odpowiadam w miejscu gdzie mówisz o uniwersalnej
> > wydajności, tylko tam, gdzie zaczynasz: "a jak się posortuje".
>
> Gdy jest dużo wyszukiwania, Ty proponujesz zrzut danych do
> osobnego wektora.


Nie.
Jeśli bardzo chcesz, mozęmy wrócić do tematu (choc nie wiem,
do czego on daży, imho się trolociag zrobił), ale dopiero,
jak postarasz się zrozumieć, jaki algorytm i dlaczego
tam zapisałem.

> Ja sortuję w tej samej pamięci w której
> są węzły drzewa. Moje rozwiązanie jest lepsze o to, że
> nie potrzeba dodatkowej pamięci. Poza tym asymptotycznych
> różnic nie ma. Moja implementacja z tego co na razie
> widzę, jest dużo szybsza, ale np. set_difference jeszcze
> nie sprawdzałem.

Asymptotycznie to std::set daje to samo. myślałem, że
walczysz o stałą;-)


pzdr
bartekltg

do góry

On Tuesday, August 22, 2017 at 4:39:39 PM UTC+2, bartekltg wrote:
> A dlaczego masz mieć dane dwa razy? Przecież każdy
> obiekt istnieje tylko raz, nie robisz żadnych kopii*).
> W maksymalnym momencie masz Ni+Ne, gdzie Ni to liczba
> elementów dodanych w pierwszej iteracji, Ne w drugiej.
Nawiązałeś do tamtego przykładu, a tam była jeszcze
pętla obejmująca to wszystko, więc pociągnąłem w tym
kierunku :) Ale masz rację, nie muszę mieć danych dwa
razy. Dla bezpieczeństwa muszę mieć strukturę o dobrych
właściwościach ogólnych, przykładem jest rb-tree. Okazało
się, że zaimplementowane rb-tree na tablicy działa i
szybciej w ogólnym przypadku, i umożliwia sztuczkę z
sortowaniem bez dodatkowej pamięci. Dlatego tak mocno
się przekonałem do takiej implementacji.


> Jeśli Ni jest duże, np rzędu Ni, to rzeczywiście na raz trzymasz dwa
> razy więcej elementów niż w przypadku drzewa, ale jeśli elementy
> nie sa za duże, to i tak jesteś do przodu, to nie potrzebujesz
> żadnych wskaźników.
>
> *) set_difference robi kopię. Ale wersję która modyfikuje źródło
> nie jest ciężko napisać.
Tak, można brać elementy z tyłu wektorów i wywoływać shrink_to_fit
co jakiś czas. Sztuczek jest wiele które w konkretnym przypadku
mogą przyspieszyć lub zaoszczędzić pamięć.

> Tylko raz, na poczatku, nie po każdej modyfikacji.
> Wstawienie/usunięcie jednego elementu w posortowany ciag
> jest O(n)
Rozumiem. Masz rację. Początkowo zrozumiałem, że w mojej
wersji drzewa wstawienie/usunięcie będzie kosztowało
O(N) po posortowaniu. Moim drzewie cały czas wstawienie i
usunięcie kosztują O(Log(N)).

Masz rację, że na początku można posortować dane. Sortowanie
prawdopodobnie będzie znacznie szybsze niż wstawianie do
drzewa. W dodatku, sortujemy same dane, a nie meta-dane
drzewa. Ja będę miał kopię, więc odtworzenie z kopii samych
danych będzie jeszcze szybsze. Algorytm:

for( j=0 ; j<M ; j++ )
set.insert( rand() );
for( j=0 ; j<K ; j++ ) {
set.insert( rand() );
for( k=0 ; k<L ; k++ )
set.search( rand() );
}

Dla L > M powinien zadziałać szybciej na posortowanej tablicy.

Jednak ten przykład podałem nie jako ostateczny cel, lecz
dlatego, aby upewnić się, że rozumiemy się co do liniowej
złożoności sortowania i logarytmicznej wyszukiwania, nawet
jeśli wyszukiwanie jest po sortowaniu i modyfikowaniu.

W praktyce czasami mogę mieć kilka insertów, albo L < M i
już na tablicy będzie ryzykownie.

Ja naprawdę chciałem uzyskać ogólną dobrą implementację, plus
to sortowanie jako jedno ulepszenie ekstra. Trochę boję się
stosować tablicy, bo po długim czasie programowania okaże się
że modyfikacji przypada więcej niż przewidziałem na początku i
będę musiał przerabiać.










> > W moim drzewku czasy wyglądają tak (w tej kolejności):
> > 1) wstawianie N elementów: O(N*Log(N))
> > 2) sortowanie drzewa: O(N):
> > 3) wyszukanie M razy: M * Log(N)
> > 4) wstawianie K elementów O( K * Log(N+K) )
>
> W tej części postu mówiliśmy o wersji "tablicowej",
> gdzie drzewko posortowałeś. Więc tam modyfikacja
> zajmuje O(sortowanie). Albo tracisz bonus od szybkiego
> wyszukiwania i wtedy nie ma tematu.

Tak, bo zabrzmiałem zbyt dosłownie z tym przykładem w
którym wykonuję dokładnie jedną modyfikację :) To
był tylko przykład w celu który powyżej opisałem.
Masz rację, że gdy jest dosłownie jedna modyfikacja, to
na wektorze powinno działać szybciej.

Ale przynajmniej wiem dlaczego się nie rozumielismy :D

> Jaki, kurde, std::set?
> std::set_difference to algorytm działajacy na dwóch posortowanych
> zakresach (np wektorach).
> Ale racja, trzeba go zmodyfikować, by działał w miejscu.
Myślałem std::set_difference wypluwa std::set :) Nieważne. Ważne
że można to zaimplementować tak, aby działał w miejscu.


> > > Zbudowałeś specjalny test, w którym wychodza zalety Twojego
> > > drzewa z sortowaniem. Ale do tego samego testu można zbudować
> > > skuteczniejszą strukturę - zwykły wektor.
> > Nie sądzę. Zwróć uwagę, że te trzy operacje są zapętlone. Po
> > serii find, jest znowu seria insert i remove. TO jest raczej
> > coś takiego:
> >
> > for( ... ) {
> > for (...)
> > insert(coś)
> >
> > for (...)
> > delete(coś)
> >
> > for (...)
> > find(coś)
> > }
> >
> > Wektor insertów rozrośnie się niepotrzebnie, gdy będą wstawiane
> > te same elementy. Wektor elementów do usuniecia też niepotrzebnie
> > się rozrośnie w przypadku powtórzeń i w przypadku elementów których
> > nie ma w insertach.
>
>
>
> Wektor elementów do usunięcia nie rośnie, musisz go czyścić.
> Jeśli w pierwszej petli skasowałeś '13', a potem w piątej dodałeś
> 13, to 13 ma być w kontenerze.

Ale do usunięcia może napłynąć dużo takich samych liczb. Gdy usuwamy z
drzewa, to za pierwszym razem usuwamy, a potem próba usunięcia kończy
się niepowodzeniem. Gdy elementy do usunięcia kumulujemy w wektorze, to
wektor zawierający np. 4 różne liczby, może zawierać 40 liczb, czyli
może być 10krotny narzut pamięciowy. Przy usuwaniu z drzewa nie będzie
takiego narzutu. Tak samo dane do wstawienia mogą się skumulować w
wektorze, może być 10 razy dłuższy niż ilość różnych wartości.

> Liczac róznicę rób od razu odpowiednik unique.
Tak, ale zanim zrobię różnicę, to muszę tracić pamięć na kumulowanie
tych samych wartości. W drzewku nie ma tego problemu.

> Nie.
> Jeśli bardzo chcesz, mozęmy wrócić do tematu (choc nie wiem,
> do czego on daży, imho się trolociag zrobił), ale dopiero,
> jak postarasz się zrozumieć, jaki algorytm i dlaczego
> tam zapisałem.
Starałem się od początku, ale nie było to oczywiste, bo tamten
przykład podałem w innym celu i myślałem że z innego powodu
zarzucasz mi czas wstawiania O(N).

Nie ma problemu, mogę do bencznarków wrzucić i ten konkretny
przypadek z jednym insertem na N wyszukiwań. CHociaż bez
sprawdzania wiadomo na 99% że co do tego masz racje.


> Asymptotycznie to std::set daje to samo. myślałem, że
> walczysz o stałą;-)
A ja myślałem, że zarzucasz mi, że wstawianie mam gorsze
asymptotycznie, bo coś tam sortowanie psuje :D


Pozdrawiam

do góry