Actualmente estoy trabajando en un proyecto de dispositivo integrado en el que tengo problemas de rendimiento. El perfil ha localizado una operación O (N) que me gustaría eliminar.

Básicamente tengo dos matricesint A[N] yshort B[N]. Entradas enA Son únicos y ordenados por restricciones externas. La operación más común es verificar si un valor particulara aparece enA[]. Menos frecuente, pero aún común es un cambio a un elemento deA[]. El nuevo valor no está relacionado con el valor anterior.

Dado que la operación más común es el hallazgo, ahí es dondeB[] entra. Es una serie ordenada de índices enA[], tal queA[B[i]] < A[B[j]] si y solo sii<j. Eso significa que puedo encontrar valores enA utilizando una búsqueda binaria.

Por supuesto, cuando actualizoA[k], Tengo que encontrark enB y moverlo a una nueva posición, para mantener el orden de búsqueda. Desde que conozco los viejos y nuevos valores deA[k], eso es solo unmemmove() de un subconjunto deB[] entre la antigua y nueva posición dek. Esta es la operación O (N) que necesito arreglar; ya que los viejos y nuevos valores deA[k] son esencialmente al azar me estoy moviendo en promedio sobreN / 2 N / 3 elementos.

Miré enstd::make_heap utilizando[](int i, int j) { return A[i] < A[j]; } como el predicado. En ese caso puedo hacer fácilmenteB[0] señalar el elemento más pequeño deA, y actualizandoB ahora es una operación de reequilibrio O (log N) barata. Sin embargo, generalmente no necesito el valor más pequeño de A, necesito encontrar si algún valor dado está presente. Y eso es ahora una búsqueda O (N log N) enB. (La mitad de mis elementos N están en el registro de profundidad N del montón, un cuarto en (registro N) -1, etc.), lo cual no es una mejora sobre una búsqueda O (N) estúpida directamente enA.

Teniendo en cuenta questd::set tiene O (registro N) insertar y encontrar, yo diría que debería ser posible obtener el mismo rendimiento aquí para actualizar y encontrar. Pero, ¿cómo hago eso? Necesito otro orden paraB? ¿Un tipo diferente?

B es actualmente unshort [N] porqueA yB juntos son del tamaño de mi caché de CPU, y mi memoria principal es mucho más lenta. Pasar de 6 * N a 8 * N bytes no sería bueno, pero sería aceptable si mi búsqueda y actualización van a O (registro N) ambas.