Il y a quelque temps, mon collègue m'a demandé de l'aider avec un problème. J'ai résolu le problème pour lui, mais en plus, il m'a semblé qu'en résolvant ce problème, plusieurs algorithmes et techniques de programmation pouvaient être expliqués. Et montrent également l'accélération du temps d'exécution de l'algorithme de 25 secondes à 40 ms.

Énoncé du problème

Pour un projet personnel, mon collègue avait besoin d'un algorithme pour trouver cinquante vidéos les plus similaires pour une vidéo donnée. La similitude était censée être estimée par le nombre de balises exposées correspondantes. Plus la vidéo correspond à des tags, plus ils sont similaires. De cela, nous pouvons immédiatement tirer plusieurs conclusions:

• Tous les tags sous la vidéo peuvent être combinés en un seul groupe;
• il n'y aura certainement pas plus de tels groupes que les vidéos elles-mêmes;
• si la vidéo est similaire à une autre vidéo d'un certain groupe de balises, elle est également similaire aux autres vidéos de ce groupe;

Il s'avère qu'il suffit de travailler uniquement avec des groupes de balises. Dans la première version, un collègue a décidé de stocker les balises dans une table de balises: chaque vidéo a un lien vers l'ID du groupe de balises, et les groupes eux-mêmes sont une séquence de valeurs booléennes qui indiquent si la balise correspondante est définie. En C #, un groupe de balises ressemble à ceci:

public class TagsGroup { bool[] InnerTags { get; } } 

Un collègue a suggéré qu'il n'aurait pas plus d'un million de vidéos sur le site et pas plus de 4 000 balises différentes, pour un compte rond, vous pouvez prendre 4096 = 2 ^ 12.
Ensuite, la classe TagsGroup peut être représentée comme ceci:

 public class TagsGroup { public const int TagsGroupLength = 4096; bool[] InnerTags { get; } public TagsGroup(bool[] innerTags) { if (innerTags == null) throw new ArgumentException(nameof(innerTags)); if (innerTags.Length != TagsGroupLength) { throw new ArgumentException(nameof(innerTags)); } InnerTags = innerTags; } } 

Vous devez maintenant vérifier la similitude entre les deux groupes de balises. Dans les conditions actuelles, cela se transforme en une simple vérification de la vérité dans les éléments correspondants des tableaux InnerTags de deux groupes de balises:

 public static int MeasureSimilarity(TagsGroup a, TagsGroup b) { int result = 0; for (int i = 0; i < TagsGroupLength; i++) { if (a.InnerTags[i] && a.InnerTags[i] == b.InnerTags[i]) result++; } return result; } 

Maintenant, il ne reste plus qu'à calculer la similitude du groupe de balises souhaité avec chaque groupe existant et à sélectionner les cinquante plus similaires. Je me fixe une autre condition pour assurer la stabilité de l'échantillon, à savoir dans l'échantillon final, il y aura cinquante groupes d'étiquettes pour lesquels MeasureSimilarity donné le résultat le plus élevé, tandis que les groupes d'étiquettes avec la même MeasureSimilarity indice inférieur pour ceux qui avaient un indice inférieur dans le groupe existant d'origine. Plus de détails peuvent être trouvés, par exemple, ici: https://ru.wikipedia.org/wiki/Sustainable_Sort .
Pour résoudre ce problème, j'ai décidé de faire la classe SimilarTagsCalculator , voici son code:

 class SimilarTagsCalculator { TagsGroup[] Groups { get; } public SimilarTagsCalculator(TagsGroup[] groups) { if (groups == null) throw new ArgumentException(nameof(groups)); Groups = groups; } public TagsGroup[] GetFiftyMostSimilarGroups(TagsGroup value) { const int resultLength = 50; //,          var list = new List<TagsSimilarityInfo>(resultLength); //      for (int groupIndex = 0; groupIndex < Groups.Length; groupIndex++) { TagsGroup tagsGroup = Groups[groupIndex]; //      int similarityValue = TagsGroup.MeasureSimilarity(value, tagsGroup); // -  TagsSimilarityInfo newInfo = new TagsSimilarityInfo(groupIndex, similarityValue); //    ,     , if (list.Count == resultLength && list[resultLength - 1].CompareTo(newInfo) == -1) { continue; //     } //   ,    -  int index = ~list.BinarySearch(newInfo); list.Insert(index, newInfo); // if (list.Count > resultLength) { //    , //   , ..    list.RemoveAt(resultLength); } } // -   TagsGroup[] result = new TagsGroup[resultLength]; for (int i = 0; i < resultLength; i++) { result[i] = Groups[list[i].Index]; } return result; } } 

et la structure TagsSimilarityInfo :

 struct TagsSimilarityInfo : IComparable<TagsSimilarityInfo>, IComparable { public int Index { get; } public int Similarity { get; } public TagsSimilarityInfo(int index, int similarity) { Index = index; Similarity = similarity; } public bool Equals(TagsSimilarityInfo other) { return Index == other.Index && Similarity == other.Similarity; } public override bool Equals(object obj) { return obj is TagsSimilarityInfo other && Equals(other); } public override int GetHashCode() { unchecked { return (Index * 397) ^ Similarity; } } public int CompareTo(TagsSimilarityInfo other) { int similarityComparison = other.Similarity.CompareTo(Similarity); return similarityComparison != 0 ? similarityComparison : Index.CompareTo(other.Index); } public int CompareTo(object obj) { if (ReferenceEquals(null, obj)) return 1; return obj is TagsSimilarityInfo other ? CompareTo(other) : throw new ArgumentException($"Object must be of type {nameof(TagsSimilarityInfo)}"); } } 

J'ai préparé trois repères pour cet algorithme:

• repère complètement aléatoire, c.-à-d. le nombre de balises définies dans les groupes est aléatoire et le groupe de balises avec lequel nous comparerons est également aléatoire;
• le nombre de balises définies dans les groupes augmente, nous comparerons avec le groupe dans lequel toutes les balises sont définies. Il s'avère que certains des derniers groupes de balises devraient être les plus appropriés;
• comme ci-dessus, mais le nombre de balises exposées diminue. Les 50 premiers groupes de balises seront les plus appropriés;

Voici les résultats de référence pour un million de groupes:

BenchmarkDotNet = v0.11.5, OS = Windows 10.0.17134.765 (1803 / April2018Update / Redstone4)
Processeur Intel Core i7-6700 à 3,40 GHz (Skylake), 1 processeur, 8 cœurs logiques et 4 cœurs physiques
Fréquence = 3328126 Hz, résolution = 300,4694 ns, minuterie = TSC
SDK .NET Core = 3.0.100-preview5-011568
[Hôte]: .NET Core 3.0.0-preview5-27626-15 (CoreCLR 4.6.27622.75, CoreFX 4.700.19.22408), RyuJIT 64 bits

La répartition du temps d'exécution est très grande, outre 25 secondes, c'est très long, mon collègue n'accepte pas d'attendre aussi longtemps. Faisons donc des optimisations. Maintenant, il y a trois domaines principaux pour accélérer le programme:

• Méthode MeasureSimilarity ;
• un algorithme dans le corps de la boucle dans GetFiftyMostSimilarGroups ;
• la boucle elle-même dans GetFiftyMostSimilarGroups ;

Nous allons considérer chacune des trois directions dans l'ordre.

Prédiction de branche

Tout d'abord, considérez la méthode MeasureSimilarity .

 public static int MeasureSimilarity(TagsGroup a, TagsGroup b) { int result = 0; for (int i = 0; i < TagsGroupLength; i++) { if (a.InnerTags[i] && a.InnerTags[i] == b.InnerTags[i]) result++; } return result; } 

Dans le précédent benchmark, il y avait une très grande variation de durée d'exécution entre le test aléatoire et l'un des tests séquentiels. Les groupes de balises pour les tests séquentiels ont été créés selon le principe suivant:

• le nombre requis de groupes a été divisé en packages. Nombre de paquets - le nombre maximum de balises dans le groupe;
• pour chaque groupe du i-ème paquet, les premières i balises ont été définies;

Il s'avère que chaque groupe de balises dans ces tests se compose de deux parties consécutives de balises exposées et non exposées. MeasureSimilarity a toutes les conditions préalables pour que la prédiction de branche de processeur ait un effet significatif dans les conditions actuelles. Pour vérifier cela, écrivez simplement un benchmark qui compare le temps d'exécution de MeasureSimilarity pour les données aléatoires et les données séquentielles:

 int GetSimilaritySum(TagsGroup[] tagsGroups) { int result = 0; foreach (TagsGroup tagsGroup in tagsGroups) { result += TagsGroup.MeasureSimilarity(tagsGroup, etalon); } return result; } [Benchmark] public int Sorted() => GetSimilaritySum(sortedGroups); [Benchmark] public int Unsorted() => GetSimilaritySum(unsortedGroups); 

Un million de groupes d'étiquettes ont été testés, mais dans Sorted dans chaque groupe, il y avait d'abord plusieurs étiquettes exposées, puis des étiquettes non exposées, et dans Unsorted le même nombre d'étiquettes exposées a été dispersé au hasard dans tout le groupe.
La différence de 5 secondes est impressionnante et quelque chose doit être fait. Pour se débarrasser de l'influence de la prédiction des branches et accélérer généralement la méthode, vous devez vous débarrasser des branches elles-mêmes. Il n'y a qu'une seule branche dans MeasureSimilarity - vérifiant que les balises correspondantes sont définies dans deux groupes. Estimons dans quels cas la condition sera vraie, pour cela nous allons faire un tableau de la vérité de la condition:

La table de vérité coïncide complètement avec le "ET" logique, c'est-à-dire le résultat est vrai si et seulement si les deux balises sont vraies, alors la condition peut être réduite à: if (a.InnerTags[i] && b.InnerTags[i]) . Mais de cette façon, la condition demeure. Dans l'étape suivante, nous nous assurerons que l'ajout au résultat est toujours effectué, pour cela nous réécrivons le corps de la boucle comme ceci:

 int t = a.InnerTags[i] && b.InnerTags[i] ? 1 : 0; result += t; 

Nous ne nous sommes toujours pas débarrassés de la condition et avons même ralenti la méthode. Mais maintenant, il est devenu évident que si le type d' InnerTags changé de bool en octet (1 pour vrai et 0 pour faux), alors vous pouvez vous débarrasser de la condition dans l'opérateur ternaire. Ensuite, la classe TagsGroup ressemblera à ceci:

 public class TagsGroup { public const int TagsGroupLength = 4096; byte[] InnerTags { get; } public static int MeasureSimilarity(TagsGroup a, TagsGroup b) { int result = 0; for (int i = 0; i < TagsGroupLength; i++) { int t = a.InnerTags[i] & b.InnerTags[i]; result += t; } return result; } public TagsGroup(bool[] innerTags) { if (innerTags == null) throw new ArgumentException(nameof(innerTags)); if (innerTags.Length != TagsGroupLength) { throw new ArgumentException(nameof(innerTags)); } InnerTags = new byte[TagsGroupLength]; for (int i = 0; i < TagsGroupLength; i++) { InnerTags[i] = (byte) (innerTags[i] ? 1 : 0); } } } 

Voici les résultats de référence pour la mise à jour de MeasureSimilarity :

mais pour le bechmark principal mis à jour:

À mon avis, c'était déjà super. Pour ceux qui étaient convaincus que toute l'accélération s'est produite uniquement parce que le type booléen a été remplacé par un octet, j'ai lancé une référence pour un tel corps de boucle:

 int t = a.InnerTags[i] & b.InnerTags[i]; if (t == 1) result += t; 

et voici les résultats:

Emballage de données

Chaque groupe a de nombreux tags, et leur nombre ne peut en aucun cas être réduit. De plus, vous devez comparer les balises avec le même index et vous ne pouvez pas donner de réponse finale sans vérifier toutes les balises. Donc, dans tous les cas, nous devrons parcourir tout le groupe de balises. Ce serait formidable de pouvoir paralléliser cette tâche d'une manière ou d'une autre, de sorte qu'il serait possible de traiter plusieurs balises en une seule opération conditionnelle. Vous pouvez le faire grâce à une véritable parallélisation, ou vous pouvez utiliser un emballage de données spécial, que nous utiliserons. Chaque balise représente désormais 1 ou 0. Dans le result résultat de l'opération "ET" est simplement accumulé. Mais la même opération logique peut être appliquée non seulement aux nombres à bit unique. C # vous permet de le faire sans aucun problème jusqu'à 64 bits (vous pouvez en faire plus via BitArray , mais ce n'est pas ça). Si nous représentons deux groupes d'étiquettes comme un ensemble de nombres de 64 bits avec le jeu de bits correspondant, alors il sera possible d'effectuer une opération «ET» sur chacun de ces groupes de nombres de 64 bits. On ne sait pas quoi faire du résultat. Regardons à nouveau le corps de la boucle:

 int t = a.InnerTags[i] & b.InnerTags[i]; result += t; 

le résultat augmente de 1 à chaque fois que t == 1 et ne change pas lorsque t == 0. Par conséquent, le résultat sera égal au nombre de fois où le résultat de a.InnerTags[i] & b.InnerTags[i] était égal à un. En conséquence, il serait possible de sauvegarder tous les résultats des a.InnerTags[i] & b.InnerTags[i] dans une sorte de tableau, et dans le résultat d'écrire uniquement le nombre d'unités dans ce tableau. Lors de l'exécution de l'opération ET sur plus de n nombres de bits, un résultat de n bits sera et il suffira seulement de savoir combien de bits sont définis parmi n. Le nombre de bits défini dans le nombre est inchangé, ce qui signifie que vous pouvez compter ces nombres. Il ne sert à rien de compter pour 64 bits, car on ne trouvera pas autant de RAM. Pour 32 bits, vous pouvez déjà trouver de l'espace sur les ordinateurs modernes, mais c'est encore beaucoup. La mémoire de moins de 16 bits n'est pas difficile à trouver, mais le calcul sera relativement long. Comme compromis, calculons pour les nombres à 8 bits:

 static readonly byte[] CountOfSettedBits = GenerateCountOfSettedBits(); static byte[] GenerateCountOfSettedBits() { //  result   i      i- . byte[] result = new byte[256]; //  ,      i   , //        int[] b = new int[8]; //     for (int i = 1; i < 256; i++) { //       int settedBitsCount = 0; //,       int m = 1; //   for (int j = 0; j < 8; j++) { //     b[j] += m; //  ,       2. m = b[j] >> 1; //        b[j] = b[j] & 1; //,        settedBitsCount += b[j]; } result[i] = (byte) settedBitsCount; //   } return result; } 

maintenant le constructeur TagsGroup ressemble à ceci:

 const int BucketSize = 8; public TagsGroup(bool[] innerTags) { if (innerTags == null) throw new ArgumentException(nameof(innerTags)); if (innerTags.Length != TagsGroupLength) { throw new ArgumentException(nameof(innerTags)); } int index = 0; //    InnerTags = new byte[TagsGroupLength / BucketSize]; //   for (int i = 0; i < TagsGroupLength / BucketSize; i++) { //     for (int j = 0; j < BucketSize; j++, index++) { //    2,      InnerTags[i] <<= 1; //    InnerTags[i] += (byte) (innerTags[index] ? 1 : 0); } } } 

Et MeasureSimilarity commencé à ressembler à ceci:

 public static int MeasureSimilarity(TagsGroup a, TagsGroup b) { int result = 0; for (int i = 0; i < TagsGroupLength / BucketSize; i++) { int t = a.InnerTags[i] & b.InnerTags[i]; result += CountOfSettedBits[t]; } return result; } 

Vous pouvez exécuter une grande référence et vous assurer que tout va mieux:

Est-il possible de rendre la méthode MeasureSimilarity encore plus rapide? Bien sûr! Pour ce faire, il suffit de se rendre compte que les registres à usage général sont désormais majoritairement 64 bits, et que nous y enregistrons des données huit bits. Pour ce faire, augmentez la taille de paquet dans laquelle les balises d'origine sont empaquetées, augmentez à 64 bits et réécrivez les méthodes nécessaires:

 const int BucketSize = 64; ulong[] InnerTags { get; } public static int MeasureSimilarity(TagsGroup a, TagsGroup b) { int result = 0; for (int i = 0; i < TagsGroupLength / BucketSize; i++) { ulong t = a.InnerTags[i] & b.InnerTags[i]; for (int j = 0; j < BucketSize / 8; j++) { result += CountOfSettedBits[t & 255]; t >>= 8; } } return result; } 

et il s'avère:

Ensuite, vous pouvez étendre la boucle intérieure:

 public static int MeasureSimilarity(TagsGroup a, TagsGroup b) { int result = 0; for (int i = 0; i < TagsGroupLength / BucketSize; i++) { ulong t = a.InnerTags[i] & b.InnerTags[i]; result += CountOfSettedBits[t & 255]; t >>= 8; result += CountOfSettedBits[t & 255]; t >>= 8; result += CountOfSettedBits[t & 255]; t >>= 8; result += CountOfSettedBits[t & 255]; t >>= 8; result += CountOfSettedBits[t & 255]; t >>= 8; result += CountOfSettedBits[t & 255]; t >>= 8; result += CountOfSettedBits[t & 255]; t >>= 8; result += CountOfSettedBits[t & 255]; } return result; } 

Est-ce encore plus rapide? Oui! Si vous utilisez les innovations de .NET Core 3.0. Bien que cette version soit toujours dans l'aperçu, mais dès le début il y a une implémentation de certains intrinsèques. Le Guide Intel Intrinsic a le _mm_popcnt_u64 intrinsèque. Qui, comme décrit: " Comptez le nombre de bits mis à 1 dans un entier 64 bits non signé a, et renvoyez ce nombre en dst. ". C'est exactement ce que nous essayons de réaliser! Dans .NET Core 3.0 Preview 5, cet intrinsèque est implémenté dans System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount (Comme indiqué correctement dans les commentaires de a-tk, avant d'utiliser intrinsèque, vous devez vérifier que le processeur les prend en charge. Dans ce cas, vérifiez l'état du System.Runtime.Intrinsics.X86.Popcnt.X64.IsSupported . System.Runtime.Intrinsics.X86.Popcnt.X64.IsSupported ). En l'utilisant, le code de la méthode MeasureSimilarity deviendra:

 public static int MeasureSimilarity(TagsGroup a, TagsGroup b) { int result = 0; for (int i = 0; i < TagsGroupLength / BucketSize; i++) { ulong t = a.InnerTags[i] & b.InnerTags[i]; result += (int) System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount(t); } return result; } 

et temps d'exécution:

Impressionnant.
Je ne connais pas les moyens qui peuvent accélérer considérablement la MeasureSimilarity et en même temps ne pas gâcher considérablement la lisibilité. Je pense que vous pouvez mettre fin à cette méthode.

Structures de données

Nous allons maintenant GetFiftyMostSimilarGroups le corps de la boucle dans la méthode GetFiftyMostSimilarGroups :

 public TagsGroup[] GetFiftyMostSimilarGroups(TagsGroup value) { const int resultLength = 50; List<TagsSimilarityInfo> list = new List<TagsSimilarityInfo>(50); for (int groupIndex = 0; groupIndex < Groups.Length; groupIndex++) { TagsGroup tagsGroup = Groups[groupIndex]; int similarityValue = TagsGroup.MeasureSimilarity(value, tagsGroup); TagsSimilarityInfo newInfo = new TagsSimilarityInfo(groupIndex, similarityValue); if (list.Count == resultLength && list[resultLength - 1].CompareTo(newInfo) == -1) { continue; } int index = ~list.BinarySearch(newInfo); list.Insert(index, newInfo); if (list.Count > resultLength) { list.RemoveAt(resultLength); } } TagsGroup[] result = new TagsGroup[resultLength]; for (int i = 0; i < resultLength; i++) { result[i] = Groups[list[i].Index]; } return result; } 

Permettez-moi de rappeler brièvement ce qui se passe ici:

• à l'intérieur de la liste, une liste triée des cinquante groupes de balises les plus appropriés est stockée, en fait du plus petit au plus grand, si vous comparez TagsSimilarityInfo ;
• insérer le nouveau groupe en question dans la liste tout en conservant le tri;
• s'il y a plus de cinquante éléments dans la liste, supprimez le groupe le moins similaire (son objet info sera le plus grand et se trouvera à la fin de la list );

C'est-à-dire il s'avère que nous devons trouver très rapidement le plus grand élément de la collection, pouvoir insérer et supprimer rapidement. Pour résoudre ces problèmes, il existe des structures de données spéciales. La première chose qui me vient à l'esprit est un groupe . Son insertion est réalisée en O (log N), obtenant le maximum en O (1), supprimant un élément en O (log N). Le seul problème est que le tas ne peut pas être itéré par les éléments croissants sans le modifier. Il n'y a pas de tas binaire dans BCL, donc je l'ai écrit moi-même:

 public class BinaryHeap<T>:IEnumerable<T> where T : IComparable<T> { readonly List<T> innerList; public BinaryHeap(int capacity) { innerList = new List<T>(capacity); } public int Count => innerList.Count; public T Max => innerList[0]; public void Add(T value) { innerList.Add(value); int i = Count - 1; int parent = (i - 1) >> 1; while (i > 0 && innerList[parent].CompareTo(innerList[i]) == -1) { Swap(i, parent); i = parent; parent = (i - 1) >> 1; } } void Swap(int a, int b) { T temp = innerList[a]; innerList[a] = innerList[b]; innerList[b] = temp; } void Heapify(int i) { for (;;) { int leftChild = (i << 1) | 1; int rightChild = (i + 1) << 1; int largestChild = i; if (leftChild < Count && innerList[leftChild].CompareTo(innerList[largestChild]) == 1) { largestChild = leftChild; } if (rightChild < Count && innerList[rightChild].CompareTo(innerList[largestChild]) == 1) { largestChild = rightChild; } if (largestChild == i) { break; } Swap(i, largestChild); i = largestChild; } } public void RemoveMax() { innerList[0] = innerList[Count - 1]; innerList.RemoveAt(Count - 1); Heapify(0); } public IEnumerator<T> GetEnumerator() { return innerList.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable) innerList).GetEnumerator(); } } 

l'implémentation correspondante de la méthode GetFiftyMostSimilarGroups se trouve dans le code source de l'article (lien ci-dessous).
En plus du tas, un arbre de recherche binaire peut apparaître. Un arbre de recherche binaire équilibré peut fournir une insertion pour O (log N), obtenir un maximum pour O (log N), supprimer un élément pour O (log N). L'avantage de cette structure est qu'elle peut être itérée dans l'ordre croissant et, en outre, l'arborescence de recherche rouge-noir dans BCL est implémentée dans SortedSet (dans un grand cadre, l'obtention d'un maximum est beaucoup plus lente que dans .netcore 3.0 et alloue de la mémoire). L'implémentation de GetFiftyMostSimilarGroups pour GetFiftyMostSimilarGroups peut être trouvée dans le code source de l'article.
Résultats de référence pour les trois implémentations GetFiftyMostSimilarGroups :

L'implémentation d'origine avec une feuille gagne presque partout dans le temps, et certainement partout dans la mémoire. Cela se produit du fait que pour un algorithme avec une feuille, l'insertion est effectuée dans O (log N) pour la recherche, et presque O (1) pour l'insertion, car la copie d'un si petit nombre d'éléments se produit très rapidement, obtenant un maximum pour O (1), supprimant un élément également pour O (1), car dans .net, la suppression du dernier élément de la feuille est remplacée par l'écriture dans le dernier élément d'une valeur vide (dans le noyau .net, rien n'est écrit dans les structures). S'il fallait donner non pas 50, mais disons 1000 des groupes les plus similaires, alors très probablement, un algorithme avec une feuille ne fonctionnerait pas. En fait, tout cela est un petit raisonnement spéculatif, car Vous pouvez toujours ajuster chacun des algorithmes.

Multithreading

Il reste maintenant à essayer d'améliorer la boucle elle-même dans GetFiftyMostSimilarGroups . Seul le multithreading vient à l'esprit. L'idée est de diviser la liste complète des groupes en plusieurs packages. Dans chaque package, trouvez les 50 groupes de balises les plus similaires, puis parmi eux, trouvez les 50 derniers groupes les plus similaires.
La version multithread de GetFiftyMostSimilarGroups ressemble à ceci:

 public TagsGroup[] GetFiftyMostSimilarGroupsMultiThread(TagsGroup value) { const int resultLength = 50; // ,     const int threadsCount = 4; //   int bucketSize = Groups.Length / threadsCount; var tasks = new Task<List<TagsSimilarityInfo>>[threadsCount]; for (int i = 0; i < threadsCount; i++) { int leftIndex = i * bucketSize; //    int rightIndex = (i + 1) * bucketSize; //    //    tasks[i] = Task<List<TagsSimilarityInfo>>.Factory.StartNew(() => GetFiftyMostSimilarGroupsMultiThreadCore(value, leftIndex, rightIndex)); } Task.WaitAll(tasks); //    var taskResults = new List<TagsSimilarityInfo>[threadsCount]; for (int i = 0; i < threadsCount; i++) { taskResults[i] = tasks[i].Result; } //      return MergeTaskResults(resultLength, threadsCount, taskResults); } 

GetFiftyMostSimilarGroupsMultiThreadCore GetFiftyMostSimilarGroups :

 List<TagsSimilarityInfo> GetFiftyMostSimilarGroupsMultiThreadCore(TagsGroup value, int leftIndex, int rightIndex) { const int resultLength = 50; List<TagsSimilarityInfo> list = new List<TagsSimilarityInfo>(resultLength); for (int groupIndex = leftIndex; groupIndex < rightIndex; groupIndex++) { TagsGroup tagsGroup = Groups[groupIndex]; int similarityValue = TagsGroup.MeasureSimilarity(value, tagsGroup); TagsSimilarityInfo newInfo = new TagsSimilarityInfo(groupIndex, similarityValue); if (list.Count == resultLength && list[resultLength - 1].CompareTo(newInfo) == -1) { continue; } int index = ~list.BinarySearch(newInfo); list.Insert(index, newInfo); if (list.Count > resultLength) { list.RemoveAt(resultLength); } } return list; } 

MergeTaskResults . - taskResults . , , . , threadsCount , : , , , :

 TagsGroup[] MergeTaskResults(int resultLength, int threadsCount, List<TagsSimilarityInfo>[] taskResults) { TagsGroup[] result = new TagsGroup[resultLength]; int[] indices = new int[threadsCount]; for (int i = 0; i < resultLength; i++) { int minIndex = 0; TagsSimilarityInfo currentBest = taskResults[minIndex][indices[minIndex]]; for (int j = 0; j < threadsCount; j++) { var current = taskResults[j][indices[j]]; if (current.CompareTo(currentBest) == -1) { minIndex = j; currentBest = taskResults[minIndex][indices[minIndex]]; } } int groupIndex = currentBest.Index; result[i] = Groups[groupIndex]; indices[minIndex]++; } return result; } 

• indices taskResults ;
• minIndex — taskResults , ;
• currentBest — - ;
• current — - ;

:

. . , , 4 50. , , .