Cómo conseguir un subvector resuelto de un vector ordenado, rápido

Question

Tengo una estructura de datos de la siguiente manera:

struct X { 
    float value; 
    int id; 
}; 

un vector de las personas (tamaño N (piensa 100000), ordenados por valor (se mantiene constante durante la ejecución del programa):

std::vector<X> values; 

Ahora, quiero escribir una función

void subvector(std::vector<X> const& values, 
       std::vector<int> const& ids, 
       std::vector<X>& out /*, 
       helper data here */); 

que llena el cabo parámetro con un subconjunto ordenada de valores, dada por los pasaron ids (tamaño M < N (alrededor de 0,8 veces N)), rápido (la memoria no es un problema, y ​​esto se hará de forma repetida, por lo que construir tablas de consulta (como datos auxiliares desde los parámetros de la función) u otra cosa que se haga una sola vez es completamente correcto).

Mi solución hasta el momento:
Build LookupTable LUT contiene Identificación del -> desplazamiento en valores (preparación, tiempo de ejecución de modo constante)
crear std::vector<X> tmp, tamaño N, lleno de ids no válidos (lineal en N)
para cada ID, copia values[lut[id]]-tmp[lut[id]] (lineal en M)
bucle sobre tmp, copiar elementos a cabo (lineal en N)

esto es lineal en N (ya que es más grande que M), pero la variable temporal y repetidos me errores de copia. ¿Hay alguna manera de hacerlo más rápido que esto? Tenga en cuenta que M estará cerca de N, así que las cosas que son O (M registro N) son desfavorables.

Edit: http://ideone.com/xR8Vp es una implementación de ejemplo del algoritmo mencionado, para hacer que el resultado deseado sea claro y demostrar que es factible en tiempo lineal; la pregunta es sobre la posibilidad de evitar la variable temporal o acelerarla de alguna otra manera, algo que no es lineal no es más rápido :).

Answer 1

Un enfoque alternativo que podría intentar es usar una tabla hash en lugar de un vector para buscar los identificadores en:

void subvector(std::vector<X> const& values, 
       std::unordered_set<int> const& ids, 
       std::vector<X>& out) { 

    out.clear(); 
    out.reserve(ids.size()); 
    for(std::vector<X>::const_iterator i = values.begin(); i != values.end(); ++i) { 
     if(ids.find(i->id) != ids.end()) { 
      out.push_back(*i); 
     } 
    } 
} 

Esto se ejecuta en tiempo lineal desde unordered_set::find es constante de tiempo esperado (suponiendo que no tenemos problemas hashing ints). Sin embargo, sospecho que podría no ser tan rápido en la práctica como el enfoque que describiste inicialmente usando vectores.

Answer 2

Como su vector está ordenado, y quiere un subconjunto de él ordenado de la misma manera, supongo que podemos cortar el trozo que desee sin tener que reorganizarlo.

¿Por qué no usar simplemente find_if() dos veces? Una vez para encontrar el inicio del rango que desea y una para encontrar el final del rango. Esto le dará los iteradores de inicio y fin del vector secundario. Construye un nuevo vector usando esos iteradores. Una de las sobrecargas vector constructor toma dos iteradores.

Ese o el algoritmo partition debería funcionar.

Answer 3

Si entendí correctamente su problema, en realidad trata de crear un algoritmo lineal de clasificación de tiempo (sujeto al tamaño de entrada de los números M). Eso NO es posible.

Su enfoque actual es tener una lista ordenada de valores posibles. Esto lleva tiempo lineal al número de valores posibles N (en teoría, dado que la búsqueda del mapa toma O (1) vez).

Lo mejor que puedes hacer es ordenar los valores (encontrados en el mapa) con un método de clasificación rápido (O (MlogM) fe quicksort, mergesort, etc.) para valores pequeños de M y tal vez hacer esa búsqueda lineal valores más grandes de M. Por ejemplo, si N es 100000 y M es 100, es mucho más rápido usar un algoritmo de clasificación.

Espero que puedan entender lo que digo. Si todavía tiene preguntas, intentaré responderlas :)

editar: (comentario) Explicaré a continuación a qué me refiero. Digamos que sabe que sus números van del 1 al 100. Los ha ordenado en algún lugar (en realidad están clasificados "naturalmente") y desea obtener un subconjunto de ellos en forma ordenada. Si fuera posible hacerlo más rápido que O (N) u O (MlogM), los algoritmos de clasificación simplemente usarían este método para ordenar.

F.e. teniendo el conjunto de números {5,10,3,8,9,1,7}, sabiendo que son un subconjunto del conjunto ordenado de números {1,2,3,4,5,6,7,8 , 9,10} usted todavía no puede ordenarlos más rápido que O (N) (N = 10) o O (MlogM) (M = 7).