To pytanie jest inspirowane innym pytaniem o to, co nowego w PFDS od publikacji książki Okasaki w 1998 roku .
Zacznę od dwóch pytań, które mam:
- Czy istnieje czysto funkcjonalna struktura danych, która zbliża się do prędkości tabel mieszania? Prób jeszcze tam nie ma.
- Czy istnieją czysto funkcjonalne drzewa palcowe z dołączonym O (1)? Najlepsze jak dotąd to O (lg lg n), opracowane przez Kaplana i Tarjana.
Jakie inne czysto funkcjonalne problemy ze strukturą danych są otwarte?
Odpowiedzi:
Zinterpretuję to pytanie dość swobodnie. W przypadku struktur danych w stylu Okasaki, zapamiętywanie jest formą ukrytej mutacji, która ma wpływ uboczny na czas działania. Dlatego przyjmuję pytanie dotyczące trwałych struktur danych w ścisłym tego słowa znaczeniu, a nie struktur danych z czysto funkcjonalną implementacją, które są podzbiorem tego pierwszego. Przez ścisłe rozumiem, że powinieneś mieć dostęp do starszych wersji struktury danych bez kary, drzewo wersji może rozgałęziać się dowolnie itp.
W tym kontekście uważam, że trwałe UNION-FIND jest ważnym otwartym problemem. Istnieje artykuł Conchon-Filliâtre, o którym wspomniano w drugim wątku. Komentator już poruszył problem z tak zwaną trwałą tablicą: tak naprawdę jest tylko częściowo trwały. Załóżmy jednak, że zastąpisz go hasłem lub inną naprawdę trwałą tablicą, która zachowuje się lepiej w najgorszym (i prawdopodobnie przeciętnym) przypadku, ale gorzej w najlepszym przypadku. To wciąż pozostawia ważną kwestię otwartą:
Artykuł daje formalny dowód poprawności w Coq. Ale nie rozwiązują zamortyzowanej złożoności ani formalnie, ani nieformalnie. To bardzo dużo nie dla mnie jasne, że skomplikowana zza kulis wyniki mutacja w oczekiwany amortyzowane złożoność we wszystkich przypadkach. Kiedy po raz ostatni o tym pomyślałem, poczułem się pewnie, że mógłbym zbudować kontrprzykład, jeśli włożę w to wysiłek. Nawet jeśli się mylę co do tej ostatniej części, brak właściwej analizy stanowi poważną lukę; jasne jest, że klasyczna analiza amortyzacyjna UNION-FIND dokonana przez Trajana nie przenosi się bezpośrednio.
źródło
Tu jest jeden:
Jaki jest czysto funkcjonalny odpowiednik słabej tabeli skrótów?
źródło