eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › Drzewa AA
Ilość wypowiedzi w tym wątku: 10

  • 1. Data: 2017-08-21 02:09:03
    Temat: Drzewa AA
    Od: "M.M." <m...@g...com>

    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?


  • 2. Data: 2017-08-21 22:58:33
    Temat: Re: Drzewa AA
    Od: bartekltg <b...@g...com>

    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


  • 3. Data: 2017-08-22 00:27:44
    Temat: Re: Drzewa AA
    Od: "M.M." <m...@g...com>

    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


  • 4. Data: 2017-08-22 00:29:22
    Temat: Re: Drzewa AA
    Od: "M.M." <m...@g...com>

    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


  • 5. Data: 2017-08-22 12:22:59
    Temat: Re: Drzewa AA
    Od: bartekltg <b...@g...com>

    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


  • 6. Data: 2017-08-22 14:43:27
    Temat: Re: Drzewa AA
    Od: "M.M." <m...@g...com>

    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


  • 7. Data: 2017-08-22 15:34:36
    Temat: Re: Drzewa AA
    Od: bartekltg <b...@g...com>

    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


  • 8. Data: 2017-08-22 16:15:29
    Temat: Re: Drzewa AA
    Od: "M.M." <m...@g...com>

    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


  • 9. Data: 2017-08-22 16:39:37
    Temat: Re: Drzewa AA
    Od: bartekltg <b...@g...com>

    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


  • 10. Data: 2017-08-22 20:19:28
    Temat: Re: Drzewa AA
    Od: "M.M." <m...@g...com>

    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

strony : [ 1 ]



Szukaj w grupach

Szukaj w grupach

REKLAMA

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo:

Strona korzysta z plików cookies w celu realizacji usług i zgodnie z Polityką Prywatności. Możesz określić warunki przechowywania lub dostępu do plików cookies w Twojej przeglądarce.