Biorąc pod uwagę specyfikację struktury danych, taką jak czysto funkcjonalna mapa ze znanymi granicami złożoności, należy wybrać między kilkoma implementacjami. Istnieje pewien folklor na temat wyboru właściwego, na przykład drzewa czerwono-czarne są uważane za generalnie szybsze, ale drzewa AVL mają lepszą wydajność przy obciążeniach roboczych przy wielu wyszukiwaniach.Statystyczna wydajność czysto funkcjonalnych map i zestawów
Czy istnieje systematyczna prezentacja (opublikowana praca) tej wiedzy (w odniesieniu do zestawów/map)? Idealnie chciałbym zobaczyć analizę statystyczną przeprowadzoną na rzeczywistym oprogramowaniu. Można na przykład stwierdzić, że istnieje N typowych rodzajów użycia mapy i wymienić rozkład prawdopodobieństwa wejścia dla każdego z nich.
Czy istnieją systematyczne testy porównawcze, które testują mapę i określają wydajność różnych dystrybucji danych wejściowych?
Czy istnieją implementacje, które używają algorytmów adaptacyjnych do zmiany reprezentacji w zależności od rzeczywistego użycia?
trzeba było patrzeć na książki Okasaki za [* czysto funkcjonalne struktury danych *?] (Http: //www.amazon. com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504) –
@RobertHarvey, tak, mam kopię. Ma doskonały materiał do projektowania PFDS i wykonywania analizy złożoności. Ma również pewne wskazówki dla praktyków (folklor, o którym mowa powyżej). Szukam więcej danych empirycznych i/lub analizy statystycznej rzeczywistych wzorców użytkowania. – t0yv0
Wydaje się, że jest to interesujące pytanie, ale nie jestem pewien, czy jest on tematem tutaj. Jest to bardzo zlokalizowane, w tym sensie, że zasadniczo masz nadzieję, że ktoś się tu natknie, że tak po prostu wie o gazecie, która mówi o tym (jest to pytanie typu "canihazresourcez", innymi słowy, wyszukiwanie w Internecie tłumaczy) . W każdym razie pobieżna wyszukiwarka Google wymyśli to: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.9196 –