std :: vecteur plus rapide que std :: unordered_set?

Question

Dans mon moteur physique personnalisé, le plus gros goulot d'étranglement est une méthode qui récupère tous les corps du partitionnement spatial (une grille 2D) et renvoie une collection contenant uniquement des pointeurs uniques vers le corps. L'utilisation d'un profileur montre que le goulot d'étranglement est dans la méthode "contains".

De toute évidence, un std::unordered_set serait la solution "idéale" ici. Cependant, il est beaucoup plus lent que la solution actuelle. J'ai également essayé google::dense_hash_set, qui est plus rapide que std::unordered_set, mais toujours plus lent que la solution actuelle.

const unordered_set<Body*>& GridInfo::getBodiesToCheck() 
{ 
    bodiesToCheck.clear(); 
    for(auto& query : queries) 
     for(auto& body : *query) 
      /*if(!contains(bodiesToCheck, body))*/ bodiesToCheck.insert(body); 
    return bodiesToCheck; 
} 

Pourquoi les conteneurs "corrects" plus lent qu'un std::vector?

Y a-t-il un moyen d'accélérer cette méthode?

Answer 1

Il y a deux possibilités que je peux penser:

1. Vous avez un nombre assez restreint d'éléments de données qu'une recherche linéaire est plus rapide qu'un hachage-plus comparer recherche.
2. Vous utilisez la même fonction contains pour rechercher un élément dans le unordered_set, au lieu d'utiliser la fonction membre find.

Answer 2

Voici ce que vous trouverez dans la documentation std:

« conteneurs unordered_set sont plus rapides que les conteneurs fixés pour accéder aux éléments individuels par leur clé, même si elles sont généralement moins efficaces pour l'itération de gamme grâce à un sous-ensemble de leur éléments."

Eh bien, puisque la méthode de recherche finira par boucle à travers un grand nombre d'éléments des thats probablement la raison ...

Peut-être que si vous avez utilisé une fonction de hachage costum vous devriez l'améliorer pour le rendre plus rapide ... La seule chose à laquelle je peux penser ...

Answer 3

Si le nombre de corps dupliqués n'est pas si élevé par rapport aux autres, une option pourrait être de simplement pousser tous vos corps dans le vecteur et supprimer les doublons par la suite. Mais cela nécessitera un std::sort suivi d'un erase(std::unique, end).

Mais cela vaut peut-être la peine d'essayer, étant donné que votre vecteur semble afficher un std::unordered_set de toute façon, qui n'a pas le même emplacement mémoire et un accès trivial comme un std::vector.

Answer 4

Je ne suis pas sûr que je comprends le problème correctement, mais il semble que la recherche sera plus lente sur std::vector/std::find, mais l'itération pourrait être plus rapide qu'avec std::unordered_set. Si tel est le cas, et vous n'êtes pas limité par des contraintes de mémoire, vous pouvez mélanger les deux approches:

Maintenir à la fois un std::unordered_set et un std::vector avec les éléments. Recherchez dans le std::unordered_set pour déterminer si l'élément est déjà là, si ce n'est pas le cas, ajoutez-le aux deux conteneurs. À la fin itérer sur le std::vector.

Notez que vous pouvez fournir des indications aux deux conteneurs concernant le nombre «attendu» d'éléments qu'ils contiendront et qui réduira le nombre d'allocations de mémoire/rehashing.