Problema

Supongamos que tengo una gran variedad de bytes (piense hasta 4 GB) que contienen algunos datos. Estos bytes corresponden a objetos distintos de tal manera que cadas bytes (pensars Hasta 32) constituirá un solo objeto. Un dato importante es que este tamaño.s es el mismo para todos los objetos, no se almacena dentro de los mismos objetos y no se conoce en el momento de la compilación.

En este momento, estos objetos son solo entidades lógicas, no objetos en el lenguaje de programación. Tengo una comparación de estos objetos que consiste en una comparación lexicográfica de la mayoría de los datos del objeto, con un poco de funcionalidad diferente para romper los vínculos utilizando los datos restantes. Ahora quiero ordenar estos objetoseficientemente (Esto realmente va a ser un cuello de botella de la aplicación).

Ideas hasta ahora

He pensado en varias formas posibles de lograr esto, pero cada una de ellas parece tener algunas consecuencias bastante desafortunadas. No necesariamente tienes que leer todos estos.Intenté imprimir en negrita la pregunta central de cada enfoque. Si vas a sugerir uno de estos enfoques,entonces Su respuesta debe responder a las preguntas relacionadas también.

1. C quicksort

Por supuesto, el algoritmo C quicksort también está disponible en aplicaciones C ++. Su firma coincide casi perfectamente con mis requisitos. Pero el hecho de que el uso de esa función prohibirá la inclusión de la función de comparación significará que cada comparación conlleva una sobrecarga de invocación de la función. Había esperado una manera de evitar eso.Cualquier experiencia sobre cómo Cqsort_r Las comparaciones con STL en términos de rendimiento serían muy bienvenidas.

2. Indirección usando objetos que apuntan a los datos

Sería fácil escribir un montón de objetos con punteros a sus datos respectivos. Entonces uno podría ordenar esos. Hay dos aspectos a considerar aquí. Por un lado, solo mover los punteros en lugar de todos los datos significaría menos operaciones de memoria. Por otro lado, no mover los objetos probablemente rompería la localidad de la memoria y, por lo tanto, almacenaría el rendimiento. Es probable que los niveles más profundos de recursión de acceso rápido en realidad puedan acceder a todos sus datos desde unas pocas páginas de caché desaparecerían casi por completo. En su lugar, cada página de memoria en caché produciría muy pocos elementos de datos utilizables antes de ser reemplazada.Si alguien pudiera aportar alguna experiencia sobre el intercambio entre la copia y la localidad de la memoria, me alegraría mucho.

3. iterador personalizado, referencia y objetos de valor

Escribí una clase que sirve como un iterador sobre el rango de memoria. La desreferenciación de este iterador no produce una referencia sino un objeto recién construido para mantener el puntero a los datos y el tamaños Que se da en la construcción del iterador. Así que estos objetos pueden ser comparados, e incluso tengo una implementación destd::swap para éstos. Desafortunadamente, parece questd::swap no es suficiente parastd::sort. En algunas partes del proceso, mi implementación de gcc utiliza la ordenación por inserción (como se implementó en__insertion_sort en archivostl_alog.h) que mueve un valor fuera de la secuencia, mueve un número de elementos en un paso, y luego regresa el primer valor a la secuencia en la posición apropiada:

          typename iterator_traits<_RandomAccessIterator>::value_type
            __val = _GLIBCXX_MOVE(*__i);
          _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
          *__first = _GLIBCXX_MOVE(__val);

¿Conoce una implementación de clasificación estándar que no requiere un tipo de valor pero que puede operar solo con swaps?

Así que no solo necesitaría mi clase, que sirve como referencia, sino que también necesitaría una clase para mantener un valor temporal. Y como el tamaño de mis objetos es dinámico, tendría que asignarlo en el montón, lo que significa asignaciones de memoria en las hojas del árbol de recusrion. Quizás una alternativa sería un tipo de valor con un tamaño estático que debería ser lo suficientemente grande como para contener objetos del tamaño que actualmente intento admitir. Pero eso significaría que habría aún más piratería en la relación entre elreference_type y elvalue_type de la clase iterador. Y significaría que tendría que actualizar ese tamaño para mi aplicación para que un día soporte objetos más grandes. Feo.

Si puede pensar en una forma limpia de obtener el código anterior para manipular mis datos sin tener que asignar memoria dinámicamente, esa sería una gran solución. Ya estoy utilizando las funciones de C ++ 11, por lo que usar la semántica de movimiento o similar no será un problema.

4. Clasificación personalizada

Incluso consideré reimplementar todo de quicksort. Quizás podría hacer uso del hecho de que mi comparación es principalmente una comparación lexicográfica, es decir, podría ordenar las secuencias por primer byte y solo cambiar al siguiente byte cuando el primer byte es el mismo para todos los elementos. No he resuelto los detalles sobre esto todavía, peroSi alguien puede sugerir una referencia, una implementación o incluso un nombre canónico que se usará como palabra clave para tal clasificación lexicográfica de byte, estaré muy contento. Todavía no estoy convencido de que, con un esfuerzo razonable de mi parte, pueda mejorar el rendimiento de la implementación de la plantilla STL.

5. Algoritmo completamente diferente

Se que haymuchos muchos tipos de algoritmos de clasificación que hay. Algunos de ellos podrían ser más adecuados para mi problema.Tipo radix Me viene a la mente primero, pero todavía no lo he pensado.Si puede sugerir un algoritmo de clasificación más adecuado a mi problema, hágalo. Preferiblemente con implementación, pero incluso sin.

Pregunta

Así que básicamente mi pregunta es esta:
"¿Cómo clasificaría de manera eficiente los objetos de tamaño dinámico en la memoria del montón?"

Cualquier respuesta a esta pregunta que sea aplicable a mi situación es buena, no importa si está relacionada con mis propias ideas o no. Las respuestas a las preguntas individuales marcadas en negrita, o cualquier otra información que pueda ayudarme a decidir entre mis alternativas, también serían útiles, especialmente si no aparece una respuesta definitiva para un solo enfoque.