Ordenando 1000-2000 elementos con muchos fallos de caché

Tengo una matriz de 1000-2000 elementos que son punteros a objetos. Quiero mantener mi matriz ordenada y, obviamente, quiero hacer esto lo más rápido posible. Están ordenados por un miembro y no se asignan de forma contigua, por lo que debe suponer una falta de caché cada vez que accedo al miembro de clasificación.

Actualmente, estoy ordenando a pedido en lugar de a agregar, pero debido a la falta de memoria caché y [presumiblemente] la falta de acceso al miembro, el bucle interno de mi ordenación rápida es lento.

Estoy haciendo pruebas y probando cosas ahora (y veo cuál es el verdadero cuello de botella) pero ¿alguien puede recomendar una buena alternativa para acelerar esto? ¿Debo hacer una inserción-ordenación en lugar de una ordenación rápida a pedido, o debo intentar cambiar mi modelo para que los elementos sean contigiosos y reduzcan las fallas de caché? O, ¿hay algún algoritmo de clasificación que no haya encontrado que sea bueno para los datos que se van a almacenar en la memoria caché?

Edit: Tal vez escribí esto mal :), en realidad no necesito mi arreglo ordenado todo el tiempo (no estoy iterando a través de ellos secuencialmente para nada) Simplemente lo necesito ordenado cuando hago un corte binario para encontrar un hacer coincidir el objeto, y hacer ese quicksort en ese momento (cuando quiero buscar) es actualmente mi cuello de botella, debido a que la memoria caché falla y salta (estoy usando un operador <en mi objeto, pero espero que las líneas de entrada en la versión )

Enfoque simple: ordenación por inserción en cada inserción. Dado que sus elementos no están alineados en la memoria, estoy adivinando la lista enlazada. Si es así, entonces podría transformarlo en una lista vinculada con saltos al elemento 10, el 100 y así sucesivamente. Esto es algo similar a la siguiente sugerencia.

O reorganiza la estructura de su contenedor en un árbol binario (o lo que cada árbol que le guste, B, B *, rojo-negro, …) e inserte elementos como los insertaría en un árbol de búsqueda.

Ejecutar una ordenación rápida en cada inserción es enormemente ineficiente. Realizar una búsqueda binaria y una operación de inserción probablemente serían órdenes de magnitud más rápidas. El uso de un árbol de búsqueda binario en lugar de una matriz lineal reduciría el costo de inserción.

Edit: me perdí que estabas haciendo una ordenación en la extracción, no insertar. En cualquier caso, mantener las cosas ordenadas amortiza el tiempo de clasificación de cada inserto, lo que casi tiene que ser una ganancia, a menos que tenga una gran cantidad de inserciones para cada extracción.

Si desea mantener la metodología de ordenación por extracción, tal vez cambie a la ordenación por fusión, u otra ordenación que tenga un buen rendimiento para los datos ordenados en su mayoría.

Creo que el mejor enfoque en su caso sería cambiar su estructura de datos a algo logarítmico y repensar su architecture. Debido a que el cuello de botella de su aplicación no es esa cosa de clasificación , pero la pregunta ¿por qué tiene que ordenar todo en cada inserto e intentar compensarlo agregando una clasificación a pedido? .

Otra cosa que podría probar (que se basa en su implementación actual) es implementar un pointer - something externo pointer - something similar a la tabla / función y ordenar esas segundas teclas, pero en realidad dudo que se beneficie en este caso.

En lugar de la matriz de los punteros, puede considerar una matriz de estructuras que constan de un puntero a su objeto y los criterios de clasificación. Es decir:

En lugar de

 struct MyType { // ... int m_SomeField; // this is the sort criteria }; std::vector arr; 

Usted puede hacer esto:

 strcut ArrayElement { MyType* m_pObj; // the actual object int m_SortCriteria; // should be always equal to the m_pObj->m_SomeField }; std::vector arr; 

También puede eliminar el campo m_SomeField de su estructura, si solo accede a su objeto a través de esta matriz.

Por lo tanto, para ordenar su matriz, no necesitará desreferenciar m_pObj cada iteración. Por lo tanto, utilizará el caché.

Por supuesto, debe mantener m_SortCriteria siempre sincronizada con m_SomeField del objeto (en caso de que lo esté editando).

Como mencionó, tendrá que hacer algunos perfiles para determinar si se trata de un cuello de botella y si otros enfoques proporcionan algún alivio.

Las alternativas al uso de una matriz son std :: set o std :: multiset, que normalmente se implementan como árboles binarios RB, por lo que tienen un buen rendimiento para la mayoría de las aplicaciones. Tendrá que compararlos con la frecuencia del patrón de ordenación por búsqueda que implementó.

En cualquier caso, no recomendaría hacer su propia búsqueda o búsqueda a menos que esté interesado en aprender más sobre cómo se hace.

Pensaría que la clasificación en la inserción sería mejor. Estamos hablando de comparaciones de O (registro N) aquí, así que digamos ceil( O(log N) ) + 1 recuperación de los datos para ordenar.

Para el año 2000, asciende a: 8

Lo bueno de esto es que puede almacenar en búfer los datos del elemento que se insertará, así es como solo tiene 8 llamadas de función para insertar realmente.

Es posible que desee ver un poco de alineación, pero haga un perfil antes de estar seguro de que ESTO es el lugar difícil.