2010-12-09 21 views
16

¿Existen implementaciones de estructuras de datos persistentes en C++ similares a las de clojure?Estructuras de datos persistentes en C++

+1

C++ no es basura recolectada, lo que hace que construir tales estructuras sea extremadamente complicado. Si no le importan las pérdidas de memoria (o ha integrado un recolector de basura), entonces es fácil. –

+2

Guau, cálmate, hermano. Buscar "Clojure" no es tan difícil; y generalmente no me jacto de no haber oído hablar de un lenguaje que está a la vanguardia de la programación funcional. No soy un gran admirador de esto, pero me parece extraño que una pregunta deba ser menospreciada por mencionarla. (Aunque estoy totalmente de acuerdo con su sugerencia de reevaluar las necesidades, en lugar de calzar el estilo de otro idioma en C++). –

+0

relacionado: http://stackoverflow.com/questions/2757278/functional-data-structures-in-c, http://stackoverflow.com/questions/303426/efficient-persistent-data-structures-for-relational-database –

Respuesta

0

Si entiendo la pregunta correctamente, lo que busca es la capacidad de duplicar un objeto sin pagar realmente la duplicación cuando está hecho, solo cuando es necesario. Los cambios en cualquier objeto pueden realizarse sin dañar el otro. Esto se conoce como "copiar al escribir".

Si esto es lo que está buscando, esto puede implementarse fácilmente en C++ utilizando punteros compartidos (vea shared_ptr from Boost, como una implementación). Inicialmente, la copia compartiría todo con la fuente, pero una vez que se realizan cambios, las partes relevantes de los punteros compartidos del objeto se reemplazan por otros punteros compartidos que apuntan a los objetos recientemente creados y copiados a fondo. (Me doy cuenta de que esta explicación es vaga: si esto es lo que quieres decir, la respuesta puede ser elaborada).

+0

Copy-on-write es funcionalmente lo que busca @Miguel, pero conduce a colecciones que funcionan mal en repetidas escrituras. –

+0

Es la "copia profunda" en copy-on-write que lo hace inadecuado para usar en la programación funcional. Las estructuras de datos en la programación funcional son estructuras de datos persistentes. Dado que son inmutables, si desea "modificarlo", se crea una nueva "copia" (nueva versión) y la versión anterior sigue disponible. Sería un desperdicio de memoria hacer copias completas cuando solo una parte de la estructura es diferente (por ejemplo, la "cabeza" de una lista). En cambio, las dos versiones comparten la parte común (por ejemplo, la "cola" de la lista). –

2

La principal dificultad para obtener una estructura de datos persistente es, de hecho, la falta de recolección de basura.

Si no tiene un esquema de recolección de basura adecuado, puede obtener uno pobre (a saber, recuento de referencias), pero esto significa que debe tener especial cuidado de NO crear referencias cíclicas.

Cambia el núcleo mismo de la estructura. Por ejemplo, piense en árbol binario. Si crea una nueva versión de un nodo, entonces necesita una nueva versión de su principal para acceder a ella (etc ...). Ahora, si la relación es bidireccional (hijo < -> padre), de hecho duplicará toda la estructura. Esto significa que tendrá una relación padre -> hijo, o lo contrario (menos común).

Puedo pensar en la implementación de un árbol binario, o un B-Tree. Apenas veo cómo obtener una matriz adecuada, por ejemplo.

Por otro lado, estoy de acuerdo en que sería genial tener sistemas eficientes en entornos de subprocesos múltiples.

+1

Las referencias cíclicas no son un problema dentro de la estructura de datos (el árbol binario, en su ejemplo). En una recopilación persistente, los nodos NO PUEDEN tener una referencia a su padre; si lo hicieran, significaría que el árbol completo se invalidaría en cada escritura. –

+0

@JoshuaWarner: Estoy de acuerdo, hablo en el siguiente párrafo pero no lo llevé a su conclusión evidente: no es posible un ciclo (si está bien construido) y sin ciclos un esquema 'shared_ptr' es completamente suficiente y no hay necesidad de un recolector de basura en toda regla. –

1

Hice mi propia versión, pero está la immer library como un ejemplo bastante completo y está específicamente inspirada en clojure. Me emocioné y me remonté unos años atrás después de escuchar un discurso de John Carmack en el que estaba saltando sobre el tren de la programación funcional. Parecía ser capaz de imaginar un motor de juego que girara alrededor de estructuras de datos inmutables. Si bien no entró en detalles y aunque parecía una idea nebulosa en su cabeza, el hecho de que lo estuviera considerando seriamente y no pareciera pensar que la sobrecarga reduciría abruptamente las tasas de fotogramas fue suficiente para entusiasmarme. sobre explorar esa idea

De hecho, lo uso como algo así como un detalle de optimización que puede parecer paradójico (hay sobrecarga a la inmutabilidad), pero me refiero a un contexto específico. Si quiero absolutamente para hacer esto:

// We only need to change a small part of this huge data structure. 
HugeDataStructure transform(HugeDataStructure input); 

... y yo absolutamente no quiero la función de causar efectos secundarios para que pueda ser flujos seguros y nunca propensos al mal uso, entonces no tengo otra opción pero para copiar la enorme estructura de datos (que puede abarcar un gigabyte).

Y allí encuentro que tener una pequeña biblioteca de estructuras de datos inmutables es inmensamente útil en ese contexto, ya que hace que el escenario anterior sea relativamente barato solo copiando poco y haciendo referencias a partes sin cambios.Dicho esto, que en su mayoría sólo tiene que utilizar una estructura de datos inmutables que es básicamente una secuencia de acceso aleatorio, así:

enter image description here

Y como han mencionado otros, se requería algún tipo de atención y puesta a punto y pruebas completas y muchos VTune sesiones para hacerlo seguro y eficiente, pero después de ponerme el codo de grasa, definitivamente hizo las cosas mucho más fáciles.

Además de la seguridad automática de hilos cada vez que utilizamos estas estructuras para escribir funciones libres de efectos secundarios, también obtenemos cosas como edición no destructiva, sistemas de deshacer triviales, excepción de seguridad trivial (no hay necesidad de retroceder) efectos a través de protectores de alcance en una función que no causa ninguno en rutas excepcionales), y dejar que los usuarios copien y peguen datos y lo instancian sin tomar mucha memoria hasta/a menos que modifiquen lo que pegan como una bonificación. De hecho, descubrí que estos bonos son aún más útiles a diario que la seguridad del hilo.

utilizo 'transitorios' (también conocido como 'constructores') como una forma de expresar los cambios en la estructura de datos, así:

Immutable transform(Immutable input) 
{ 
    Transient transient(input); 

    // make changes to mutable transient. 
    ... 

    // Commit the changes to get a new immutable 
    // (this does not touch the input). 
    return transient.commit(); 
} 

Incluso tengo una biblioteca de imágenes inmutable que utilizo para la edición de imágenes a trivializar la edición no destructiva. Se utiliza una estrategia similar a la estructura anterior mediante el tratamiento de imágenes como azulejos, así:

enter image description here

Cuando un transitorio se modifica y tenemos un nuevo inmutable, sólo las partes modificadas se hacen único. El resto de los azulejos son (índices solo 32 bits) de poca profundidad copiado:

enter image description here

hago uso de estos en las áreas de rendimiento bastante críticos como malla y procesamiento de vídeo. Hubo un poco de ajuste en cuanto a la cantidad de datos que debería almacenar cada bloque (demasiado y desperdiciamos el procesamiento y la memoria al copiar demasiados datos, muy poco y desperdiciamos el procesamiento y la memoria, copiando demasiados punteros con bloqueos de hilo más frecuentes).)

No los utilizo para raytracing ya que es una de las áreas de rendimiento crítico más extremas imaginables y los gastos indirectos más pequeños son notables para los usuarios (en realidad comparan y notan diferencias de rendimiento en el rango de 2%). pero la mayoría de las veces, son lo suficientemente eficientes, y es una gran ventaja cuando puedes copiar estas enormes estructuras de datos en general para simplificar la seguridad del hilo, deshacer sistemas, edición no destructiva, etc., sin preocuparte sobre el uso explosivo de la memoria y las demoras notables que se gastaron al copiar todo profundamente.