algorithm - robinson - Omitir lista contra árbol de búsqueda binaria
por que se llama lista robinson (7)
Además, además de las respuestas dadas (facilidad de implementación combinada con un rendimiento comparable a un árbol equilibrado). Encuentro que implementar un cruce en orden (hacia adelante y hacia atrás) es mucho más simple porque una lista de omisiones tiene una lista vinculada dentro de su implementación.
Recientemente me encontré con la estructura de datos conocida como lista de omisiones . Parece tener un comportamiento muy similar a un árbol de búsqueda binario.
¿Por qué querrías usar una lista de omisiones en un árbol de búsqueda binario?
Del artículo de Wikipedia que citó:
Θ (n) operaciones, que nos obligan a visitar cada nodo en orden ascendente (como la impresión de la lista completa) ofrecen la oportunidad de realizar una desmarcación aleatoria de la estructura de niveles de la lista de omisiones de una manera óptima, llevando la lista de omisiones al tiempo de búsqueda O (log n). [...] Una lista de omisiones, sobre la cual no hemos realizado recientemente [ninguna de tales] Θ (n) operaciones, no proporciona las mismas garantías absolutas de rendimiento en el peor caso que las estructuras de datos de árbol balanceadas más tradicionales , porque siempre es posible (aunque con muy baja probabilidad) de que los saltos de moneda usados para construir la lista de saltos produzcan una estructura mal equilibrada
EDITAR: así que es una solución de compromiso: las listas de salto usan menos memoria con el riesgo de que degeneren en un árbol desequilibrado.
En la práctica, he descubierto que el rendimiento del árbol B en mis proyectos ha resultado ser mejor que las listas de omisiones. Las listas de omisiones parecen más fáciles de entender, pero la implementación de un árbol B no es tan difícil.
La única ventaja que conozco es que algunas personas inteligentes han resuelto cómo implementar una lista de omisiones concurrentes sin bloqueos que solo usa operaciones atómicas. Por ejemplo, Java 6 contiene la clase ConcurrentSkipListMap, y puede leer el código fuente si está loco.
Pero tampoco es demasiado difícil escribir una variante simultánea del árbol B, lo he visto hacer otra persona, si divides preventivamente y fusionas nodos "por si acaso" mientras caminas por el árbol, entonces no tendrás que preocúpate por los interbloqueos y solo tendrás que mantener un bloqueo en dos niveles del árbol a la vez. La sobrecarga de sincronización será un poco más alta, pero el árbol B probablemente sea más rápido.
En primer lugar, no se puede comparar de forma justa una estructura de datos aleatorizados con una que ofrezca las mejores garantías posibles.
Una lista de omisiones es equivalente a un árbol de búsqueda binaria aleatoriamente equilibrado (RBST) de la manera que se explica con más detalle en "Exploración de la dualidad entre las listas de omisiones y los árboles de búsqueda binaria" de Dean y Jones.
A la inversa, también puede tener listas de omisiones deterministas que garanticen el peor de los casos, cf. Munro et al.
En contraste con lo que algunos afirman anteriormente, puede tener implementaciones de árboles de búsqueda binaria (BST) que funcionan bien en la programación concurrente. Un posible problema con las BST centradas en la concurrencia es que no puede obtener las mismas garantías de equilibrado que tendría con un árbol rojo-negro (RB). (Pero las listas de omisiones "estándar", es decir, randomzided, tampoco le otorgan estas garantías.) Existe una relación entre mantener el equilibrio en todo momento y un acceso concurrente bueno (y fácil de programar), por lo que normalmente se utilizan árboles RB relajados. cuando se desea buena concurrencia. La relajación consiste en no volver a equilibrar el árbol de inmediato. Para una encuesta un tanto anticuada (1998), vea "El rendimiento de los algoritmos concurrentes del árbol rojo-negro" de [ps.gz] .
Una de las mejoras más recientes sobre estos es el llamado árbol cromático (básicamente, usted tiene un peso tal que el negro sería 1 y el rojo sería cero, pero también permite valores intermedios). ¿Y cómo funciona un árbol cromático contra la lista de omisiones? Veamos lo que Brown et al. "Una técnica general para árboles sin bloqueo" (2014) tiene que decir:
con 128 hilos, nuestro algoritmo supera al skiplist de no bloqueo de Java en un 13% a 156%, el árbol AVL basado en bloqueo de Bronson et al. en un 63% a 224%, y un RBT que usa la memoria transaccional de software (STM) de 13 a 134 veces
EDITAR para agregar: la lista de saltos basada en bloqueo de Pugh, que se evaluó en Fraser y Harris (2007) "Programación simultánea sin bloqueo" se acercó a su propia versión sin bloqueo (un punto ampliamente insistido en la respuesta principal aquí), también se ajusta para una buena operación simultánea, cf. "Mantenimiento simultáneo de listas de salto" de Pugh, aunque de una manera más bien leve. Sin embargo, un artículo más reciente / 2009 "A Simple Optimistic skip-list Algorithm" de Herlihy et al., Que propone una implementación supuestamente más simple (que Pugh) de listas de omisiones simultáneas, criticó a Pugh por no proporcionar una prueba de corrección suficientemente convincente para ellos. Dejando de lado este (quizás demasiado pedante) escrúpulo, Herlihy et al. Demuestra que su implementación más simple basada en un bloqueo de una lista de omisiones no se puede escalar realmente, así como la implementación sin bloqueos del JDK, pero solo para una alta contención (50% insertos, 50% de eliminaciones y 0% de búsquedas) ... que Fraser y Harris no hizo ninguna prueba; Fraser y Harris solo probaron el 75% de las búsquedas, el 12.5% de las inserciones y el 12.5% las eliminaciones (en la lista de omisiones con ~ 500K elementos). La implementación más simple de Herlihy et al. también se acerca a la solución sin bloqueo del JDK en el caso de baja contención que probaron (70% de búsquedas, 20% de inserción, 10% de eliminación); en realidad superaron la solución sin bloqueo para este escenario cuando hicieron su lista de omisiones lo suficientemente grande, es decir, yendo de 200K a 2M elementos, por lo que la probabilidad de contención en cualquier bloqueo se volvió insignificante. Hubiera sido bueno si Herlihy et al. había superado su suspensión por las pruebas de Pugh y también había probado su implementación, pero lamentablemente no lo hicieron.
EDIT2: Encontré una (motherboard) de todos los benchmarks (2015) de Gramoli: "Más de lo que siempre quiso saber sobre sincronización. Synchrobench, midiendo el impacto de la sincronización en algoritmos concurrentes" : Aquí hay una imagen extractada relevante para esta pregunta.
"Algo.4" es un precursor (más antiguo, versión 2011) de Brown et al. Mencionado anteriormente. (No sé cuánto mejor o peor es la versión 2014). "Algo.26" es Herlihy mencionado anteriormente; como puede ver, se arruina con las actualizaciones, y mucho peor con las CPU Intel utilizadas aquí que con las CPU Sun del documento original. "Algo.28" es ConcurrentSkipListMap del JDK; no funciona tan bien como se esperaba en comparación con otras implementaciones de listas de saltos basadas en CAS. Los ganadores bajo alta contención son "Algo.2" un algoritmo basado en bloqueo (!!) descrito por Crain et al. en "Un árbol de búsqueda binaria compatible con la contención " y "Algo.30" es el "skiplist rotativo" de "Estructuras de datos logarítmicos para multinúcleos" . "Algo.29" es la "lista de omisiones sin bloqueo de puntos calientes" . Tenga en cuenta que Gramoli es coautor de los tres artículos de este algoritmo ganador. "Algo.27" es la implementación en C ++ de la lista de omisiones de Fraser.
La conclusión de Gramoli es que es mucho más fácil arruinar una implementación de árbol concurrente basada en CAS que atornillar una lista de omisiones similar. Y según las cifras, es difícil estar en desacuerdo. Su explicación para este hecho es:
La dificultad en el diseño de un árbol que está libre de bloqueos surge de la dificultad de modificar referencias múltiples atómicamente. Las listas de omisiones consisten en torres vinculadas entre sí a través de punteros sucesores y en las que cada nodo apunta al nodo inmediatamente debajo de él. A menudo se consideran similares a los árboles porque cada nodo tiene un sucesor en la torre sucesora y debajo de él, sin embargo, una distinción importante es que el puntero descendente es generalmente inmutable, lo que simplifica la modificación atómica de un nodo. Esta distinción es probablemente la razón por la cual las listas de omisiones superan a los árboles bajo fuerte contención como se observa en la Figura [arriba].
Anular esta dificultad fue una preocupación clave en el trabajo reciente de Brown et al. Tienen un documento completo separado (2013) "Primitivos pragmáticos para estructuras de datos sin bloqueo" para crear "primitivas" compuestas LL / SC de múltiples registros, que denominan LLX / SCX, que se implementan utilizando CAS (a nivel de máquina). Brown y col. utilizaron este elemento esencial LLX / SCX en su implementación de árbol simultáneo 2014 (pero no en su 2011).
Creo que quizás también valga la pena resumir aquí las ideas fundamentales de la lista de omisiones "sin puntos críticos" / contención amigable (CF) . Admite una idea esencial de los árboles RB relajados (y estructuras de datos de congruencia similar): las torres ya no se construyen inmediatamente después de la inserción, sino que se retrasan hasta que haya menos contención. Por el contrario, la eliminación de una torre alta puede crear muchas disputas; esto se remonta al documento de skip-list concurrente de Pugh de 1990, que es la razón por la cual Pugh introdujo la inversión del puntero en la eliminación (un tidbit que la página de Wikipedia sobre listas de omisiones todavía no menciona, por desgracia). La lista de omisiones de CF lleva esto un paso más allá y retrasa la eliminación de los niveles superiores de una torre alta. Ambos tipos de operaciones diferidas en las listas de omisiones de CF se llevan a cabo mediante un subproceso similar al colector de basura separado (CAS), que sus autores denominan "subproceso de adaptación".
El código de Synchrobench (que incluye todos los algoritmos probados) está disponible en: https://github.com/gramoli/synchrobench . El último Brown et al. la implementación (no incluida en el anterior) está disponible en http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java ¿Alguien tiene una máquina central de 32+ disponible? J / K Mi punto es que pueden ejecutar esto ustedes mismos.
Las listas de omisión se implementan mediante listas.
Existen soluciones de bloqueo para listas unidas y doblemente vinculadas, pero no existen soluciones sin bloqueo que utilicen directamente CAS solo para cualquier estructura de datos O (logn).
Sin embargo, puede usar listas basadas en CAS para crear listas de omisiones.
(Tenga en cuenta que el MCAS, que se crea utilizando CAS, permite estructuras de datos arbitrarias y se ha creado una prueba de concepto árbol rojo-negro utilizando MCAS).
Por extraño que sea, resultan ser muy útiles :-)
Las listas de omisiones son más susceptibles de acceso / modificación concurrente. Herb Sutter escribió un article sobre la estructura de datos en entornos concurrentes. Tiene más información en profundidad.
La implementación más utilizada de un árbol de búsqueda binaria es un árbol rojo-negro . Los problemas concurrentes surgen cuando se modifica el árbol que a menudo necesita reequilibrar. La operación de reequilibrio puede afectar grandes porciones del árbol, lo que requeriría un bloqueo mutex en muchos de los nodos de árbol. Insertar un nodo en una lista de omisiones está mucho más localizado, solo los nodos directamente vinculados al nodo afectado deben estar bloqueados.
Actualización de los comentarios de Jon Harrops
Leí la última programación en papel de Fraser y Harris Simultánea sin cerraduras . Cosas realmente buenas si le interesan las estructuras de datos sin bloqueo. El documento se centra en la memoria transaccional y una operación teórica de MCM multipaya, comparar y cambiar. Ambos se simulan en software ya que ningún hardware los admite todavía. Estoy bastante impresionado de que hayan podido construir MCAS en software.
No encontré el material de memoria transaccional particularmente convincente, ya que requiere un recolector de basura. Además , la memoria transaccional del software está plagada de problemas de rendimiento. Sin embargo, estaría muy entusiasmado si la memoria transaccional de hardware alguna vez se vuelve común. Al final, sigue siendo una investigación y no será útil para el código de producción durante una década más o menos.
En la sección 8.2, comparan el rendimiento de varias implementaciones de árbol simultáneas. Resumiré sus hallazgos. Vale la pena descargar el pdf, ya que tiene algunos gráficos muy informativos en las páginas 50, 53 y 54.
- Las listas de omisiones de bloqueo son increíblemente rápidas. Se escalan increíblemente bien con la cantidad de accesos simultáneos. Esto es lo que hace que las listas de omisiones sean especiales, otras estructuras de datos basadas en bloqueo tienden a croar bajo presión.
- Las listas de omisiones sin cerradura son consistentemente más rápidas que las listas de omisiones de bloqueo, pero apenas.
- las listas de omisiones transaccionales son consistentemente 2-3 veces más lentas que las versiones de bloqueo y sin bloqueo.
- el bloqueo de árboles rojo-negro croa bajo acceso simultáneo. Su rendimiento se degrada linealmente con cada nuevo usuario concurrente. De las dos implementaciones conocidas de bloqueo de árbol rojo-negro, una tiene esencialmente un bloqueo global durante el reequilibrio de árbol. El otro usa escalada de bloqueo sofisticada (y complicada) pero aún no supera significativamente la versión de bloqueo global.
- los árboles rojo-negro sin cerradura no existen (ya no es cierto, ver Actualización).
- los árboles rojos-negros transaccionales son comparables con las listas de saltos transaccionales. Eso fue muy sorprendente y muy prometedor. Memoria transaccional, aunque más lenta si es mucho más fácil de escribir. Puede ser tan fácil como buscar rápidamente y reemplazar en la versión no concurrente.
Actualizar
Aquí hay un documento sobre árboles sin cerrojo : Árboles rojo-negro sin candado usando CAS .
No lo he investigado a fondo, pero en la superficie parece sólido.
Las listas de salto tienen la ventaja de eliminar el bloqueo. Pero, el tiempo de ejecución depende de cómo se decida el nivel de un nuevo nodo. Usualmente esto se hace usando Random (). En un diccionario de 56000 palabras, la lista de saltos tomó más tiempo que un árbol desplegable y el árbol tomó más tiempo que una tabla hash. Los primeros dos no pudieron coincidir con el tiempo de ejecución de la tabla hash. Además, la matriz de la tabla hash se puede bloquear también de forma simultánea.
Skip List y listas ordenadas similares se usan cuando se necesita una referencia. Por ejemplo: encontrar vuelos al lado y antes de una fecha en una aplicación.
Un árbol binario de búsqueda binaria inmemory es excelente y se usa con mayor frecuencia.
Omitir lista Vs Splay Tree Vs Hash Table Runtime en el diccionario find op