Structura de date persistentă

În domeniul IT , o structură de date persistentă este o structură de date care, atunci când este modificată, păstrează întotdeauna versiunea anterioară a acesteia: aceste structuri de date sunt de fapt imuabile, deoarece operațiunile efectuate asupra acestora nu actualizează vizibil structura existentă, aducând în schimb la crearea unei noi structuri actualizate. O structură de date persistentă nu trebuie înțeleasă ca o structură de date stocată pe o memorie persistentă (permanentă), cum ar fi un hard disk : este o semnificație diferită a termenului persistent.

O structură de date este parțial persistentă dacă toate versiunile pot fi accesate, dar numai cele mai recente pot fi modificate. O structură de date este complet persistentă dacă toate versiunile pot fi accesate și modificate. Dacă este posibilă și operația de îmbinare care creează o nouă versiune din două versiuni anterioare, structura de date este numită persistent confluent . Structurile de date care nu sunt persistente se numesc efemere .

Aceste tipuri de structuri sunt deosebit de frecvente în programarea logică și programarea funcțională : în programele pur funcționale toate datele sunt imuabile astfel încât să facă structurile de date complet persistente. Structurile de date persistente pot fi, de asemenea, create prin actualizarea datelor la locul lor, iar acestea pot necesita de obicei mai puțin timp și spațiu de stocare în masă decât omologii lor pur funcționali.

Deși persistența poate fi realizată prin simpla copiere, aceasta nu este foarte eficientă în ceea ce privește timpul și spațiul, deoarece multe operații produc doar mici modificări într-o structură de date. O metodă mai bună este de a exploata asemănările dintre versiunile vechi și noi pentru a partaja părți comune, cum ar fi utilizarea aceluiași subarborescent în structurile de copac. Cu toate acestea, din moment ce devine deseori imposibil de determinat câte versiuni anterioare împărtășesc aceleași părți ale structurii și pentru că de multe ori doriți să renunțați la versiunile vechi, este necesar un mediu cu colectare a gunoiului .

Poate că cea mai simplă structură persistentă este lista legată , o listă simplă de obiecte în care fiecare are o referință care indică următoarea din listă. Este persistent prin faptul că îi puteți lua coada (formată dintr-un anumit număr de intrări) și puteți adăuga un nou nod: coada va fi partajată între lista veche și cea nouă. Atâta timp cât intrările în coadă sunt imuabile, partajarea va fi invizibilă pentru program.

Multe structuri de date bazate pe puncte, cum ar fi RB-Trees și cozi , pot fi ușor adaptate pentru a crea structuri de date persistente.

linkuri externe

• Continuarea structurilor de date , pe cs.cmu.edu .
• Structuri de date persistente (sondaj) , pe citeseerx.ist.psu.edu .
• Tablouri complet persistente pentru actualizări incrementale eficiente și citiri voluminoase , pe citeseerx.ist.psu.edu .
• Deque în timp real, mașini de turing cu mai multe capete și programare pur funcțională , pe citeseerx.ist.psu.edu .