STL Set: insérer deux millions de nombres ordonnés de la manière la plus efficace

Question

Pour l'insertion de masse suivante, étant donné que les entrées sont ordonnées, y a-t-il de (légères) optimisations?

set<int> primes; 
for (int i = 2; i <= 2000000; i++) { 
    primes.insert(i); 
} 
// then follows Sieve of Eratosthenes algorithm 

---

Nouvelle amélioration, deux fois plus vite:

set<int> primes; 
for (int i = 2; i <= 2000000; i++) { 
    primes.insert(primes.end(), i); 
} 
// then follows Sieve of Eratosthenes algorithm 

Answer 1

Il y a une version surchargée de la méthode insert disponible qui prend un itérateur comme premier paramètre. Cet itérateur est utilisé comme indice, c'est-à-dire que la comparaison commencera à partir de cet itérateur. Donc si vous passez l'itérateur correct comme indice, alors vous devriez avoir une opération d'insertion très efficace sur l'ensemble. Voir here pour plus de détails. Je crois en votre cas, numbers.end() -1 sera une bonne option.

Answer 2

De http://www.cplusplus.com/reference/stl/set/set/

vector<int> numbers; 
for (int i=2; i<=2000000; ++i) 
    numbers.push_back(i); 

set<int> primes(numbers.begin(), numbers.end()); 

qui aurait O (n) la complexité, où que le vôtre a O (n * log (n)) complexité.

Le lien référencé indique que lorsque vous utilisez le constructeur basé sur l'itérateur, si l'itérateur est trié, vous obtenez un résultat linéaire. Cependant, je ne vois rien d'explicite sur comment expliquer explicitement au constructeur qu'il s'agit d'un itérateur trié.

---

Pour quelque chose de plus propre, je préfère utiliser l'itérateur de comptage de boost. Cela raccourcit cela:

set<int> primes(
    boost::counting_iterator<int>(0), 
    boost::counting_iterator<int>(200000)); 

Answer 3

est ici quelques-uns:

1. mettre en œuvre un allocateur stl personnalisé qui fait les réservations pour la mémoire dès le départ.

2. Si vous utilisez la solution de vecteur, appelez la réserve.

3. Si vous souhaitez simplement implémenter l'utilisation du tamis (ou implémenter) un boost counting iterator et ne stocker que les résultats dans un vecteur, qui appelle réserve.

Answer 4

Si vous commencez avec la gamme complète des candidats int s, je ne voudrais pas utiliser un set du tout, je voudrais utiliser un vector<bool>, les init tous false et marquer les cibles (nombres premiers) comme true comme ils sont situés.

vector<bool> candidates(200000); 

Vous pouvez indexer cela en utilisant le candidat actuel int - 1 (plage candidate = 1..200000). Puis itérer en utilisant find pour localiser les valeurs réelles, en convertissant à int en utilisant le décalage par rapport à begin().

• Nombre total d'allocations de mémoire - 1.
• utilisation de la mémoire totale 25000 octets (vector<bool> est un cas particulier, voir le commentaire de Rogers @ Greg) vs> = 800000 pour set<int>, actualisation des frais généraux BTree.
• L'accès à tous les éléments s'effectue via l'arithmétique du pointeur.