Pourquoi std:: rotate est-il si rapide?
Pourquoi std::rotate est-il tellement plus rapide que la fonction équivalente qui cplusplus.com décrit?
Cplusplus.com mise en œuvre:
template <class ForwardIterator>
void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
{
ForwardIterator next= middle;
while (first != next)
{
swap (*first++, *next++);
if(next == last)
next= middle;
else if (first==middle)
middle= next;
}
}
J'ai deux algorithmes de tri d'insertion qui sont entièrement identiques, à l'exception que l'on utilise std::rotate, et que l'on utilise cplusplus.com fonction équivalente. Je les mets à trier 1000 vecteurs avec 1000 int éléments. Le genre qui utilise std::rotate prend 0.376 secondes, et l'autre prend 8.181 secondes.
, Pourquoi est-ce? Je ne suis pas avec l'intention d'essayer de faire quelque chose de mieux que les fonctions STL mais je suis toujours curieux.
2 réponses
Modifier:
Puisque le contexte n'est pas donné, il n'est pas clair si votre code appelle std::swap() ou d'une autre swap(a,b) algorithme de type
T tmp = a; a = b; b = tmp;
Lorsque a et b sont des vecteurs de 1000 intS chacun, cela copierait tous les éléments vectoriels 3 fois. La version spécialisée de std::swap() pour les conteneurs comme std::vector<T> appelle la méthode container a.swap(b) à la place, en échangeant essentiellement uniquement les pointeurs de données dynamiques des conteneurs.
En outre, pour différents types d'itérateurs, l'implémentation std::rotate() peut utiliser certaines optimisations (voir ma réponse plus ancienne, peut-être trompeuse ci-dessous).
Mise en garde: l'implémentation de std::rotate() dépend de l'implémentation.
Pour différentes catégories d'itérateurs, différents algorithmes peuvent être utilisés
(par exemple, recherchez __rotate( dans l'en-tête bits/stl_algo.h de GNU g++).
Pour déplacer n éléments par m=std::distance(first,middle) un algorithme simple (naïf) comme M rotations par un élément nécessite O(n*m) opérations de déplacement ou de copie. Mais seuls les mouvements O(n) sont nécessaires, lorsque chaque élément est directement placé à sa bonne position, il en résulte un algorithme (approximativement) M fois plus rapide.
Un exemple d'illustration: faire pivoter une chaîne s = "abcdefg" par trois éléments:
abcdefg : store 'a' in temporary place
dbcdefg : move s[3] to s[0] (where it belongs in the end, directly)
dbcgefg : move s[6] to s[3]
dbcgefc : move s[9%7] to s[6] (wrapping index modulo container size: 9%7 == 2)
dbfgefc : move s[5] to s[2]
dbfgebc : move s[1] to s[5] (another wrapping around)
defgebc : move s[4] to s[1]
defgabc : move 'a' from temporary place to s[4]
Pour n et m avec le plus grand diviseur commun 1, vous avez terminé maintenant. Sinon, vous devez répéter ce schéma n/m temps pour les premiers m éléments consécutifs (n > m pris ici).
Cet algorithme un peu plus compliqué est beaucoup plus rapide.
Pour itérateurs bidirectionnels un autre algorithme o(3n) légendaire peut être utilisé, appelé "retournement des mains". Selon le livre de Jon Bentley Programming Pearls Il a été utilisé dans les premiers éditeurs UNIX pour déplacer du texte:
Placez vos mains devant vous, l'une au-dessus de l'autre, les pouces vers le haut. Maintenant
- tournez une main.
- tournez l'autre.
- tournez les deux, connectés les uns aux autres.
Dans le code:
reverse(first, middle);
reverse(middle, last);
reverse(first, last);
Pour accès aléatoire les itérateurs de gros morceaux de mémoire peuvent être déplacés par swap_ranges() (ou memmove() opérations pour les types de POD).
Microoptimisation en utilisant des opérations d'assembleur peut donner une petite quantité supplémentaire d'accélération, il peut être fait sur le dessus de l'algorithme à jeun.
Les algorithmes utilisant des éléments consécutifs au lieu de "sauter" en mémoire entraînent également un plus petit nombre de pertes de cache sur les architectures informatiques modernes.
Comme les commentateurs l'ont déjà indiqué, cela dépend de l'implémentation de votre bibliothèque Standard. Mais le code que vous avez posté est valide même pour forward iterators . En tant que tel, il impose très peu d'exigences (seulement que ces itérateurs peuvent être incrémentés et déréférencés).
Stepanov classique Éléments de Programmation consacre un chapitre entier (10) rotate et d'autres réarrangement des algorithmes. Pour les itérateurs de la série de swaps dans votre code donne O(3N) affectations. Pour itérateurs bidirectionnels , trois appels consécutifs à reverse donnent un autre algorithme O(3N). Pour les itérateurs à accès aléatoire, std::rotate peut être implémenté en tant qu'affectations O(N) en définissant une permutation des indices W. R. T. à l'itérateur de départ first.
Tous les algorithmes ci-dessus sont en place. En utilisant un tampon mémoire, il est possible que la version à accès aléatoire puisse bénéficier de la plus grande localité de cache de memcpy() ou memmove() (si le le type de valeur sous-jacent est POD) dans lequel des blocs entiers de mémoire contiguë peuvent être échangés. Si votre Tri d'insertion est effectué sur un tableau ou std::vector, Il est probable que votre bibliothèque Standard profite de cette optimisation.
TL; DR : faites confiance à votre bibliothèque Standard et ne réinventez pas la roue!