Comment obtenir un sous-vecteur TRIES d'un vecteur Sorted, rapide

Question

J'ai une structure de données comme ceci:

struct X { 
    float value; 
    int id; 
}; 

un vecteur de ceux (taille N (pensez 100000), triées par valeur (reste constante pendant l'exécution du programme):

std::vector<X> values; 

maintenant, je veux écrire une fonction

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

qui remplit le sur paramètre avec un sous-ensemble de classement de valeurs, donné par les passés ids (taille M < N (environ 0,8 fois N)), rapide (la mémoire n'est pas un problème, et cela sera fait à plusieurs reprises, donc la construction de lookuptables (les données d'aide à partir des paramètres de la fonction) ou quelque chose d'autre qui est fait qu'une seule fois est entièrement ok).

Ma solution à ce jour:
Construire LookupTable LUT contenant id -> décalage dans valeurs (préparation, exécution de manière constante)
créer std::vector<X> tmp, la taille N, rempli d'ids invalides (linéaire en N)
pour chaque id, copier values[lut[id]]-tmp[lut[id]] (linéaire en M)
boucle sur tmp, copie des articles à sur (linéaire N)

c'est linéaire dans N (comme il est plus grand que M), mais la variable temporaire et des bugs de copie répétées me. Y a-t-il un moyen de le faire plus rapidement que cela? Notez que M sera proche de N, donc les choses qui sont O (M journal N) sont défavorables.

Edit: http://ideone.com/xR8Vp est un exemple d'implémentation de l'algorithme mentionné, pour rendre la sortie désirée claire et prouver qu'elle est faisable en temps linéaire - la question est sur la possibilité d'éviter la variable temporaire ou de l'accélérer d'une autre manière, quelque chose qui n'est pas linéaire n'est pas plus rapide :).

Answer 1

Une autre approche, vous pouvez essayer est d'utiliser une table de hachage au lieu d'un vecteur pour rechercher ids dans:

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); 
     } 
    } 
} 

Cela va dans le temps linéaire depuis unordered_set::find est le temps prévu constante (en supposant que nous n'avons pas problèmes de hashing ints). Cependant, je soupçonne que cela ne soit pas aussi rapide dans la pratique que l'approche que vous avez décrite initialement en utilisant des vecteurs.

Answer 2

Depuis que votre vecteur est trié, et que vous voulez qu'un sous-ensemble de celui-ci soit trié de la même manière, je suppose que nous pouvons simplement découper le morceau que vous voulez sans le réarranger. Pourquoi ne pas simplement utiliser find_if() deux fois? Une fois pour trouver le début de la plage que vous voulez et une fois pour trouver la fin de la gamme. Cela vous donnera les itérateurs de début et de fin du sous-vecteur. Construire un nouveau vecteur en utilisant ces itérateurs. L'un des surcharges vectorielles prend deux itérateurs.Cela devrait fonctionner ou partition devrait fonctionner

Answer 3

Si j'ai bien compris votre problème, vous essayez en fait de créer un algorithme de tri temporel linéaire (sujet à la taille d'entrée des nombres M). Ce n'est pas possible.

Votre approche actuelle consiste à avoir une liste triée des valeurs possibles. Cela prend un temps linéaire au nombre de valeurs possibles N (théoriquement, étant donné que la recherche de carte prend O (1) temps). Le mieux que vous puissiez faire, c'est de trier les valeurs (que vous avez trouvées sur la carte) avec une méthode de tri rapide (O (MlogM) fe quicksort, mergesort etc) pour les petites valeurs de M et peut-être faire une recherche linéaire. Par exemple, si N vaut 100000 et M vaut 100, il est beaucoup plus rapide d'utiliser un algorithme de tri.

J'espère que vous pouvez comprendre ce que je dis. Si vous avez encore des questions je vais essayer d'y répondre :)

edit: (comment) Je vais expliquer plus loin ce que je veux dire. Dites que vous savez que vos nombres vont de 1 à 100. Vous les avez triés quelque part (en fait ils sont triés "naturellement") et vous voulez en obtenir un sous-ensemble trié. S'il était possible de le faire plus rapidement que O (N) ou O (MlogM), les algorithmes de tri utiliseraient cette méthode pour trier.

F.e. en ayant l'ensemble des nombres {5,10,3,8,9,1,7}, sachant qu'ils sont un sous-ensemble de l'ensemble trié de nombres {1,2,3,4,5,6,7,8 , 9,10} vous ne pouvez toujours pas les trier plus rapidement que O (N) (N = 10) ou O (MlogM) (M = 7).