Trwała struktura danych

Z Wikipedii

W przetwarzaniu komputerowym, trwała struktura danych albo czysto funkcyjna struktura danych to struktura danych, która zawsze zachowuje swoje poprzednie wersje kiedy są modyfikowane. Takie struktury danych są w efekcie niezmienne, jako że operacje na nich nie powodują zmiany samej struktury lecz powoduje powstanie nowej, uaktualnionej jej wersji. Trwała struktura danych nie jest strukturą danych składowaną na trwałym nośniku danych, takim jak dysk; jest to inne i niepowiązane znaczenie słowa "trwały".

Struktura danych jest częściowo trwała jeśli wszystkie jej wersje mogą być odczytane, ale tylko najnowsza wersja może być modyfikowana. Struktura danych jest całkowicie trwała jeśli wszystkie jej wersje mogą być odczytane i modyfikowane. Struktura danych jest zbieżnie trwała (ang. confluently persistent) jeśli istnieje operacja mieszania lub scalania, które mogą stworzyć nową wersję na podstawie dwóch poprzednich wersji. Struktury, które nie są trwałe, są ulotne.

Te typy struktur danych są szczególnie częste w programowaniu logicznym i funkcyjnym. W programowaniu czysto funkcyjnym, wszystkie dane są niezmienne i przez to struktury danych stają się automatycznie całkowicie trwałe. Trwałe struktury danych mogą być także tworzone przez aktualizację danych w miejscu, przez co mogą one być szybsze lub zajmować mniej miejsca niż ich czysto funkcyjne odpowiedniki.

Trwałość może być osiągana przez proste kopiowanie, ale jest to nieefektywne czasowo i zajmuje za dużo miejsca, ponieważ większość operacji wykonuje tylko drobne zmiany w tych strukturach danych. Lepszym sposobem jest wykorzystanie podobieństwa pomiędzy nowymi i starymi wersjami do wspóldzielenia struktur pomiędzy nimi, np. użycie tego samego poddrzewa w strukturach drzewa. Ponieważ przy takim postępowaniu szybko dochodzimy do sytuacji, że istnieją liczne starsze wersje i jest wtedy konieczne określenie które części wspólnej struktury są współdzielone przez te wersje, więc pożądane jest istnienie w środowisku zarządzania pamięcią typu garbage collection. Wtedy można łatwo pozbyć się starszych, niepotrzebnych wersji.

Być może najprostszą trwałą strukturą danych jest lista jednokierunkowa, w którym każdy obiekt (ogniwo tej listy) posiada wskaźnik do następnego obiektu listy. Jest to struktura trwała, ponieważ możemy wziąć ogon listy, tzn. ostatnie k obiektów i dodawać nowe obiekty na przodzie tego ogona. Wtedy ten ogon nie będzie powielony; będzie współdzielony pomiędzy starą i nową listą. Dopóki zawartość ogona pozostanie niezmienna, to współdzielenie będzie niewidoczne dla programu.

Wiele często używanych struktur danych bazujących na wskaźnikach, takich jak drzewa czerwono-czarne i kolejki, mogą być łatwo zmienionych na wersje trwałe. Na przykład, odpowiednikiem tablicy może być VLista, struktura danych stworzona w 2002 przez Phila Bagwella.

[edytuj] Zobacz też

• Trwałość (informatyka)
• Nawigowalne bazy danych

[edytuj] Linki zewnętrzne

• Making Data Structures Persistent (or Author's version)
• Persistent Data Structures (survey)
• Fully persistent arrays for efficient incremental updates and voluminous reads
• Real-Time Deques, Multihead Turing Machines, and Purely Functional Programming

---