data-structures - utilizan - programming styles

¿Cómo se logra la manipulación no destructiva y eficiente de la memoria de las colecciones en la programación funcional?

Question

Estoy tratando de descubrir cómo la manipulación no destructiva de grandes colecciones se implementa en la programación funcional, es decir. cómo es posible alterar o eliminar elementos individuales sin tener que crear una colección completamente nueva donde todos los elementos, incluso los no modificados, se duplicarán en la memoria. (Incluso si la colección original se recolectara como basura, esperaría que la huella de memoria y el rendimiento general de tal colección sean terribles).

Esto es lo lejos que he llegado hasta ahora:

Usando F #, se me ocurrió una insert función que divide una lista en dos partes e introduce un nuevo elemento intermedio, aparentemente sin clonar todos los elementos sin cambios:

// return a list without its first n elements:
// (helper function)
let rec skip list n =
    if n = 0 then
        list
    else
        match list with
        | []    -> []
        | x::xs -> skip xs (n-1)

// return only the first n elements of a list:
// (helper function)
let rec take list n =
    if n = 0 then
        []
    else
        match list with
        | []    -> []
        | x::xs -> x::(take xs (n-1))

// insert a value into a list at the specified zero-based position:
let insert list position value =
    (take list position) @ [value] @ (skip list position)

Luego verifiqué si los objetos de una lista original son "reciclados" en listas nuevas usando Object.ReferenceEquals de .NET:

open System

let (===) x y =
    Object.ReferenceEquals(x, y)

let x = Some(42)
let L = [Some(0); x; Some(43)]
let M = Some(1) |> insert L 1

Todas las siguientes tres expresiones se evalúan como true , lo que indica que el valor al que se refiere x se reutiliza tanto en las listas L como en M , es decir. que solo hay 1 copia de este valor en la memoria:

L.[1] === x
M.[2] === x
L.[1] === M.[2]

Mi pregunta:

¿Usualmente los lenguajes de programación funcionales reutilizan valores en lugar de clonarlos en una nueva ubicación de memoria, o tuve suerte con el comportamiento de F #? Asumiendo lo primero, ¿es así como la edición de colecciones razonablemente eficiente en memoria se puede implementar en la programación funcional?

(Por cierto: sé sobre el libro de Chris Okasaki. Estructuras de datos puramente funcionales , pero todavía no he tenido tiempo de leerlo a fondo).

Answer 1

Cómo es posible alterar o eliminar elementos individuales sin tener que crear una colección completamente nueva donde todos los elementos, incluso los no modificados, se duplicarán en la memoria.

Esto funciona porque no importa qué tipo de colección, los punteros a los elementos se almacenan por separado de los elementos mismos. (Excepción: algunos compiladores optimizarán parte del tiempo, pero saben lo que están haciendo). Entonces, por ejemplo, puede tener dos listas que difieren solo en el primer elemento y comparten colas:

let shared = ["two", "three", "four"]
let l      = "one" :: shared
let l''     = "1a"  :: shared

Estas dos listas tienen la parte shared en común y sus primeros elementos son diferentes. Lo que es menos obvio es que cada lista también comienza con un par único, a menudo llamado "celda de cons":

• La lista l comienza con un par que contiene un puntero a "one" y un puntero a la cola compartida.

• La lista l'' comienza con un par que contiene un puntero a "1a" y un puntero a la cola compartida.

Si solo hubiéramos declarado l y quisiéramos alterar o eliminar el primer elemento para obtener l'' , haríamos esto:

let l'' = match l with
         | _ :: rest -> "1a" :: rest
         | []        ->  raise (Failure "cannot alter 1st elem of empty list")

Hay un costo constante

• Divide l en su cabeza y cola examinando la celda de cons.

• Asigne una nueva celda de cons que apunta a "1a" y la cola.

La nueva celda cons se convierte en el valor de la lista l'' .

Si realiza cambios puntuales en medio de una gran colección, normalmente utilizará algún tipo de árbol equilibrado que utilice el tiempo y el espacio logarítmico. Con menos frecuencia puede usar una estructura de datos más sofisticada:

• La cremallera de Gerard Huet se puede definir para casi cualquier estructura de datos similar a un árbol y se puede usar para atravesar y realizar modificaciones puntuales a un costo constante. Las cremalleras son fáciles de entender.

• Los árboles de dedo de Paterson e Hinze ofrecen representaciones de secuencias muy sofisticadas, que entre otros trucos le permiten cambiar elementos en el medio de manera eficiente, pero son difíciles de entender.

Answer 2

Estoy tratando de descubrir cómo la manipulación no destructiva de grandes colecciones se implementa en la programación funcional, es decir. cómo es posible alterar o eliminar elementos individuales sin tener que crear una colección completamente nueva donde todos los elementos, incluso los no modificados, se duplicarán en la memoria.

Esta página tiene algunas descripciones e implementaciones de estructuras de datos en F #. La mayoría de ellos provienen de Estructuras de datos puramente funcionales de Okasaki, aunque el árbol AVL es mi propia implementación, ya que no estaba presente en el libro.

Ahora, ya que preguntaste sobre la reutilización de nodos sin modificar, tomemos un árbol binario simple:

type ''a tree =
    | Node of ''a tree * ''a * ''a tree
    | Nil

let rec insert v = function
    | Node(l, x, r) as node ->
        if v < x then Node(insert v l, x, r)    // reuses x and r
        elif v > x then Node(l, x, insert v r)  // reuses x and l
        else node
    | Nil -> Node(Nil, v, Nil)

Tenga en cuenta que reutilizamos algunos de nuestros nodos. Digamos que comenzamos con este árbol:

Cuando insertamos una e en el árbol, obtenemos un árbol nuevo, con algunos de los nodos apuntando hacia atrás en nuestro árbol original:

Si no tenemos una referencia al árbol xs anterior, entonces .NET recogerá los nodos sin referencias en vivo, específicamente los nodos d , g f .

Tenga en cuenta que solo hemos modificado los nodos a lo largo de la ruta de nuestro nodo insertado . Esto es bastante típico en la mayoría de las estructuras de datos inmutables, incluidas las listas. Entonces, la cantidad de nodos que creamos es exactamente igual a la cantidad de nodos que necesitamos atravesar para insertar en nuestra estructura de datos.

¿Usualmente los lenguajes de programación funcionales reutilizan valores en lugar de clonarlos en una nueva ubicación de memoria, o tuve suerte con el comportamiento de F #? Asumiendo lo primero, ¿es así como la edición de colecciones razonablemente eficiente en memoria se puede implementar en la programación funcional?

Sí.

Las listas, sin embargo, no son una estructura de datos muy buena, ya que la mayoría de las operaciones no triviales en ellas requieren O (n) tiempo.

Los árboles binarios equilibrados admiten inserciones O (log n), lo que significa que creamos O (log n) copias en cada inserción. Como log ₂ (10 ^ 15) es ~ = 50, la sobrecarga es muy pequeña para estas estructuras de datos particulares. Incluso si mantiene alrededor de cada copia de cada objeto después de insertar / eliminar, su uso de memoria aumentará a una tasa de O (n log n), muy razonable, en mi opinión.

Answer 3

Me parece que su pregunta se trata principalmente de datos inmutables , no de idiomas funcionales per se . De hecho, los datos son necesariamente inmutables en código puramente funcional (véase transparencia referencial ), pero no conozco ningún lenguaje que no sea de juguete que imponga pureza absoluta en todas partes (aunque Haskell se acerca más, si le gusta ese tipo de cosas).

En términos generales, la transparencia referencial significa que no existe una diferencia práctica entre una variable / expresión y el valor que tiene / evalúa. Debido a que un dato inmutable (por definición) nunca cambiará, puede identificarse trivialmente con su valor y debe comportarse de manera indistinguible de cualquier otro dato con el mismo valor.

Por lo tanto, al elegir no establecer una distinción semántica entre dos datos con el mismo valor, no tenemos ninguna razón para construir deliberadamente un valor duplicado. Entonces, en casos de igualdad obvia (por ejemplo, agregar algo a una lista, pasarlo como un argumento de función, etc.), los idiomas en los que son posibles las garantías de inmutabilidad generalmente reutilizarán la referencia existente, como dices.

Del mismo modo, las estructuras de datos inmutables poseen una transparencia referencial intrínseca de su estructura (aunque no de sus contenidos). Suponiendo que todos los valores contenidos también son inmutables, esto significa que las piezas de la estructura también se pueden reutilizar de manera segura en las nuevas estructuras. Por ejemplo, la cola de una lista de contras a menudo se puede reutilizar; en tu código, esperaría que:

(skip 1 L) === (skip 2 M)

... también sería cierto.

Sin embargo, la reutilización no siempre es posible; la porción inicial de una lista eliminada por su función de skip no puede ser reutilizada, por ejemplo. Por la misma razón, agregar algo al final de una lista de contras es una operación costosa, ya que debe reconstruir una lista completamente nueva, similar al problema de la concatenación de cadenas terminadas en nulos.

En tales casos, los enfoques ingenuos se introducen rápidamente en el ámbito del rendimiento horrible que le preocupaba. A menudo, es necesario repensar sustancialmente los algoritmos fundamentales y las estructuras de datos para adaptarlos con éxito a datos inmutables. Las técnicas incluyen dividir estructuras en capas o piezas jerárquicas para aislar cambios, invertir partes de la estructura para exponer actualizaciones baratas a partes modificadas con frecuencia, o incluso almacenar la estructura original junto con una colección de actualizaciones y combinar las actualizaciones con el original sobre la marcha solamente cuando se accede a los datos

Ya que estás usando F # aquí, voy a asumir que al menos estás algo familiarizado con C #; el inestimable Eric Lippert tiene un montón de publicaciones sobre estructuras de datos inmutables en C # que probablemente te iluminarán mucho más allá de lo que yo podría proporcionar. A lo largo de varias publicaciones, demuestra implementaciones inmutables (razonablemente eficientes) de una pila, árbol binario y cola de doble extremo, entre otras. ¡Lectura encantadora para cualquier programador de .NET!

Answer 4

Puede estar interesado en estrategias de reducción de expresiones en lenguajes de programación funcionales. Un buen libro sobre el tema es The Implementation of Functional Programming Languages , de Simon Peyton Jones, uno de los creadores de Haskell. Eche un vistazo especialmente al siguiente capítulo Reducción de gráficos de Lambda Expressions ya que describe el uso compartido de subexpresiones comunes. Espero que ayude, pero me temo que solo se aplica a los lenguajes perezosos.

Answer 5

Si bien los objetos a los que se hace referencia son los mismos en su código, creo que el espacio de almacenamiento de las referencias es el mismo y la estructura de la lista se duplica por take . Como resultado, aunque los objetos a los que se hace referencia son los mismos, y las colas se comparten entre las dos listas, las "celdas" para las porciones iniciales se duplican.

No soy un experto en programación funcional, pero tal vez con algún tipo de árbol podría lograr la duplicación de solo elementos de registro (n), ya que tendría que volver a crear solo la ruta desde la raíz hasta el elemento insertado.