| dbpprop:abstract
|
- In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word "persistent. " A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. The data structure is fully persistent if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent. Structures that are not persistent are called ephemeral. These types of data structures are particularly common in logical and functional programming, and in a purely functional program all data is immutable, so all data structures are automatically fully persistent. Persistent data structures can also be created using in-place updating of data and these may, in general, use less time or storage space than their purely functional counterparts. While persistence can be achieved by simple copying, this is inefficient in time and space, because most operations make only small changes to a data structure. A better method is to exploit the similarity between the new and old versions to share structure between them, such as using the same subtree in a number of tree structures. However, because it rapidly becomes infeasible to determine how many previous versions share which parts of the structure, and because it is often desirable to discard old versions, this necessitates an environment with garbage collection. Perhaps the simplest persistent data structure is the singly-linked list or cons-based list, a simple list of objects formed by each carrying a reference to the next in the list. This is persistent because we can take a tail of the list, meaning the last k items for some k, and add new nodes on to the front of it. The tail will not be duplicated, instead becoming shared between both the old list and the new list. So long as the contents of the tail are immutable, this sharing will be invisible to the program. Many common reference-based data structures, such as red-black trees, and queues, can easily be adapted to create a persistent version.
- Se entiende por persistencia (en programación) como la acción de preservar la información de un objeto de forma permanente (guardar), pero a su vez también se refiere a poder recuperar la información del mismo (leer) para que pueda ser nuevamente utilizada. En el caso de persistencia de objetos la información que persiste en la mayoría de los casos son los valores que contienen los atributos en ese momento, no necesariamente la funcionalidad que proveen sus métodos. Nota: La persistencia no es ni una capacidad ni una propiedad de la POO, no tiene nada que ver con el paradigma en sí, solo es el mecanismo que se usa para persistir información de un determinado tipo (como puede ser serializar, guardar los datos en una tabla, en un archivo plano, etc). Desde la óptica de la persistencia, se podrían clasificar los objetos en: Transitorios: Cuyo tiempo de vida depende directamente del ámbito del proceso que los instanció. Persistentes: Cuyo estado es almacenado en un medio secundario para su posterior reconstrucción y utilización, por lo que su tiempo de vida es independiente del proceso que los instanció. La persistencia permite al programador almacenar, transferir y recuperar el estado de los objetos. Para esto existen varias técnicas: Serialización Motores de persistencia Bases de datos orientadas a objetos
- En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu'elle est modifiée; une telle structure est observationnellement immuable, car ses opérations ne la modifient pas en place (de manière visible) mais renvoient au contraire de nouvelles structures. Une structure est partiellement persistante si seule sa version la plus récente peut être modifiée, les autres n'étant accessibles qu'en lecture. La structure est dite totalement persistante si chacune de ses versions peut être lue ou modifiée. S'il existe une opération permettant la fusion de deux versions antérieures, la structure est dite confluente. Les structures qui ne sont pas persistantes sont dites éphémères. Ce type de structures de données est particulièrement courant en programmation logique et fonctionnelle. Dans un programme purement fonctionnel, où toute donnée est immuable, les structures de données sont automatiquement totalement persistantes. Les structures persistantes peuvent aussi être obtenues en utilisant des modifications en place des données et peuvent alors être parfois plus efficaces, en temps ou en espace, que leurs contreparties purement fonctionnelles. Bien que la persistance peut être obtenue par une simple copie, c'est en général une solution inefficace en temps et en espace, car la plupart des opérations n'effectuent que peu de changements dans une structure de données. Une meilleure solution consiste à exploiter les similarités entre les anciennes versions et la nouvelle, telles que des sous-arbres communs dans un certain nombre de structures d'arbre. Parce qu'il devient rapidement difficile de déterminer quelles sont les parties de la structure effectivement partagées entre plusieurs versions, et parce qu'il est souvent souhaitable de supprimer des versions devenues inutiles, la présence d'un ramasse-miettes s'impose naturellement. La structure de données persistante la plus simple est sans doute celle de liste simplement chaînée, où chaque élément contient une référence vers l'élément suivant dans la liste. Une telle structure est persistante si les opérations se limitent à extraire un suffixe d'une liste, c'est-à-dire les k derniers éléments pour un certain k, et à y ajouter de nouveaux éléments en tête. Le suffixe peut alors être partagé entre l'ancienne liste et la nouvelle, au lieu d'être dupliqué. Tant que les éléments sont immuables, ce partage reste invisible. De nombreuses structures de données, telles que les arbres bicolores ou les files, peuvent facilement être adaptées pour être persistantes. Une version persistante de la structure de tableau est la structure de VList introduite en 2002 par Phil Bagwell.
- 永続データ構造（英: Persistent data structure）とは、変更される際に変更前のバージョンを常に保持するデータ構造である。このようなデータ構造は、更新の際に元のデータ構造を書き換えるのではなく、新たなデータ構造を生成すると考えられ、イミュータブルなデータ構造の構築に利用可能である。
- Persistentie betekent dat iets lang in stand blijft.
- 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.
|
| rdfs:comment
|
- In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word "persistent.
- Se entiende por persistencia (en programación) como la acción de preservar la información de un objeto de forma permanente (guardar), pero a su vez también se refiere a poder recuperar la información del mismo (leer) para que pueda ser nuevamente utilizada. En el caso de persistencia de objetos la información que persiste en la mayoría de los casos son los valores que contienen los atributos en ese momento, no necesariamente la funcionalidad que proveen sus métodos.
- En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu'elle est modifiée; une telle structure est observationnellement immuable, car ses opérations ne la modifient pas en place (de manière visible) mais renvoient au contraire de nouvelles structures. Une structure est partiellement persistante si seule sa version la plus récente peut être modifiée, les autres n'étant accessibles qu'en lecture.
- 永続データ構造（英: Persistent data structure）とは、変更される際に変更前のバージョンを常に保持するデータ構造である。このようなデータ構造は、更新の際に元のデータ構造を書き換えるのではなく、新たなデータ構造を生成すると考えられ、イミュータブルなデータ構造の構築に利用可能である。
- Persistentie betekent dat iets lang in stand blijft.
- 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.
|
![[RDF Data]](/statics/sw-cube.png)
