Jaka jest najskuteczniejsza implementacja tablic z aktualizacjami funkcjonalnymi?

Question

Potrzebuję struktury danych w formie tablicy z najszybszą możliwą aktualizacją funkcjonalną. Widziałem kilka różnych implementacji elastycznych tablic, które zapewniają mi tę właściwość (Braun, listy dostępu losowego), ale zastanawiam się, czy istnieje implementacja, która jest specjalnie zoptymalizowana pod kątem przypadku, gdy nie jesteśmy zainteresowani dołączaniem lub wstawianiem - tylko aktualizacje.

Answer 1

Jean-Cristophe Filliâtre ma a very nice implementation z trwałych tablic, który jest opisany w the paper połączonych na tej samej stronie (która dotyczy trwałego union-find, którego trwałe składowe są głównym składnikiem). Kod jest dostępny bezpośrednio pod numerem there.

Chodzi o to, że „ostatnia wersja” tablicy jest reprezentowany jako zwykłej tablicy, z O(1) dostępu i operacji aktualizacji, a poprzednie wersje są reprezentowane tej ostatniej wersji, a także lista różnic. Jeśli spróbujesz uzyskać dostęp do poprzedniej wersji struktury, tablica zostanie "ponownie utworzona", aby zastosować listę różnic i ponownie zaprezentować efektywną reprezentację.

To oczywiście nie będzie O (1) pod wszystkimi przepływami pracy (jeśli będziesz mieć stały dostęp do i modyfikować niepowiązane wersje struktury, często będziesz płacić za ponowne wyliczanie kosztów), ale dla wspólnego przepływu pracy głównie z jedną wersją, i od czasu do czasu wracając do starszej wersji, która ponownie staje się "ostatnią wersją" i otrzymuje aktualizacje, jest to bardzo wydajne. Bardzo przyjemne wykorzystanie zmienności ukrytej pod czysto obserwacyjnym interfejsem.

Answer 2

Jakiego języka używasz? W Haskell można używać mutable arrays z monadą państwową, aw Merkurymu można używać tablic zmiennych, przewijając stan IO. Ocaml ma również moduł tablicowy, który niestety nie zachowuje referencyjnej przezroczystości, jeśli tego właśnie szukasz.

Answer 3

Mam bardzo dobre doświadczenia z repa (nice demo). Bardzo dobra wydajność, automatyczny równoległość, wielowymiarowy, polimorficzny. Zalecane, aby spróbować.

Answer 4

Potrzebowałem również funkcjonalnych tablic i filcu na to pytanie SO kilka dni temu. Nie byłem usatysfakcjonowany rozwiązaniem zaproponowanym przez Gasche, ponieważ tworzenie nowej macierzy jest kosztowną operacją i muszę często uzyskiwać dostęp do starszych wersji macierzy (mam zamiar użyć tego do implementacji alfa/beta AI odtwarzanej w tablicy).

(Kiedy mówię, kosztowne, myślę, że jest to O (n * h), gdzie h jest wielkością historii, ponieważ w najgorszym przypadku tylko jedna komórka była aktualizowana wielokrotnie i jest potrzebna do przejrzenia całej listy aktualizacji dla każdego komórka.Oczekuję również, większość komórek nie jest aktualizowana, gdy trzeba do przekierowania tablicy).

Dlatego proponuję inne podejście, może uda mi się uzyskać tutaj informacje zwrotne. Moim pomysłem jest przechowywanie tablicy jak w B-Tree, z tym że, ponieważ nie jest zmienna, mogę łatwo uzyskać dostęp i zaktualizować dowolną wartość przez indeks.

Napisałem mały wstęp do repozytorium projektu: https://github.com/shepard8/ocaml-ptarray. Kolejność jest wybierana tak, aby uzyskać nawet głębokość i porządek drzewa, dzięki czemu mogę uzyskać niezłe komplikacje w zależności od kolejności operacji get/set, czyli O (k^2).

Przy k = 10 mogę zapisać do 10^10 wartości. W rzeczywistości moje tablice nie powinny zawierać więcej niż 200 wartości, ale ma to na celu pokazanie, jak trwałe jest moje rozwiązanie.

Każda rada powitana!