scala - haskell functional programming
Lista de omisión concurrente puramente funcional (4)
Las listas de omisión (Pugh, 1990) proporcionan diccionarios ordenados con operaciones de tiempo logarítmico como los árboles de búsqueda, pero las listas de omisión son mucho más susceptibles de actualizaciones concurrentes .
¿Es posible crear una lista de omisión concurrente puramente funcional eficiente? Si no, ¿es posible crear algún tipo de diccionario ordenado concurrente puramente funcional eficiente?
La propiedad de las listas de omisión que las hace buenas para las actualizaciones concurrentes (es decir, que la mayoría de las sumas y restas son locales) también las hace malas para la inmutabilidad (es decir, que muchos de los elementos anteriores en la lista apuntan finalmente a los elementos posteriores, y tendrían que ser cambiado).
Específicamente, las listas de salto consisten en estructuras que se ven así:
NODE1 ---------------------> NODE2 ---------...
| |
V V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...
Ahora, si tiene una actualización que, por ejemplo, elimina NODE2b o NODE1b , puede encargarse de ella de manera muy local: simplemente apunta 2a a 2c o 1a a 2a respectivamente y listo. Desafortunadamente, debido a que todos los nodos de hoja apuntan uno a otro, no es una buena estructura para una actualización funcional (inmutable).
Por lo tanto, las estructuras de los árboles son mejores para la inmutabilidad (ya que el daño siempre está limitado localmente, solo el nodo que le interesa y sus padres directos a través de la raíz del árbol).
Las actualizaciones simultáneas no funcionan bien con estructuras de datos inmutables. Si lo piensas bien, cualquier solución funcional tiene una actualización de A como f(A) . Si desea dos actualizaciones, una dada por f y otra dada por g , prácticamente debe hacer f(g(A)) g(f(A)) , o debe interceptar las solicitudes y crear una nueva operación h = f,g que puedes aplicar de una sola vez (o tienes que hacer otras cosas muy inteligentes).
Sin embargo, las lecturas simultáneas funcionan fantásticamente bien con estructuras de datos inmutables, ya que se garantiza que no habrá cambio de estado. Si no asume que puede tener un bucle de lectura / escritura que se resuelve antes de que cualquier otra escritura pueda interrumpir, entonces nunca tendrá que bloquear la lectura.
Por lo tanto, las estructuras de datos pesados de escritura probablemente se implementan mejor de manera mudable (y con algo como una lista de omisión donde solo es necesario bloquear localmente), mientras que las estructuras de datos pesados de lectura probablemente se implementan de manera inmutable (donde un árbol es una estructura de datos más natural). ).
La solución de Andrew McKinlay es la verdadera solución funcional "verdadera" para una verdadera lista de saltos aquí, pero tiene un inconveniente. Usted paga tiempo logarítmico para acceder a un elemento, pero ahora la mutación más allá del elemento principal se vuelve desesperada. ¡La respuesta que quieres está enterrada en innumerables copias de ruta!
¿Podemos hacerlo mejor?
Parte del problema es que hay múltiples rutas desde el infinito a tu elemento.
Pero si piensa a través de los algoritmos para buscar en una lista de omisión, nunca use ese hecho.
Podemos pensar que cada nodo en el árbol tiene un enlace preferido, el enlace que está más arriba desde la izquierda, que en cierto sentido se puede considerar como "dueño" de esa entrada.
Ahora podemos considerar la noción de "dedo" en una estructura de datos, que es una técnica funcional que le permite concentrarse en un elemento en particular y proporcionar una ruta de regreso a la raíz.
Ahora podemos empezar con una simple lista de saltos.
-inf-------------------> 16
-inf ------> 8 --------> 16
-inf -> 4 -> 8 -> 12 --> 16
Ampliándola por nivel:
-inf-------------------> 16
| |
v v
-inf ------> 8 --------> 16
| | |
v v v
-inf -> 4 -> 8 -> 12 --> 16
Eliminar todos los punteros excepto los preferidos:
-inf-------------------> 16
| |
v v
-inf ------> 8 16
| | |
v v v
-inf -> 4 8 -> 12 16
Luego, puede mover un ''dedo'' a la posición 8 siguiendo todos los indicadores que tendría que voltear para llegar allí.
-inf ------------------> 16
^ |
| v
-inf <------ 8 16
| | |
v v v
-inf -> 4 8 -> 12 16
Desde allí es posible eliminar 8, empujando el dedo en otro lugar, y puede continuar navegando a través de la estructura con el dedo.
Visto de esta manera, podemos ver que las rutas privilegiadas en una lista de salto forman un árbol de expansión.
Mover 1 paso con el dedo es una operación O (1) si solo tiene punteros privilegiados en el árbol y usa "nodos delgados" como este. Si usó nodos gruesos, entonces el movimiento del dedo hacia la izquierda / derecha sería potencialmente más costoso.
Todas las operaciones siguen siendo O (log n) y puede utilizar una estructura aleatoria de lista de omisión o una determinista como de costumbre.
Dicho esto, cuando dividimos la lista de omisión en una noción de una ruta preferida, obtenemos que una lista de omisión es solo un árbol con algunos enlaces redundantes no preferidos que no necesitamos para insertar / buscar / eliminar, de manera que La longitud de cada una de esas rutas desde la parte superior derecha es O (log n) con alta probabilidad o garantizada dependiendo de su estrategia de actualización.
Incluso sin el dedo, puede mantener O (log n) el tiempo esperado por inserción / eliminación / actualización 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 in situ. Siempre se produce una cosa nueva. En cierto sentido, las actualizaciones funcionales concurrentes son fáciles. ¡Todos tienen su propia respuesta! Simplemente no pueden ver a los demás.
No es una lista de omisión, pero parece coincidir con la descripción del problema: los árboles rojo-negro persistentes de Clojure (ver PersistentTreeMap.java ). La fuente contiene este aviso:
/**
* 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 mantienen el orden de los elementos y son "persistentes" en el sentido en que Rich Hickey usa la palabra (inmutable y capaz de mantener sus garantías de rendimiento cuando se construyen versiones actualizadas).
En caso de que quiera jugar con ellos, puede construir instancias en código Clojure con la función sorted-map .
Si solo necesita contras en el frente de la lista de omisión, entonces debería ser posible hacer una versión inmutable persistente.
La ventaja de este tipo de lista de omisión sería el acceso "aleatorio". por ejemplo, podría acceder al elemento n ''más rápido de lo que podría en una lista enlazada única regular.