Cómo acelerar un método simple (preferiblemente sin cambiar las interfaces o estructuras de datos)?

Question

tengo algunas estructuras de datos:

• all_unordered_m es un vector grande que contiene todas las cadenas que necesito (todos diferentes)
• ordered_m es un vector pequeño que contiene los índices de un subconjunto de las cuerdas (todos diferentes) en el anterior vector
• position_m mapea los índices de objetos del primer vector a su posición en el segundo.

El método string_after(index, reverse) devuelve la cadena referenciada por ordered_m despuésall_unordered_m[index].

ordered_m se considera circular, y se explora en orden natural o inverso según el segundo parámetro.

El código es algo como lo siguiente:

struct ordered_subset { 
    // [...] 

    std::vector<std::string>& all_unordered_m; // size = n >> 1 
    std::vector<size_t> ordered_m;    // size << n 
    std::tr1::unordered_map<size_t, size_t> position_m; 

    const std::string& 
    string_after(size_t index, bool reverse) const 
    { 
     size_t pos = position_m.find(index)->second; 
     if(reverse) 
      pos = (pos == 0 ? orderd_m.size() - 1 : pos - 1); 
     else 
      pos = (pos == ordered.size() - 1 ? 0 : pos + 1); 
     return all_unordered_m[ordered_m[pos]]; 
    } 
}; 

Teniendo en cuenta que:

• sí necesito todas las estructuras de datos para otros fines;
• no puedo cambiarlos porque necesito para acceder a las cadenas:
  • por su id en la all_unordered_m;
  • por su índice dentro de los varios ordered_m;
• Necesito saber la posición de una cuerda (identificada por su posición en el primer vector) dentro del vector ordered_m;
• No puedo cambiar la interfaz string_after sin cambiar la mayor parte del programa.

¿Cómo puedo acelerar el método string_after que se llama billones de veces y está consumiendo aproximadamente el 10% del tiempo de ejecución?

EDIT: He intentado hacer un position_mvector en lugar de un unordered_map y utilizando el siguiente método para evitar saltos:

string_after(size_t index, int direction) const 
{ 
    return all_unordered_m[ordered_m[ 
     (ordered_m.size()+position_m[index]+direction)%ordered_m.size()]]; 
} 

El cambio en position_m parece ser el más eficaz (I' No estoy seguro de que la eliminación de las ramas haya cambiado, me siento tentado de decir que el código es más compacto pero igual de eficiente con respecto a eso).

Answer 1

vector las búsquedas son increíblemente rápidas. size() llamadas y aritmética simple son increíblemente rápidas. Las búsquedas de map, en comparación, son tan lentas como una tortuga muerta con un bloque de concreto en la espalda. A menudo los he visto convertirse en un cuello de botella en un código simple como este.

Puede probar unordered_map de TR1 o C++ 0x (una sustitución de tabla de acceso directo de map) y ver si eso hace la diferencia.

Answer 2

Bueno, en tales casos (una función pequeña que se llama a menudo) cada rama puede ser muy costosa. Hay dos cosas que te vienen a la mente.

1. ¿Podría omitir el parámetro reverse y convertirlo en dos métodos separados? Esto solo tiene sentido si eso simplemente no empuja la if-declaración al código de llamada.
2. Intente lo siguiente para calcular pos: pos = (pos + 1) % ordered_m.size() (esto es para el caso de reenvío). Esto solo funciona si está seguro de que pos nunca se desborda al incrementarlo.

En general, trate de reemplazar las ramas con operaciones aritméticas en tales casos, esto puede darle una aceleración sustancial.