eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingDrzewa AA › Re: Drzewa AA
  • X-Received: by 10.31.174.14 with SMTP id x14mr4076vke.18.1503405807809; Tue, 22 Aug
    2017 05:43:27 -0700 (PDT)
    X-Received: by 10.31.174.14 with SMTP id x14mr4076vke.18.1503405807809; Tue, 22 Aug
    2017 05:43:27 -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!e2no1625562qta.1!news-out.google.com!i9ni50780qte.0!nnt
    p.google.com!e2no1625561qta.1!postnews.google.com!glegroupsg2000goo.googlegroup
    s.com!not-for-mail
    Newsgroups: pl.comp.programming
    Date: Tue, 22 Aug 2017 05:43:27 -0700 (PDT)
    In-Reply-To: <f...@g...com>
    Complaints-To: g...@g...com
    Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=159.205.152.94;
    posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
    NNTP-Posting-Host: 159.205.152.94
    References: <1...@g...com>
    <5...@g...com>
    <d...@g...com>
    <f...@g...com>
    User-Agent: G2/1.0
    MIME-Version: 1.0
    Message-ID: <d...@g...com>
    Subject: Re: Drzewa AA
    From: "M.M." <m...@g...com>
    Injection-Date: Tue, 22 Aug 2017 12:43:27 +0000
    Content-Type: text/plain; charset="UTF-8"
    Content-Transfer-Encoding: quoted-printable
    Lines: 167
    Xref: news-archive.icm.edu.pl pl.comp.programming:211231
    [ ukryj nagłówki ]

    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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

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: