Lista de omisión simultánea puramente funcional

Question

Saltar listas (Pugh, 1990) proporcionan los diccionarios ordenados con logarítmica -time operaciones como los árboles de búsqueda, pero omitir las listas son mucho más susceptibles a concurrente actualizaciones .

¿Es posible crear una lista de omisión simultánea puramente funcional eficiente? Si no es así, ¿es posible crear cualquier tipo de diccionario ordenada concurrente puramente funcional eficiente?

Answer 1

La propiedad de las listas de salto que los hace buenos para actualizaciones simultáneas (es decir, que la mayoría de las adiciones y sustracciones son locales) también les hace mal para la inmutabilidad (es decir, que una gran cantidad de artículos anteriores en el punto de la lista, finalmente, a los artículos posteriores, y tendría que ser cambiado).

Específicamente, omitir listas consisten en estructuras que parecen tan:

NODE1 ---------------------> NODE2 ---------...
  |                           |
  V                           V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...

Ahora, si usted tiene una actualización que, por ejemplo, borra o NODE2b NODE1b, puede cuidar de él de forma muy local: sólo 2a punto a 2c o 1a a 2a respectivamente, y ya está. Por desgracia, debido a que la hoja de todos los nodos de un punto a otro, que no es una buena estructura para una actualización funcional (inmutable).

Por lo tanto, las estructuras de árbol son mejores para la inmutabilidad (ya que el daño se limita siempre a nivel local - sólo el nodo que se preocupan por sus padres y directos a través de la raíz del árbol)

.

actualizaciones simultáneas no funcionan bien con estructuras de datos inmutables. Si se piensa en ello, cualquier solución funcional tiene una actualización de A como f(A). Si quieres dos cambios, uno dado por f y uno dado por g, que bastante tienen que ver f(g(A)) o g(f(A)), o tiene que interceptar las peticiones y crear un nuevo h = f,g operación que se puede aplicar de una sola vez (o si tener que hacer varias otras cosas altamente inteligente).

Sin embargo, lecturas simultáneas de trabajo increíblemente bien con estructuras de datos inmutables ya que está garantizado para tener ningún cambio de estado. Si no asumir que se puede tener un bucle de lectura / escritura que resuelve antes que cualquier otra escritura pueden interrumpir, a continuación, que nunca tenga que bloquear en lectura.

Por lo tanto, las estructuras de datos de escritura-pesados ??son probablemente mejor implementada mutably (y con algo así como una lista de omisión en la que sólo necesita para bloquear de forma local), mientras que las estructuras de datos pesados ??de lectura son probablemente mejor implementados de manera inmutable (donde un árbol es un mayor estructura de datos natural).

Answer 2

La solución de Andrew McKinlay es la solución real "verdadero" funcional para un skip-list real aquí, pero tiene un inconveniente. Usted paga el tiempo logarítmica para acceder a un elemento, pero ahora mutación más allá del elemento de cabeza se vuelve inútil. La respuesta que quieres está enterrado en un sinnúmero de caminos copias!

¿Podemos hacerlo mejor?

Parte del problema es que hay múltiples rutas de -infinity a su artículo.

Pero si se piensa a través de los algoritmos para buscar en una skiplist, que nunca usa ese hecho.

puede pensar en cada nodo en el árbol como tener un enlace preferido, el enlace de más arriba a la misma desde la izquierda, que en cierto sentido se puede considerar como 'poseer' esa entrada.

Ahora podemos considerar la noción de un 'dedo' en una estructura de datos, que es una técnica funcional que le permite concentrarse en un elemento particular y suministrar una copia de ruta a la raíz.

Ahora podemos empezar con un simple salto-list

-inf-------------------> 16
-inf ------> 8 --------> 16
-inf -> 4 -> 8 -> 12 --> 16

expandiéndolo por nivel:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8 --------> 16
  |          |            |
  v          v            v
-inf -> 4 -> 8 -> 12 --> 16

Gaza a todos, excepto los punteros preferidos:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8           16
  |          |            |
  v          v            v
-inf -> 4    8 -> 12     16

A continuación, puede mover un 'dedo' a la posición 8 mediante el seguimiento de todos los punteros que tendría que dar la vuelta para llegar allí.

-inf ------------------> 16
   ^                      |
   |                      v
-inf <------ 8           16
   |         |            |
   v         v            v
-inf -> 4    8 -> 12     16

A partir de ahí, es posible eliminar 8, empujando con el dedo en otro lugar, y puede continuar a navegar a través de la estructura con el dedo.

Visto de esta manera, podemos ver que los caminos privilegiados en una lista de salto forman un árbol de expansión!

Moving 1 paso con el dedo es un (1) Operación O si sólo tiene punteros privilegiados en el árbol y utiliza las "nodos" flacos como este. Si utilizó nodos de grasa, entonces el movimiento del dedo hacia la izquierda / derecha sería potencialmente más caro.

Todas las operaciones se mantienen O (log n) y se puede utilizar una estructura de lista saltar aleatorios o un ser determinista, como de costumbre.

Dicho esto, cuando rompemos la skiplist abajo en una noción de un camino preferido entonces tenemos que skiplist es sólo un árbol con algunos enlaces redundantes no preferidas que no necesitamos para insertar / buscar / borrar, tal que la longitud de cada uno de esos caminos desde la parte superior derecha es o (log n), ya sea con alta probabilidad o garantizados dependiendo de su estrategia de actualización.

Incluso sin el dedo se puede mantener O (log n) esperado por insertar / actualizar / borrar en un árbol con este formulario.

Ahora, la palabra clave en su pregunta que no tiene sentido es "concurrente". Una estructura de datos puramente funcional no tiene una noción de mutación en el lugar. Siempre se producirá una nueva cosa. En cierto sentido actualizaciones funcionales concurrentes son fáciles. Todo el mundo tiene su propia respuesta! Ellos simplemente no pueden ver los demás.

Answer 3

No es una lista de salto, pero parece coincidir con la descripción del problema: la persistencia de árboles rojo-negro de Clojure (ver PersistentTreeMap.java ). La fuente incluya este mensaje:

/**
 * Persistent Red Black Tree
 * Note that instances of this class are constant values
 * i.e. add/remove etc return new values
 * <p/>
 * See Okasaki, Kahrs, Larsen et al
 */

Estos árboles mantener el orden de los elementos y son "persistentes" en el sentido en que Rich Hickey usa la palabra (inmutable y capaces de mantener sus garantías de rendimiento como versiones actualizadas se construyen).

En caso de que quiera jugar con ellos, se puede construir ejemplos en código Clojure con el sorted-map función.

Answer 4

Si sólo necesita a los contras en el frente de la lista de salto, entonces debería ser posible hacer una versión inmutable persistente.

La ventaja de este tipo de lista de salto sería el acceso "al azar". p.ej. Se podía acceder al enésimo elemento más rápido de lo que podía en una sola lista enlazada regular.