Envase de cola más rápido (C++)

Question

Estoy usando cola y cola de prioridad, a través de la cual planeo bombear una gran cantidad de datos con bastante rapidez.

Por lo tanto, quiero que mis q y pq respondan a sumas y restas.

¿Cuáles son los méritos relativos de usar un vector, lista o deque como el contenedor subyacente?

Actualización: En el momento de escribir estas líneas, vale la pena leer las respuestas de Mike Seymour y Steve Townsend a continuación. ¡Gracias a ambos!

Answer 1

La única manera de estar seguro de cómo el rendimiento de los efectos de elección es medirlo, en una situación similar a la de los casos de uso esperados. Dicho esto, he aquí algunas observaciones:

Para std::queue:

• std::deque es generalmente la mejor opción; admite todas las operaciones necesarias en tiempo constante y asigna memoria en fragmentos a medida que crece.
• std::list también admite las operaciones necesarias, pero puede ser más lento debido a más asignaciones de memoria; en circunstancias especiales, es posible que pueda obtener buenos resultados asignando desde un grupo de objetos dedicado, pero eso no es del todo sencillo.
• std::vector no se puede utilizar, ya que no tiene una operación pop_front(); tal operación sería lenta, ya que tendría que mover todos los elementos restantes.

A potencialmente más rápido, pero menos flexible, alternativa es implementar un buffer circular a través de una matriz de tamaño fijo (por ejemplo std::array, o una std::vector que no cambia el tamaño). Tendrá que lidiar con el caso de que se llene, ya sea al informar un error, o al asignar un buffer más grande y al copiar todos los datos.

Para std::priority_queue:

• std::vector es generalmente la mejor opción; crece exponencialmente (reduciendo el número de asignaciones de memoria) y es una estructura de datos simple a la que es muy rápido acceder; un iterador puede implementarse simplemente como un contenedor alrededor de un puntero.
• std::deque puede ser más lento, ya que normalmente crece de forma lineal (requiere más asignación de memoria) y el acceso es más complicado que con un vector.
• std::list no se puede utilizar, ya que no proporciona acceso aleatorio.

En resumen: los valores predeterminados suelen ser la mejor opción, pero si la velocidad realmente es importante, mida las alternativas.

Answer 2

Usaría std::queue para su cola básica que es (al menos de forma predeterminada) un contenedor en deque. Haz algo más especial si no funciona para ti.

std::priority_queue también existe (más de vector por defecto), pero la semántica agregada hace que sea más probable que tenga que rodar la suya aquí, dependiendo del rendimiento observado para su patrón de acceso particular.

vector tiene características de almacenamiento que lo hacen muy inadecuado para la eliminación de la parte frontal del conjunto de datos. Una gran cantidad de barajados para hacer cada vez que pop_front. Para una cola simple, evita esto.

list es probable que sea demasiado caro para cualquier cola de alto impacto, porque por contrato tiene que ofrecer la función que no necesita. Podría ser un candidato para usar como una cola de prioridad, pero mi instinto siempre es confiar en el STL.

Answer 3

vector implementaría una pila ya que su inserción rápida está al final y la eliminación rápida también está al final. Si desea una cola FIFO, vector sería una implementación incorrecta de usar.

deque o list ambos proporcionan inserción de tiempo constante en cada extremo. list es bueno para cachés LRU en los que desea mover elementos fuera del medio rápidamente y donde desea que sus iteradores sigan siendo válidos sin importar cuánto los mueva. deque se usa generalmente cuando las inserciones y eliminaciones se encuentran al final.

Lo principal que tengo que preguntar acerca de su colección es si se accede por varios hilos. Supongo que lo son, en cuyo caso uno de tus objetivos principales es reducir el bloqueo. Esto se hace mejor si al menos tiene una función multi_push y multi_get para que pueda poner más de un elemento a la vez sin ningún bloqueo.

También hay contenedores sin cerradura o contenedores sin cerraduras.

Probablemente descubrirá que su estrategia de bloqueo es más importante que cualquier actuación en la colección, siempre que sus operaciones sean todas de tiempo constante.