std :: map and performance, ensembles intersectés

StackOverflow https://stackoverflow.com/questions/1056244

  •  20-08-2019
  •  | 
  •  

Question

Je croise des ensembles de nombres et je le fais en enregistrant un compte de chaque fois que je vois un nombre sur une carte.

Je trouve que la performance est très lente.

Détails: - L'un des ensembles contient 150 000 numéros - L'intersection de cet ensemble et d'un autre ensemble prend environ 300 ms la première fois et environ 5000 ms la deuxième fois. - Je n’ai pas encore fait de profilage, mais chaque fois que je casse le débogueur en faisant l’intersection, c’est dans malloc.c!

Alors, comment puis-je améliorer cette performance? Basculer vers une structure de données différente? Certains comment améliorer les performances d'allocation de mémoire de la carte?

Mise à jour:

  1. Est-il possible de demander à std :: map ou boost :: unordered_map à pré-allouer un peu d'espace?
  2. Ou y a-t-il des conseils pour les utiliser efficacement?

Update2:

Voir conteneur C ++ rapide comme le hachage C # < !> lt; T > et Dictionnaire < K, V > ;?

Update3:

J'ai comparé set_intersection et obtenu des résultats horribles: 

(set_intersection) Found 313 values in the intersection, in 11345ms
(set_intersection) Found 309 values in the intersection, in 12332ms

Code: 

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}
Était-ce utile?

La solution 9

J'ai découvert quelque chose: si j'attache le débogueur à des versions RELEASE ou DEBUG (par exemple, en tapant F5 dans l'IDE), alors je vais avoir des moments horribles.

Autres conseils

Vous devez absolument utiliser des vecteurs préalloués qui sont bien plus rapides. Le problème avec l'intersection d'ensembles stl est que chaque fois que vous passez à l'élément suivant, vous poursuivez un pointeur alloué de manière dynamique, qui pourrait ne pas se trouver dans vos caches de processeur. Avec un vecteur, l'élément suivant sera souvent dans votre cache car il est physiquement proche de l'élément précédent.

Le truc avec les vecteurs, c'est que si vous ne préaffectez pas la mémoire pour une tâche de ce type, elle s'exécutera MÊME SAUF, car elle réallouera la mémoire à mesure qu'elle se redimensionnera lors de votre étape d'initialisation.

Essayez quelque chose comme ceci instaed - ce sera beaucoup plus vite. 

int runIntersectionTestAlgo() { 

vector<char> vector1; vector1.reserve(100000);
vector<char> vector2; vector2.reserve(1000);

// Create 100,000 values for set1
for ( int i = 0; i < 100000; i++ )    {
    int value = 1000000000 + i;
    set1.push_back(value);
}

sort(vector1.begin(), vector1.end());

// Create 1,000 values for set2
for ( int i = 0; i < 1000; i++ )    {
    int random = rand() % 200000 + 1;
    random *= 10;
    int value = 1000000000 + random;
    set2.push_back(value);
}

sort(vector2.begin(), vector2.end());

// Reserve at most 1,000 spots for the intersection
vector<char> intersection; intersection.reserve(min(vector1.size(),vector2.size()));
set_intersection(vector1.begin(), vector1.end(),vector2.begin(), vector2.end(),back_inserter(intersection));

return intersection.size(); 
}

Sans en savoir plus sur votre problème, & "Recherchez avec un bon profileur &"; est le meilleur conseil général que je puisse donner. Au-delà de ça ...

Si l’allocation de mémoire est votre problème, passez à une sorte d’allocateur en pool réduisant les appels à malloc. Boost a un certain nombre d’allocateurs personnalisés qui devraient être compatibles avec std::allocator<T>. En fait, vous pouvez même essayer ceci avant le profilage, si vous avez déjà remarqué que les échantillons de rupture de débogage finissent toujours par vector.

Si vous savez que votre espace numérique est dense, vous pouvez passer à une implémentation bitset ou <=>, en utilisant vos nombres comme index dans le vecteur.

Si votre espace numérique est généralement maigre, mais présente une classification naturelle (il s'agit d'un gros si ), vous pouvez passer à une carte de vecteurs. Utilisez des bits d’ordre supérieur pour l’indexation de carte et des bits d’ordre inférieur pour l’indexation vectorielle. Sur le plan fonctionnel, cette procédure est très similaire à celle qui consiste à utiliser simplement un allocateur en pool, mais elle vous donnera probablement un meilleur comportement de mise en cache. Cela a du sens, puisque vous fournissez plus d’informations à la machine (la mise en cluster est explicite et conviviale pour le cache, plutôt que la distribution aléatoire attendue de l’allocation de pool).

Je seconderais la suggestion de les trier. Il existe déjà des algorithmes de jeux STL qui fonctionnent sur des plages triées (comme set_intersection, set_union, etc.):

set_intersection

Je ne comprends pas pourquoi vous devez utiliser une carte pour effectuer une intersection. Comme on l’a dit, vous pouvez mettre les ensembles dans std::set, puis utiliser std::set_intersection().

Ou vous pouvez les mettre dans hash_set. Mais il faudrait alors implémenter l'intersection manuellement: techniquement, il suffit de placer l'un des ensembles dans un <=>, puis de parcourir l'autre, et de vérifier si chaque élément est contenu dans <=>.

Les intersections avec les cartes sont lentes, essayez un hash_map . (Cependant, cela n’est pas fourni dans toutes les implémentations STL.

Vous pouvez également trier les deux cartes et le faire de manière fusionnée.

Quel est votre algorithme d'intersection? Peut-être y a-t-il des améliorations à apporter?

Voici une autre méthode

Je ne sais pas si c'est plus rapide ou plus lent, mais ça pourrait être quelque chose à essayer. Avant de le faire, je vous recommande également d'utiliser un profileur pour vous assurer que vous travaillez réellement sur le hotspot. Modifiez les ensembles de chiffres que vous intersectez pour utiliser std::set<int> à la place. Puis parcourez le plus petit en regardant chaque valeur que vous trouvez. Pour chaque valeur du plus petit ensemble, utilisez la méthode find pour voir si le nombre est présent dans chacun des autres ensembles (pour obtenir des performances optimales, recherchez du plus petit au plus grand).

Ceci est optimisé dans le cas où le nombre n’est pas trouvé dans tous les ensembles. Ainsi, si l’intersection est relativement petite, il se peut qu’elle soit rapide.

Ensuite, stockez l'intersection dans std::vector<int> à la place - l'insertion avec push_back est également très rapide.

Voici une autre méthode alternative

Modifiez les ensembles de nombres en std::sort et utilisez std::binary_search pour trier du plus petit au plus grand. Puis utilisez std::set pour trouver les valeurs, en utilisant à peu près la même méthode que ci-dessus. Cela peut être plus rapide que de rechercher <=> car le tableau est plus serré dans la mémoire. En fait, peu importe, vous pouvez alors parcourir les valeurs dans lock-step, en regardant celles qui ont le même valeur. Incrémentez uniquement les itérateurs inférieurs à la valeur minimale que vous avez vue à l'étape précédente (si les valeurs étaient différentes).

Peut-être votre algorithme. Si je comprends bien, vous faites une rotation de chaque ensemble (ce que j'espère être un ensemble standard) et vous les jetez dans une autre carte. Cela fait beaucoup de travail que vous n'avez pas besoin de faire, car les clés d'un jeu standard sont déjà triées dans l'ordre. Au lieu de cela, prenez un & "; Fusion-tri &"; comme approche. Spin sur chaque iter, dereferencing pour trouver le min. Comptez le nombre qui ont ce min et incrémentez-les. Si le nombre était N, ajoutez-le à l'intersection. Répétez cette opération jusqu'à la fin de la première carte (si vous comparez les tailles avant de commencer, vous ne devrez pas vérifier chaque fin de carte à chaque fois).

Réponse à la mise à jour : il existe des possibilités d'accélérer l'allocation de mémoire en réservant à l'avance de l'espace, comme boost :: pool_alloc . Quelque chose comme: 

std::map<int, int, std::less<int>, boost::pool_allocator< std::pair<int const, int> > > m;

Mais honnêtement, le malloc est très bon à ce qu’il fait; Je profilerais avant de faire quelque chose de trop extrême.

Regardez vos algorithmes, puis choisissez le type de données approprié. Si vous allez avoir un comportement de type set, et que vous voulez faire des intersections et autres, std::set est le conteneur à utiliser.

Etant donné que ses éléments sont stockés de manière triée, l’insertion peut vous coûter O (log N), mais une intersection avec une autre (trié!) <=> peut être effectuée en temps linéaire.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top