c++ - sistema - Implementación eficiente de montones binarios
programa en c++ que convierta de decimal a binario y viceversa (4)
Estoy buscando información sobre cómo implementar montones binarios de manera eficiente. Siento que debería haber un buen artículo en algún lugar sobre la implementación de montones de manera eficiente, pero no he encontrado ninguno. De hecho, no he podido encontrar ningún recurso sobre la cuestión de la implementación eficiente más allá de lo básico, como almacenar el montón en una matriz. Estoy buscando técnicas para hacer un montón binario rápido más allá de los que describo a continuación.
Ya escribí una implementación en C ++ que es más rápida que la de Microsoft Visual C ++ y la std :: priority_queue de GCC o usando std :: make_heap, std :: push_heap y std :: pop_heap. Las siguientes son las técnicas que ya he cubierto en mi implementación. Solo se me ocurrieron los 2 últimos, aunque dudo que esas sean ideas nuevas:
(Editar: sección añadida sobre la optimización de la memoria)
Mira las notas de implementación de Wikipedia para montones binarios. Si la raíz del montón se coloca en el índice 0, las fórmulas para padre, hijo izquierdo y derecho del nodo en el índice n son respectivamente (n-1) / 2, 2n + 1 y 2n + 2. Si utiliza una matriz basada en 1, las fórmulas se convierten en las más simples n / 2, 2n y 2n + 1. Por lo tanto, los padres y el hijo izquierdo son más eficientes cuando se utiliza una matriz basada en 1. Si p apunta a una matriz basada en 0 y q = p - 1, entonces podemos acceder a p [0] como q [1] para que no exista una sobrecarga en el uso de una matriz basada en 1.
Pop en un montón se describe con frecuencia reemplazando el elemento superior por la hoja inferior más a la izquierda y luego moviéndolo hacia abajo hasta que se restaura la propiedad del montón. Esto requiere 2 comparaciones por nivel por lo que vamos, y es probable que bajemos mucho desde que movimos una hoja a la cima del montón. Entonces, deberíamos esperar un poco menos de 2 comparaciones de log n.
En cambio, podemos dejar un agujero en el montón donde estaba el elemento superior. Luego movemos ese agujero por el montón moviendo de forma iterativa al niño más grande. Esto requiere solo 1 comparación por nivel que pasemos. De esta manera, el agujero se convertirá en una hoja. En este punto podemos mover la hoja inferior derecha a la posición del agujero y mover ese valor hasta que se restablezca la propiedad de pila. Como el valor que movimos era una hoja, no esperamos que se mueva muy arriba en el árbol. Entonces, deberíamos esperar un poco más que log n comparaciones, que es mejor que antes.
Supongamos que desea eliminar el elemento máximo y también insertar un nuevo elemento. Luego puede hacer cualquiera de las implementaciones de eliminación / extracción descritas anteriormente, pero en lugar de mover la hoja inferior derecha, utiliza el nuevo valor que desea insertar / presionar. (Cuando la mayoría de las operaciones son de este tipo, he descubierto que un árbol de torneo es mejor que un montón, pero por lo demás, el montón es un poco mejor).
Las fórmulas padre, hijo izquierdo y derecho trabajan en índices y no se puede hacer que funcionen directamente en valores de puntero. Entonces, vamos a trabajar con índices y eso implica buscar valores p [i] en una matriz p de un índice i. Si p es un T * ei es un número entero, entonces
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i
y el compilador tiene que realizar este cálculo para obtener p [i]. sizeof (T) es una constante en tiempo de compilación, y la multiplicación se puede hacer de manera más eficiente si sizeof (T) es una potencia de dos. Mi implementación se hizo más rápida al agregar 8 bytes de relleno para aumentar sizeof (T) de 24 a 32. La eficiencia reducida de la caché probablemente significa que esto no es una ganancia para conjuntos de datos lo suficientemente grandes.
Esto fue un aumento del 23% en el rendimiento en mi conjunto de datos. Lo único que hacemos con un índice que no sea encontrar padre, hijo izquierdo y derecho es buscar el índice en una matriz. Entonces, si hacemos un seguimiento de j = sizeof (T) * i en lugar de un índice i, entonces podríamos hacer una búsqueda p [i] sin la multiplicación que de otro modo está implícita en la evaluación de p [i] porque
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i == static_cast<char*>(p) + j
Entonces, las fórmulas izquierda-derecha e infantil para valores j se convierten respectivamente en 2 * j y 2 * j + sizeof (T). La fórmula principal es un poco más complicada, y no he encontrado una manera de hacerlo, aparte de convertir el valor j en un valor i y regresar así:
parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T)
Si sizeof (T) es una potencia de 2, entonces se compilará en 2 turnos. Eso es 1 operación más que el padre habitual usando índices i. Sin embargo, guardamos 1 operación en la búsqueda. Entonces, el efecto neto es que encontrar al padre toma la misma cantidad de tiempo de esta manera, mientras que la búsqueda del hijo izquierdo y derecho se vuelve más rápida.
Las respuestas de TokenMacGuy y templatetypedef señalan las optimizaciones basadas en memoria que reducen las fallas de caché. Para conjuntos de datos muy grandes o colas de prioridad utilizadas con poca frecuencia, el SO puede intercambiar partes de la cola al disco. En ese caso, vale la pena agregar una gran cantidad de sobrecarga para hacer un uso óptimo de la memoria caché, ya que el intercambio desde el disco es muy lento. Mis datos se ajustan fácilmente a la memoria y se usan continuamente, por lo que es probable que ninguna parte de la cola se intercambie al disco. Sospecho que este es el caso para la mayoría de los usos de las colas de prioridad.
Hay otras colas de prioridad que están diseñadas para hacer un mejor uso de la memoria caché de la CPU. Por ejemplo, un 4-heap debería tener menos errores de caché y la cantidad de sobrecarga adicional no es mucho. LaMarca y Ladner informan en 1996 que obtienen un 75% de mejora en el rendimiento de ir a 4 montones alineados. Sin embargo, Hendriks informa en 2010 que:
También se probaron las mejoras en el montón implícito sugerido por LaMarca y Ladner [17] para mejorar la ubicación de los datos y reducir las fallas de caché. Implementamos un montón de cuatro vías, que de hecho muestra una consistencia un poco mejor que el montón de dos vías para datos de entrada muy sesgados, pero solo para tamaños de cola muy grandes. El montón jerárquico maneja mejor los tamaños de cola muy grandes.
¿Hay más técnicas que estas?
Como una elaboración en la publicación de @ TokenMacGuy, es posible que desee buscar en las estructuras de datos ajenas a la caché . La idea es construir estructuras de datos que, para sistemas de almacenamiento en caché arbitrarios, minimicen la cantidad de errores de caché. Son complicados, pero en realidad podrían ser útiles desde su punto de vista, ya que funcionan bien incluso cuando se trata de sistemas de caché de varias capas (por ejemplo, registros / L1 / L2 / VM).
De hecho, hay un documento que detalla una cola de prioridad de memoria caduca óptima que podría ser de interés. Esta estructura de datos tendría todo tipo de ventajas en términos de velocidad, ya que trataría de minimizar el número de errores de caché en cada nivel.
En el primer punto: incluso tener un "espacio libre" para su implementación basada en arreglos no es un desperdicio. Muchas operaciones necesitan un elemento temporal de todos modos. En lugar de inicializar un elemento nuevo cada vez, tener un elemento dedicado en el índice [0] es útil.
No sé si te perdiste este enlace en la página wiki de Binary Heap o si decidiste que no vale la pena, pero de cualquier forma: http://en.wikipedia.org/wiki/B-heap
Un artículo / artículo interesante sobre este tema considera el comportamiento del almacenamiento en caché / paginación en el diseño general del montón; La idea es que es mucho más costoso pagar una falta de caché o una página en casi cualquier otra parte de la implementación de una estructura de datos. El documento analiza un diseño de montón que aborda esto.