Andrei Alexandrescu est une véritable légende vivante. Il s'agit d'une personne qui a apporté une contribution significative à l'histoire des langages de programmation modernes et des techniques généralisées et de métaprogrammation. Combien d'exemplaires ont été cassés dans les discussions
sur les normes de conception et de
codage C ++ modernes 101 (écrites avec les armoiries C ++ exceptionnelles de Sutter), et d'autres
livres et articles . En tant que co-auteur
du langage D , il a eu l'occasion non seulement de théoriser, mais aussi de faire de son rêve une réalité - et, ce qui est caractéristique, il l'a
incarné .
Maintenant, vous tenez dans ses mains un
rapport de la conférence DotNext 2018 Piter, qui parle des technologies d'optimisation modernes. Qu'est-ce que .NET a à voir avec cela? Il s'agit d'un rapport fondamental d'une personne qui a optimisé toute sa vie. Si les performances sont importantes pour vous, vous devez les regarder (ou lire cet article). Bienvenue au chat!
L'art du benchmarking
Je voudrais discuter avec vous de plusieurs sujets liés à l'analyse comparative. Pour commencer, répétons quelques choses de base.
La loi d'Amdahl fait partie des classiques de l'informatique, elle est principalement utilisée dans le calcul parallèle, mais fonctionne dans tout système complexe. Si nous voulons améliorer le travail d'un certain système, nous devons commencer là où les principaux problèmes de ce système sont concentrés. La loi elle-même est évidente: si un composant représente 20% du système, alors l'amélioration maximale des performances du système qui peut être obtenue en optimisant le fonctionnement de ce composant uniquement est de 20%. Trop souvent, je dois rencontrer des gens (bien sûr, nos lecteurs ne leur appartiennent pas) qui font des choses comme l'optimisation de l'analyse en ligne de commande. Ces opérations prennent les 10 premières microsecondes de votre programme, et les gens analysent leur complexité algorithmique et sont horrifiés si le temps est quadratique.
Comme vous le savez probablement, avant de commencer l'optimisation, il est nécessaire de profiler l'application et de sélectionner des points chauds. Ici, il faut dire à propos de la
loi de Ladma (ce n'est pas un vrai nom de famille, et Amdal, relu). Vous devez concentrer vos efforts sur la composante qui mène au plus grand investissement de temps. Il doit être déplacé en dehors de l'application, effectuer les travaux nécessaires, revenir en arrière et tester à nouveau. La raison pour laquelle vous devez le faire est que, très souvent, une amélioration des performances de 20% est le résultat de dix améliorations de 2%. Et dans le cadre d'un grand système, il est impossible de mesurer une si petite amélioration. Pour cela, le composant doit être testé dans une suite de tests. Une amélioration de 20% des performances de l'un des principaux composants du système peut signifier une amélioration de 5% pour le système dans son ensemble, et pour certains domaines, c'est un excellent résultat. N'oubliez pas que les optimisations peuvent avoir un certain nombre d'effets globaux. Par conséquent, sur la base des résultats de l'analyse comparative sélective, vous devez être très prudent lorsque vous tirez des conclusions sur le fonctionnement du système dans son ensemble.
Une erreur que nos lecteurs ne sont pas sûrs de commettre, mais qui est généralement assez courante: les gens mesurent la vitesse d'assemblage du débogage. Cela ne devrait jamais être fait. Cela revient à se fâcher à cause de la faible vitesse de l'escargot lors des courses: il n'est pas destiné à une telle compétition, il a d'autres objectifs dans la vie. Une autre erreur, un peu moins évidente: les gens mesurent d'abord les performances de base du système, et immédiatement après cela effectuent un benchmarking. Mais après avoir collecté la base de référence, de nombreuses ressources sont réchauffées. Par exemple, les fichiers ouverts sont mis en mémoire tampon et restent en mémoire (au moins sous Linux). Ainsi, le deuxième test ne sera plus rapide que parce qu'il est lancé après le premier. Cela se produit même avec des appels malloc. Après ces appels, le système ne revient pas à son état d'origine même si des appels de libération de mémoire sont effectués. La configuration interne, la mise en cache et les fonctionnalités utilisées par l'allocateur de mémoire permettent aux appels malloc suivants de s'exécuter beaucoup plus rapidement. Même sans tenir compte de l'effet du cache, malloc se souvient que, par exemple, certaines fonctions ont alloué de la mémoire pour des objets de 4 kilo-octets plusieurs fois, ce qui signifie que vous devez avoir une liste libre avec une taille d'élément de 4 kilo-octets. Ou un autre exemple: les recherches DNS sont mises en cache pour être réutilisées après la première requête. Si possible, lors de l'analyse comparative, vous devez redémarrer l'ensemble du processus à chaque fois, du début à la fin.
Par exemple, afin de remettre complètement le système dans son état d'origine, dans le cas de fichiers, ils doivent être ouverts sur un disque séparé, qui, après la fin du test, doit être supprimé (si je comprends bien, cela peut être fait sous Windows). L'opération n'est pas facile, mais dans la plupart des cas nécessaire.
Poursuivant la conversation sur les erreurs lors de l'optimisation, j'ai dû faire face à de tels cas lorsque les coûts d'impression sont inclus dans les résultats des tests. Il y a des erreurs de procédure lorsque plus d'une chose est modifiée avant chaque mesure, ce qui viole les principes les plus fondamentaux d'une expérience scientifique, car il n'est pas clair quel effet vous mesurez. Une autre erreur grave est lorsque certains rares cas sont optimisés, ce qui conduit à une pessimisation dans d'autres situations.
Voici un exemple avec Stack Overflow. L'auteur trie souvent des données déjà triées et est surpris, car la fonction `is_sorted 'est évidemment beaucoup plus rapide que` sort. Pourquoi alors dans `trier la première ligne n'est pas` si is_sorted retourne? Vous optimisez un cas extrêmement rare, des données complètement triées, et tous ceux qui ont au moins un élément non trié devront supporter les coûts de cette optimisation. Cela ne vaut pas la peine.
Je pense que je n’ai pas à prouver depuis longtemps que les architectures concurrentes actuelles sont extrêmement complexes: changement de fréquence dynamique, interruption par d’autres processus, virtualisation, etc. Par conséquent, il est presque impossible d'obtenir le même temps lors de la mesure, vos indicateurs trembleront toujours. Par conséquent, il ne faut pas se fier à des choses qui semblent évidentes. Disons, il peut nous sembler évident que moins d'instructions signifient un code plus rapide, et ce n'est pas toujours vrai. Il peut également sembler que l'utilisation des données stockées sera toujours plus rapide que la réexécution des calculs, donc si vous mettez en cache les résultats, tout ira bien. Comme dans le cas précédent, il ne peut pas être énoncé sans équivoque, tout comme l'inverse ne peut être énoncé sans condition - tout dépend du contexte. Évidemment, vous ne devriez avoir qu'une chose: tout doit être mesuré. Si vous mesurez tout, vous obtiendrez de meilleurs résultats que des experts ayant des connaissances qui ne prennent pas de mesures.
Il existe un certain nombre de pratiques assez fiables, dont la discussion peut vous conduire à des réflexions intéressantes. Nous devons commencer par le fait que les mathématiques ne vous laisseront pas tomber. Il permet de montrer que des systèmes à différentes vitesses peuvent être équivalents. Les mathématiques donnent des règles pour montrer l'équivalence de certaines choses et identifier certaines propriétés, et même si elles ne sont pas biaisées, peu importe ce qui est intéressant et ce qui ne l'est pas. Beaucoup de gens pensent que l'optimisation est basée sur la connaissance du code machine et du travail avec les bits, mais en fait elle a beaucoup de mathématiques, car vous prouvez qu'un système plus rapide est équivalent à un système plus lent.
Une autre règle générale est que les ordinateurs aiment les choses ennuyeuses. Avez-vous besoin de vous multiplier par deux vecteurs, un milliard d'éléments chacun? C'est une tâche idéale pour un ordinateur, tout l'équipement qu'il contient est spécialement affûté pour ce genre de tâches. Pour analyser ces données, en fonction d'eux pour construire une expression régulière - je ne veux pas le faire. Les ordinateurs n'aiment pas les choses comme les branches, les dépendances, les appels indirects, bref - ils n'aiment pas le code intelligent, ils aiment le code ennuyeux. Les ordinateurs n'aiment pas l'enregistrement indirect - un problème complexe avec lequel les personnes impliquées dans le fer luttent depuis longtemps et ne peuvent pas résoudre.
Une autre règle est que vous devez privilégier les opérations les moins puissantes, en d'autres termes, préférer l'ajout à la multiplication et la multiplication à l'exponentiation. Encore une fois, les mathématiques sont utiles ici.
Enfin, la dernière règle - le plus petit, le plus beau. La petite taille permet aux ordinateurs de tirer le meilleur parti de leurs avantages, car ils préfèrent que les données, et en particulier les instructions, soient proches les unes des autres. Les résultats de plusieurs mesures de la vitesse de l'application seront toujours différents, vous aurez une certaine distribution des résultats. Habituellement, nous prenons simplement la moyenne de ces quelques résultats. Mais le problème est qu'en raison des spécificités des ordinateurs, la moyenne inclura beaucoup de bruit. Lorsque Bill Gates prend le bus, en moyenne, chaque passager d'un bus est un milliardaire. Cela semble génial, mais c'est peu de confort pour une personne sans-abri voyageant dans le même bus. Une situation similaire se produit avec les interruptions: l'opération de multiplication prend des nanosecondes, mais lorsque vous effectuez de nombreuses mesures de telles opérations, l'une d'entre elles aura inévitablement une interruption de deux millisecondes. La différence est de trois ordres de grandeur, et pourtant, les développeurs n'en tiennent pas toujours compte.
Donc, je le répète: le bruit dans les ordinateurs est toujours additif; pour les gens, cela peut sembler insignifiant, mais pour le microcrédit, il est important, et la moyenne arithmétique comprendra beaucoup de bruit. Au lieu de la moyenne, vous avez besoin d'un indicateur qui ne mesurera que le temps que vous pouvez en quelque sorte influencer. Si nous abordons cette question du point de vue des mathématiques, nous verrons que nous devons trouver une valeur qui correspondra au plus grand nombre de mesures que nous ayons faites. En d'autres termes, nous avons besoin d'un mod. Cela nous amène immédiatement au problème: que se passe-t-il si vous prenez le mod quicksort? Si l'algorithme est probabiliste ou si les données sont aléatoires, alors il n'y aura presque jamais de mode. La densité des valeurs sera presque la même dans tout le spectre. Dans ce cas, nous rejetons simplement les 5% des mesures les plus importantes et après cela nous prenons la valeur moyenne - ou le maximum, dans ce dernier cas nous aurons un plafond qui ne sera pas dépassé dans 95% des cas. Presque toujours, il y aura un sujet assis dans l'ancien sous-sol avec un modem lent, dans lequel chaque page se chargera pendant une heure. Purement humains, nous sympathisons bien sûr avec lui, mais nous ne pouvons techniquement pas aider tout le monde - par conséquent, les 5% de cas restants doivent être négligés. En général, lors de la résolution de problèmes de réseau, nous nous concentrons souvent sur le 95e centile, car il est impossible de se concentrer sur le 100e. Le centième centile signifie le résultat le plus lent de toutes les mesures collectées - ce n'est pas informatif.
Remplacer les branches par l'arithmétique
Comment, j'espère, il est devenu clair que la mesure n'est pas un problème facile. Regardons quelques exemples et commençons par essayer de remplacer la ramification par l'arithmétique. Nous parlons de cas où nous avons besoin d'une instruction if, mais l'utiliser trop souvent n'est pas souhaitable. Au lieu de cela, nous intégrerons le résultat de la branche en tant que valeur 0/1. Le code sera linéaire, l'ordinateur n'aura qu'à le parcourir du début à la fin, sans penser à l'étape suivante.
Essayons de résoudre le problème suivant: transférer les plus bas de chaque quartile du tableau vers le premier quartile. En d'autres termes, le tableau doit être divisé en quatre parties et la valeur minimale de chaque partie doit être placée au début du tableau.
static void min4(double[] p) { int n = p.Length; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < n / 4; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Ci-dessus est le code de base. Soit dit en passant, je peux fièrement signaler que j'ai traduit ces exemples en C # et qu'ils ont été compilés avec succès. Le code lui-même est assez simple: `m est affecté à l'index de la plus petite des deux valeurs situées aux indices` i et` j, puis une affectation similaire est répétée deux fois de plus, en fonction des deux autres indices. Enfin, la valeur à l'indice `m est inversée dans le tableau avec la valeur à l'indice` i. Comme vous pouvez le voir, nous contournons le tableau à l'aide de quatre variables inductives.
Le problème de tester un tel algorithme sera intéressant et pas évident. Nous devrons le tester non pas sur un ensemble de données, mais sur des données qui pourraient survenir dans divers cas. Par exemple, sur des données qui ressemblent à des tuyaux d'un organe: augmentez d'abord, puis diminuez; sur des données aléatoires avec une distribution uniforme; sur un ensemble aléatoire de zéros et de uns - à partir de données aléatoires, la différence est qu'il y aura de nombreuses valeurs en double; sur des données déjà triées; enfin, sur des données obtenues par des mesures réelles de certains phénomènes physiques. Ce sera une approche sérieuse pour mesurer la vitesse d'un algorithme, et elle est généralement acceptée par les personnes qui étudient les algorithmes.
Essayons d'améliorer le code que nous venons de rencontrer.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < q; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Comme première optimisation, nous essaierons d'éviter une répétition excessive des opérations, pour cela nous supprimons plusieurs opérations de division de la boucle - divisant `n par 2 et 4 et divisant 3 *` n par 4. Mais après cette optimisation, nous découvrons que les calculs n'étaient pas pour nous le principal problème: le code ne deviendra pas plus rapide, bien qu'il soit plus compact. Dans le meilleur des cas, nous obtiendrons une amélioration d'un demi pour cent.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = q, k = 2 * q, l = 3 * q; for (; i < q; ++i, ++j, ++k, ++l) { int m0 = p[i] <= p[j] ? i : j; int m1 = p[k] <= p[l] ? k : l; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Le deuxième changement que nous apporterons au code est de réduire les dépendances. Dans la version précédente de l'algorithme, l'attribution de `m à` k ou` l dépend de la valeur affectée à` m ligne ci-dessus. Pour réduire le nombre de `m dépendances, nous calculons séparément` m0 et` m1, puis les comparons. Lorsque j'ai effectué cette optimisation, j'espérais une amélioration significative de la vitesse de l'algorithme, mais au final, il s'est avéré être nul. Mais, à mon avis, il est important de garder le nombre de dépendances au minimum, c'est pourquoi j'ai enregistré le code.
static void min4(double[] p) { int q = p.Length / 4; for (int i = 0; i < q; ++i) { int m0 = p[i] <= p[i + q] ? i : i + q; int m1 = p[i + 2 * q] <= p[i + 3 * q] ? i + 2 * q : i + 3 * q; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Essayons maintenant de réduire le nombre de variables inductives de quatre à une, et nous calculerons les trois autres de manière arithmétique, car elles sont en relation constante les unes avec les autres. C'est assez simple: au lieu de `k, nous aurons` i + q, au lieu des deux autres variables -` i + 2 * q et` i + 3 * q. J'avais également de grands espoirs pour cette optimisation, mais, comme la précédente, elle n'a donné aucun résultat à temps. Cela prouve encore une fois l'importance des mesures: sans elles, je pourrais me vanter d'avoir considérablement amélioré le fonctionnement de l'algorithme, et j'aurais des arguments très significatifs.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2: ++i) { int m0 = p[i - q] < p[i] ? i - q : i; int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q; Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
À la quatrième tentative, nous restructurons le cycle pour éliminer la multiplication par 3. Cela nous donnera une amélioration de 3%. Le résultat n'est toujours pas impressionnant. Ensuite, essayez de vous débarrasser des opérateurs ternaires.
Pour ce faire, je voudrais vous présenter une nouvelle fonction - `static int optionnel (bool flag, int value). Il convertit la valeur booléenne d'entrée en Int32, multiplie par -1 et la transmet à l'opérateur ET au niveau du bit avec la deuxième valeur d'entrée. Si le drapeau d'entrée était faux, alors dans int32 ce sera 0, et après toutes les conversions sur la sortie, nous aurons toujours 0. Si le drapeau d'entrée était vrai, dans int32 ce sera 1, multiplié par -1 nous obtenons FFFFFFFF, qui après le bit «Et» avec n'importe quel nombre donnera ce deuxième numéro. Veuillez noter qu'il n'y a aucune instruction if n'importe où, le code est sans branchement, c'est ennuyeux pour un ordinateur (bien qu'il nous semble juste complexe).
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2; ++i) { int m0 = i - optional(p[i - q] <= p[i], q); int m1 = i + q + optional(p[i + q2] < p[i + q], q); Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Nous remplacerons les opérateurs ternaires par cette fonction optionnelle, nous l'intégrerons dans le calcul. Nous l'appliquons deux fois, et dans le troisième cas, laissons le point d'interrogation. Ainsi, au lieu de quatre contrôles dans ce cycle, je n'en aurai qu'un.
D'après les résultats de mesure que vous voyez sur la diapositive, il est clair à quel point il était important de tester l'algorithme sur plusieurs ensembles de données différents. Sur un ensemble, nous ne comprendrions rien. Sur les données aléatoires et réelles, nous avons plus d'une double accélération, sur les tuyaux d'orgue et les données triées, nous avons un léger ralentissement. Cela est dû au fait que dans le cas de données triées pour le prédicteur de transition, il n'y aura pas de surprise, il prédira avec une précision de 100%. Dans le cas des tuyaux d'orgue, nous aurons une mauvaise prédiction au milieu de l'ensemble de données - encore une fois, une très grande précision. En revanche, avec des données aléatoires, la différence entre nos deux approches sera énorme. Nous avons remplacé tous les contrôles imprévisibles par une logique simple. Ici, nous revenons à une vérité simple: les ordinateurs sont conçus pour l'informatique, comme son nom l'indique (informatique - informatique). Ramification, affichage d'images sur l'écran - tout cela, ils fonctionnent bien pire. Il est beaucoup plus simple d'exécuter «et» au niveau du bit que de passer l'instruction if.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = 0; i < q; ++i) { int m = i + optional(p[i + q] < p[i], q); m += optional(p[i + q2] < p[m], q); m += optional(p[i + q2 + q] < p[m], q); Swap(ref p[i], ref p[m]); } }
Ayant finalement obtenu un résultat positif de l'optimisation, nous allons essayer de remplacer le dernier opérateur ternaire par notre fonction `optionnelle. Cette fois, le gain de vitesse sera faible. Pour comprendre pourquoi cela se produit, vous devez regarder le code généré. Dans la version précédente du code, où le point d'interrogation était toujours présent, le compilateur avait déjà trouvé un moyen d'exécuter le code sans branchement. Et quand il arrive à l'opérateur ternaire, il pourrait déjà le prédire. Remplacer ce dernier morceau par `facultatif donnera un code un peu pire. Par conséquent, je le répète, il est important de prendre des mesures à chaque fois.
Une autre fonctionnalité que je voudrais vous recommander est `ifelse sans branches, que vous voyez maintenant à l'écran. Certes, je n'ai pas pu réaliser avec elle les améliorations de performances dans notre exemple. Si 0 lui est transmis comme indicateur, la première ligne sera 0; dans le second, nous soustrayons 1 de 0 dans Int32 et obtenons FFFFFFFF, après quoi cette valeur est passée au bit "Et" avec l'argument de fonction `v2, qui nous donnera cet argument lui-même sans changements; enfin, les première et deuxième lignes sont passées au «OU» au niveau du bit, ce qui, encore une fois, nous donnera «v2. Si le drapeau est 1, alors la première ligne sera égale à `v1; dans le second, nous soustrayons 1 de 1 et obtenons 0, à la suite de quoi la ligne entière sera 0, et 0 et `v1 dans le bit OR 'donnera' v1.
J'espère qu'une telle «ifelse sans fonction de branchement intéressera les personnes impliquées dans le backend - pour l'instant, les compilateurs modernes pour une raison quelconque n'utilisent pas cette approche. Avec ces fonctions, vous pouvez réorganiser les algorithmes afin que les compilateurs les comprennent pour vous, car vous êtes plus intelligent et plus créatif que votre compilateur.
Grande intersection d'ensemble
Modifiez un peu le sujet de notre conversation et passez à l'intersection de grands ensembles. Jusqu'à présent, nous parlions d'opérateurs individuels, nous allons maintenant créer de nouveaux algorithmes, nous devrons donc nous distraire des détails et ouvrir nos esprits à une perspective plus large. Je suppose que vous connaissez le tri par fusion, multipliez deux vecteurs et recherchez des éléments communs à deux vecteurs triés. Deux ensembles triés sont parcourus, et lorsque des éléments égaux sont en eux, cela est considéré comme une correspondance. Si l'un des deux éléments comparés est plus petit, il se déplace. Cet algorithme est assez simple, mais très courant - probablement le plus utilisé au monde. Il est utilisé dans toutes les requêtes de plusieurs mots, chacune de ces requêtes est l'intersection de deux ensembles. Cet algorithme, en particulier, utilise Google et devrait également être appliqué à toutes les requêtes de base de données.
int Intersect(double[] a1, double[] a2, double[] t) { if (a1.Length == 0 || a2.Length == 0) return 0; int i1 = 0, i2 = 0, i = 0; for (;;) if (a1[i1] < a2[i2]) { if (++i1 == a1.Length) break; } else if (a2[i2] < a1[i1]) { if (++i2 == a2.Length) break; } else { t[i++] = a1[i1]; if (++i1 == a1.Length || ++i2 == a2.Length) break: } return i; }
Jetez un œil à l'implémentation de base de cet algorithme. Si les deux jeux d'entrées sont vides, alors, évidemment, nous retournons 0. Ensuite, nous commençons une boucle infinie, dans laquelle, s'il y a correspondance, nous augmentons le résultat de 1 et vérifions si le cycle doit être terminé. Au lieu d'une boucle infinie, on pourrait utiliser l'instruction for et spécifier la condition pour y terminer la boucle. Mais cela signifierait un travail supplémentaire. Dans l'implémentation que vous voyez sur la diapositive, dans la première branche, nous avons `if (a1 [i1] <a2 [i2]), après quoi il y a une augmentation de` i1 de 1, et nous ne pouvons que vérifier` i1. De même, dans la deuxième branche, il suffit de cocher `i2. Les deux valeurs doivent être vérifiées uniquement dans la troisième branche. Si cette vérification était au début du cycle, nous ferions le travail supplémentaire.
Essayons d'améliorer cette implémentation. Pour le moment, sa complexité algorithmique est linéaire, en fonction de deux arguments d'entrée. Dans l'apprentissage automatique, il faut souvent trouver l'intersection d'ensembles très différents les uns des autres en taille ou en statistiques. Par exemple, vous disposez d'un vecteur d'entrée long et d'un vecteur d'entité court que vous vérifiez. Dans notre code, il peut y avoir un million d'enregistrements en «a1 et mille en» a2. Dans ce cas, nous ne sommes pas prêts à parcourir un million d'étapes pour terminer cet algorithme. La plus grande charge sera ici sur la ligne de code suivante: `if (++ i1 == a1.length) break. Juste avant cela, une comparaison se produit, puis dans cette ligne, il y a un incrément de la valeur; il s'agit essentiellement d'une recherche linéaire. Nous parcourons le vecteur long à la recherche d'éléments du court. Dans le pire des cas, nous effectuerons de nombreuses recherches de ce type, en se déplaçant lentement le long du vecteur.
Essayons d'améliorer cet algorithme. Eh bien, si ce n'est pas une recherche linéaire, alors le binaire est meilleur, non? Utilisons le binaire. Son avantage est qu'il donne l'indice du plus grand des plus petits éléments.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, a1[i1]); if (m == a2.Length) continue; --m; if (!(a2[m] < a1[i1])) t[i++] = a1[i1]; } return i; }
Le code ci-dessus est une implémentation de notre algorithme de recherche binaire. Mais ce n'est pas très efficace. La pire situation ici sera lorsque la recherche binaire échouera à chaque fois. Et cela se produira dans des scénarios assez importants - par exemple, lorsque les deux ensembles sont identiques. Vous, comme un imbécile, coupez des cercles avec une recherche binaire, alors que vous n'avez qu'à parcourir le premier algorithme linéaire. Pourquoi la recherche binaire, lorsque l'élément souhaité - à chaque fois ici, le premier de la liste?
Comment faire fonctionner l'algorithme avec succès sur des données identiques et différentes? La vérification de toutes les données sera trop coûteuse pour les ressources. Je ferai une réserve qu'il ne s'agit pas de données complètement identiques, mais très similaires, avec des statistiques similaires, les tailles peuvent également varier. Vous pouvez vérifier les quelques éléments suivants. La solution évidente est de réduire votre recherche. Lorsque nous effectuons une recherche binaire, alors, après avoir trouvé un élément, nous ne nous intéressons plus aux éléments plus petits que lui, puisque le deuxième vecteur est également trié. Ainsi, nous pouvons à chaque fois réduire notre zone de recherche, en éliminant moins tous les éléments de l'élément trouvé.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i2 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, i2, a2.Length, a1[i1]); if (m == i2) continue; if (!(a2[m - 1] < a1[i1])) t[i++] = a1[i1]; i2 = m + 1; } return i; }
Voici la mise en œuvre de cette approche. Vous voyez que nous effectuons une recherche binaire à chaque fois pour une partie du tableau d'origine commençant par `i2 et se terminant par` a2.length. Comme `i2 augmentera à chaque recherche, la zone de recherche sera réduite.
La prochaine optimisation que je voudrais implémenter ici est liée à l'algorithme de recherche au galop. Il s'agit essentiellement d'une recherche binaire avec une étape différente. Dans le cas de la recherche binaire, nous commençons à chaque fois par le milieu - mais pensons que lorsque nous recherchons un nom dans l'annuaire téléphonique, nous ne l'ouvrons pas au milieu? Si le nom de famille d’une personne commence, disons, sur «B», nous ouvrirons le livre plus près du début. Ce principe est implémenté dans une recherche galopante: on commence à explorer les données dans le sens ascendant avec un pas croissant exponentiellement après chaque vérification: d'abord 1, puis 2, puis 4. Cela nous donne une bonne complexité algorithmique. Si le pas grandissait linéairement, la complexité serait quadratique. Lorsque nous «sautons» l'élément que nous recherchons, nous effectuons une recherche binaire normale sur le segment restant, qui sera petite et n'affectera pas de manière significative le temps d'exécution de l'algorithme. Ainsi, nous combinons tous les avantages des deux approches. Mise en place d'un tel algorithme:
int GBsearch(double[] a, int i, int j, double v) { for (int step = 1;; step *= 2) { if (i >= j) break; if (a[i] > v) break; if (i + step >= j) return Bsearch(a, i + 1, J, v); if (a[i + step] > v) return Bsearch(a, i + 1, i + step, v); i += step + 1; } return i; }
Nous discutons maintenant de la mise à l'échelle, c'est-à-dire que nous essayons de trouver l'intersection de plus de deux ensembles. Pour chaque recherche de plusieurs mots, il faudra trouver l'intersection de plusieurs ensembles. Pour ce faire, on peut par exemple comparer les deux premiers ensembles, puis leur intersection avec le troisième et ainsi de suite. Mais ce n'est pas une solution optimale. Nous devons prendre les premiers éléments de tous les ensembles et trouver le plus petit d'entre eux, qui devra ensuite être déplacé. Nous avons besoin d'une structure de données qui nous permet de trouver le plus petit des nombreux éléments et qui a une complexité constante. Une telle structure de données est un tas. Mais ce sera un groupe étrange, il ne sera pas basé sur un tableau physique. Ce sera imaginaire, nous n'y organiserons que les premiers éléments de nos décors. Une fois que nous avons trouvé le plus petit élément du tas, nous pouvons toujours rechercher tous les autres ensembles.
Le travail sur les sujets dont nous discutons aujourd'hui dans la pratique a une forme plutôt artisanale. En pratique, nous aurons le plus souvent plusieurs ensembles, pas seulement deux, et beaucoup de travail a été écrit sur ce sujet. L'algorithme classique ici est SVS, dans lequel nous regroupons les ensembles, prenons les deux plus petits et choisissons le plus court comme candidat. Vous trouverez ici un bon aperçu de ce sujet. Les problèmes liés aux ensembles croisés, au produit scalaire des vecteurs clairsemés, au tri par fusion, à toute forme de comparaison avec l'image dans le temps deviennent de plus en plus intéressants. L'algorithme que je vous ai montré s'est révélé très utile. Merci de votre attention.
Andrei Alexandrescu ne viendra pas à DotNext 2018 Moscou, mais Jeffrey Richter, Greg Young, Pavel Yosifovich et d'autres seront là. Les noms des conférenciers et les sujets des rapports peuvent être trouvés ici , et les billets ici . Rejoignez-nous maintenant!