Calculer Girl
  1. Calculer Girl
  3. Qu’est-ce qui rend si rapide l’implémentation de gcc std :: list?
Intereting Posts
Vérifier qu’une variable est un nombre dans le shell UNIX obtenir le chemin Java / JVM du programme dans Windows Server La commande ‘mvn’ n’est pas reconnue sur le noeud esclave Windows Jenkins Commande Linux pour imprimer une structure de répertoire sous la forme d’un arbre Windows: impossible de voir la stack d’appels lors de l’ouverture d’un minidump L’appel de MsiEnumRelatedProducts à partir de C # se bloque Erreur Genymotion: Impossible de charger le moteur Virtualbox Comment chiffrer un fichier volumineux dans openssl en utilisant une clé publique Désactiver le stickyness sur apache mod_proxy_balancer La tâche de démarrage se bloque une fois la tâche terminée Comment XOR deux caractères décimaux dans BASH FileOutputStream java.io.IOException: EOF prématuré Comment extraire le contenu entre deux crochets en utilisant grep? Tableaux, listes liées et autres structures de données dans le script cmd.exe (batch) Tilde non reconnu dans le terminal Mac

Qu’est-ce qui rend si rapide l’implémentation de gcc std :: list?

J’ai une implémentation de liste chaînée et j’expérimente les algorithmes Mergesort et QuickSort.

Ce que je ne comprends pas, c’est pourquoi l’opération de sorting dans std :: list est si rapide. En regardant la liste std :: sous Linux et il semble être aussi une liste liée, pas une liste basée sur un tableau.

Le sorting de fusion que j’ai essayé presque identique à la version de Dave Gamble ici: Fusionner Trier une liste liée

En outre, je pensais essayer un simple quicksort basé sur ce code: http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

Étonnamment, sortinger 10 millions de nombres aléatoires en utilisant std :: list et sortinger était environ 10 fois plus rapide que l’un ou l’autre.

Et pour ceux qui le demandent, oui, je dois utiliser ma propre classe de liste pour ce projet.

J’ai jeté un coup d’oeil à l’implémentation intéressante de GLibC pour list :: sort ( code source ) et il ne semble pas implémenter un algorithme de sorting par fusion traditionnel (du moins, je n’en ai jamais vu auparavant).

Fondamentalement, ce qu’il fait est:

  1. Crée une série de seaux (64 au total).
  2. Supprime le premier élément de la liste pour le sortinger et le fusionne avec le premier i=0 ( i=0 th).
  3. Si, avant la fusion, le seau n’est pas vide, fusionner le seau avec le seau i+1 .
  4. Répétez l’étape 3 jusqu’à ce que nous fusionnions avec un seau vide.
  5. Répétez les étapes 2 et 3 jusqu’à ce que la liste à sortinger soit vide.
  6. Fusionner tous les seaux non vides restants ensemble à partir du plus petit au plus grand.

Petite remarque: fusionner un seau X avec un seau Y enlèvera tous les éléments du seau X et les appenda au seau Y tout en gardant tout sortingé. Notez également que le nombre d’éléments dans un compartiment est 0 ou 2^i .

Maintenant, pourquoi est-ce plus rapide qu’une sorte de fusion traditionnelle? Eh bien, je ne peux pas dire avec certitude, mais voici quelques choses qui me viennent à l’esprit:

  • Il ne parcourt jamais la liste pour trouver un point central qui rend également l’algorithme plus convivial pour le cache.
  • Les anciens compartiments étant petits et utilisés plus fréquemment, les appels à merge réduisent le cache plus fréquemment.
  • Le compilateur est capable d’optimiser cette implémentation. Il faudrait comparer l’assemblage généré pour être sûr de cela.

Je suis sûr que les gens qui ont implémenté cet algorithme l’ont testé de manière approfondie, donc si vous voulez une réponse définitive, vous devrez probablement demander à la liste de diffusion de GCC.