Vor einiger Zeit bat mich mein Kollege, ihm bei einem Problem zu helfen. Ich habe das Problem für ihn gelöst, aber außerdem schien es mir, dass bei der Lösung dieses Problems verschiedene Programmieralgorithmen und -techniken erklärt werden können. Und zeigen Sie auch die Beschleunigung der Ausführungszeit des Algorithmus von 25 Sekunden auf 40 ms.

Erklärung des Problems

Für ein persönliches Projekt benötigte mein Kollege einen Algorithmus, um fünfzig ähnlichste Videos für ein bestimmtes Video zu finden. Die Ähnlichkeit sollte durch die Anzahl der übereinstimmenden exponierten Tags geschätzt werden. Je mehr Tags mit dem Video übereinstimmen, desto ähnlicher sind sie. Daraus können wir sofort mehrere Schlussfolgerungen ziehen:

• Alle Tags unter dem Video können zu einer Gruppe zusammengefasst werden.
• Es wird definitiv nicht mehr solche Gruppen geben als die Videos selbst;
• Wenn das Video einem anderen Video aus einer bestimmten Gruppe von Tags ähnlich ist, ähnelt es auch anderen Videos aus dieser Gruppe.

Es stellt sich heraus, dass es ausreicht, nur mit Tag-Gruppen zu arbeiten. In der ersten Version hat ein Kollege beschlossen, Tags in einer Tag-Tabelle zu speichern: Jedes Video hat einen Link zur Tag-Gruppen-ID, und die Gruppen selbst sind eine Folge von Booleschen Werten, die angeben, ob das entsprechende Tag festgelegt ist. In C # sieht eine Tag-Gruppe folgendermaßen aus:

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

Ein Kollege schlug vor, dass er nicht mehr als eine Million Videos auf der Website und nicht mehr als 4.000 verschiedene Tags haben würde. Für ein rundes Konto können Sie 4096 = 2 ^ 12 verwenden.
Dann kann die TagsGroup Klasse folgendermaßen dargestellt werden:

 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; } } 

Jetzt müssen Sie die beiden Gruppen von Tags auf Ähnlichkeit überprüfen. Unter den aktuellen Bedingungen wird dies zu einer einfachen Überprüfung auf true in den entsprechenden Elementen der InnerTags Arrays von zwei Gruppen von Tags:

 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; } 

Jetzt müssen Sie nur noch die Ähnlichkeit der gewünschten Tag-Gruppe mit jeder vorhandenen Gruppe berechnen und die fünfzig ähnlichsten auswählen. Ich habe mir eine andere Bedingung gestellt, um die Stabilität der Probe sicherzustellen, d.h. In der endgültigen Stichprobe gibt es fünfzig Tag-Gruppen, für die MeasureSimilarity das höchste Ergebnis MeasureSimilarity hat, während Tag-Gruppen mit derselben MeasureSimilarity niedrigeren Index für diejenigen haben, die in der ursprünglich vorhandenen Gruppe einen niedrigeren Index hatten. Weitere Details finden Sie beispielsweise hier: https://ru.wikipedia.org/wiki/Sustainable_Sort .
Um dieses Problem zu lösen, habe ich beschlossen, die SimilarTagsCalculator Klasse zu SimilarTagsCalculator . Hier ist der 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; } } 

und die TagsSimilarityInfo Struktur:

 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)}"); } } 

Ich habe drei Benchmarks für diesen Algorithmus vorbereitet:

• vollständig zufälliger Benchmark, d.h. Die Anzahl der gesetzten Tags in den Gruppen ist zufällig und die Tag-Gruppe, mit der wir vergleichen werden, ist ebenfalls zufällig.
• Die Anzahl der in Gruppen festgelegten Tags nimmt zu. Wir werden sie mit der Gruppe vergleichen, in der alle Tags festgelegt sind. Es stellt sich heraus, dass einige der letzten Gruppen von Tags am besten geeignet sein sollten.
• das gleiche wie oben, aber die Anzahl der exponierten Tags nimmt ab. Die ersten 50 Gruppen von Tags sind am besten geeignet.

Hier sind die Benchmark-Ergebnisse für eine Million Gruppen:

BenchmarkDotNet = v0.11.5, OS = Windows 10.0.17134.765 (1803 / April2018Update / Redstone4)
Intel Core i7-6700 CPU 3,40 GHz (Skylake), 1 CPU, 8 logische und 4 physische Kerne
Frequenz = 3328126 Hz, Auflösung = 300,4694 ns, Timer = TSC
.NET Core SDK = 3.0.100-Vorschau5-011568
[Host]: .NET Core 3.0.0-Vorschau5-27626-15 (CoreCLR 4.6.27622.75, CoreFX 4.700.19.22408), 64-Bit-RyuJIT

Die Streuung der Ausführungszeit ist sehr groß, außerdem sind 25 Sekunden eine sehr lange Zeit, mein Kollege stimmt nicht zu, so lange zu warten. Lassen Sie uns also Optimierungen vornehmen. Jetzt gibt es drei Hauptbereiche, um das Programm zu beschleunigen:

• MeasureSimilarity Methode;
• ein Algorithmus im Hauptteil der Schleife in GetFiftyMostSimilarGroups ;
• die Schleife selbst in GetFiftyMostSimilarGroups ;

Wir werden jede der drei Richtungen nacheinander betrachten.

Verzweigungsvorhersage

Betrachten Sie zunächst die MeasureSimilarity Methode.

 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; } 

Im vorherigen Benchmark gab es eine sehr große Variation in der Laufzeit zwischen dem Zufallstest und einem der sequentiellen. Tag-Gruppen für sequentielle Tests wurden nach folgendem Prinzip erstellt:

• Die erforderliche Anzahl von Gruppen wurde in Pakete aufgeteilt. Anzahl der Pakete - die maximale Anzahl der Tags in der Gruppe;
• Für jede Gruppe im i-ten Paket wurden die ersten i-Tags festgelegt.

Es stellt sich heraus, dass jede Gruppe von Tags in diesen Tests aus zwei aufeinanderfolgenden Teilen von belichteten und nicht belichteten Tags besteht. MeasureSimilarity hat alle Voraussetzungen, damit die Vorhersage des Prozessorzweigs unter den aktuellen Bedingungen einen signifikanten Effekt hat. Um dies zu überprüfen, schreiben Sie einfach einen Benchmark, der die Laufzeit von MeasureSimilarity für zufällige und für sequentielle Daten vergleicht:

 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); 

Eine Million Tag-Gruppen wurden getestet, aber in Sorted in jeder Gruppe gab es zuerst mehrere exponierte Tags und dann nicht exponierte, und in Unsorted die gleiche Anzahl exponierter Tags zufällig über die Gruppe verteilt.
Der Unterschied von 5 Sekunden ist beeindruckend und es muss etwas getan werden. Um den Einfluss der Verzweigungsvorhersage zu beseitigen und die Methode im Allgemeinen zu beschleunigen, müssen Sie die Verzweigungen selbst beseitigen. In MeasureSimilarity gibt es nur einen Zweig. Überprüfen Sie, ob die entsprechenden Tags in zwei Gruppen festgelegt sind. Lassen Sie uns abschätzen, in welchen Fällen die Bedingung wahr sein wird. Dazu erstellen wir eine Tabelle mit der Wahrheit der Bedingung:

Die Wahrheitstabelle stimmt vollständig mit dem logischen "UND" überein, d.h. Das Ergebnis ist genau dann wahr, wenn beide Tags wahr sind. Dann kann die Bedingung auf if (a.InnerTags[i] && b.InnerTags[i]) reduziert werden: if (a.InnerTags[i] && b.InnerTags[i]) . Auf diese Weise bleibt der Zustand jedoch bestehen. Im nächsten Schritt stellen wir sicher, dass die Addition zum Ergebnis immer durchgeführt wird. Dazu schreiben wir den Körper der Schleife wie folgt um:

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

Wir haben den Zustand immer noch nicht beseitigt und die Methode sogar langsamer gemacht. Jetzt ist jedoch klar geworden, dass Sie die Bedingung im ternären Operator InnerTags , wenn der Typ von InnerTags von bool in byte geändert wird (1 für true und 0 für false). Dann TagsGroup die TagsGroup Klasse folgendermaßen aus:

 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); } } } 

Hier sind die Benchmark-Ergebnisse für die aktualisierte MeasureSimilarity :

aber für das aktualisierte Hauptbechmark:

Meiner Meinung nach war es schon toll. Für diejenigen, die davon überzeugt waren, dass die gesamte Beschleunigung nur stattfand, weil der boolesche Typ durch ein Byte ersetzt wurde, habe ich einen Benchmark für einen solchen Schleifenkörper gestartet:

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

und das sind die Ergebnisse:

Datenverpackung

Jede Gruppe hat viele Tags und ihre Anzahl kann in keiner Weise reduziert werden. Außerdem müssen Sie Tags mit demselben Index vergleichen, und Sie können keine endgültige Antwort geben, ohne alle Tags zu überprüfen. In jedem Fall müssen wir also die gesamte Gruppe von Tags durchlaufen. Es wäre großartig, diese Aufgabe irgendwie parallelisieren zu können, so dass es möglich wäre, mehrere Tags in einer bedingten Operation zu verarbeiten. Sie können dies durch echte Parallelisierung oder durch spezielle Datenverpackungen tun, die wir verwenden werden. Jedes Tag steht jetzt für 1 oder 0. Im result Ergebnis der Operation "AND" einfach akkumuliert. Die gleiche logische Operation kann jedoch nicht nur auf Einzelbitzahlen angewendet werden. Mit C # können Sie dies problemlos bis zu 64-Bit-Zahlen tun (Sie können mehr über BitArray tun, aber das ist es nicht). Wenn wir zwei Gruppen von Tags als einen Satz von 64-Bit-Zahlen mit den entsprechenden gesetzten Bits darstellen, ist es möglich, eine "UND" -Operation für jede solche Gruppe von 64-Bit-Zahlen auszuführen. Es ist nicht klar, was mit dem Ergebnis zu tun ist. Schauen wir uns noch einmal den Körper der Schleife an:

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

Das Ergebnis erhöht sich jedes Mal um 1, wenn t == 1 ist, und ändert sich nicht, wenn t == 0. Als Ergebnis entspricht das Ergebnis, wie oft das Ergebnis von a.InnerTags[i] & b.InnerTags[i] eins war. Dementsprechend wäre es möglich, alle Ergebnisse von a.InnerTags[i] & b.InnerTags[i] in einer Art Array zu speichern und im Ergebnis nur die Anzahl der Einheiten in dieses Array zu schreiben. Wenn die UND-Operation für mehr als n-Bit-Zahlen ausgeführt wird, ergibt sich ein n-Bit-Ergebnis, und es reicht aus, nur zu wissen, wie viele Bits unter n gesetzt sind. Die Anzahl der in der Nummer gesetzten Bits bleibt unverändert, dh Sie können diese Nummern zählen. Es macht keinen Sinn, für 64 Bit zu zählen Wir werden nicht so viel RAM finden. Für 32 Bit finden Sie bereits Platz auf modernen Computern, aber das ist immer noch sehr viel. Speicher unter 16 Bit ist nicht schwer zu finden, aber die Berechnung ist relativ lang. Berechnen wir als Kompromiss 8-Bit-Zahlen:

 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; } 

Jetzt sieht der TagsGroup-Konstruktor folgendermaßen aus:

 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); } } } 

Und MeasureSimilarity aus:

 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; } 

Sie können einen großen Benchmark durchführen und sicherstellen, dass alles besser ist:

Ist es möglich, die MeasureSimilarity Methode noch schneller zu machen? Natürlich! Um dies zu tun, reicht es aus, die Tatsache zu erkennen, dass Allzweckregister jetzt meistens 64-Bit sind und wir 8-Bit-Daten in sie treiben. Erhöhen Sie dazu die Paketgröße, in die die ursprünglichen Tags gepackt werden, erhöhen Sie sie auf 64 Bit und schreiben Sie die erforderlichen Methoden neu:

 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; } 

und es stellt sich heraus:

Dann können Sie die innere Schleife erweitern:

 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; } 

Ist es noch schneller? Ja! Wenn Sie die Innovationen von .NET Core 3.0 verwenden. Diese Version befindet sich zwar noch in der Vorschau, aber von Anfang an gibt es eine Implementierung einiger Eigenheiten. Das Intel Intrinsic Guide enthält das intrinsische _mm_popcnt_u64 . Welche, wie beschrieben: " Zählen Sie die Anzahl der auf 1 gesetzten Bits in einer vorzeichenlosen 64-Bit-Ganzzahl a und geben Sie diese Anzahl in dst zurück. " Genau das wollen wir erreichen! In .NET Core 3.0 Preview 5 ist dieses Intrinsic in System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount implementiert (Wie in den Kommentaren von a-tk korrekt angegeben, müssen Sie überprüfen, ob der Prozessor sie unterstützt, bevor Sie Intrinsics verwenden. Überprüfen Sie in diesem Fall die System.Runtime.Intrinsics.X86.Popcnt.X64.IsSupported ). Wenn Sie es verwenden, MeasureSimilarity der Code der MeasureSimilarity Methode folgendermaßen aus:

 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; } 

und Ausführungszeit:

Beeindruckend.
Ich kenne die Möglichkeiten nicht, die MeasureSimilarity erheblich beschleunigen und gleichzeitig die Lesbarkeit nicht wesentlich MeasureSimilarity können. Ich denke, Sie können diese Methode beenden.

Datenstrukturen

Jetzt werden wir uns mit dem Hauptteil der Schleife in der GetFiftyMostSimilarGroups Methode 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; } 

Lassen Sie mich kurz daran erinnern, was hier passiert:

• Innerhalb der Liste wird eine sortierte Liste der fünfzig am besten geeigneten Tag-Gruppen gespeichert, und zwar von kleiner zu größer, wenn Sie TagsSimilarityInfo vergleichen.
• Fügen Sie die betreffende neue Gruppe unter Beibehaltung der Sortierung in die Liste ein.
• Wenn die Liste mehr als fünfzig Elemente enthält, löschen Sie die am wenigsten ähnliche Gruppe (ihr Info-Objekt ist das größte und befindet sich ganz am Ende der list ).

Das heißt, Es stellt sich heraus, dass wir sehr schnell das größte Element in der Sammlung finden müssen, um es schnell einfügen und löschen zu können. Um solche Probleme zu lösen, gibt es spezielle Datenstrukturen. Das erste, was mir in den Sinn kommt, ist ein Haufen . Ihre Einfügung erfolgt in O (log N), wobei das Maximum in O (1) ermittelt und ein Element in O (log N) entfernt wird. Das einzige Problem ist, dass der Heap nicht von den zunehmenden Elementen iteriert werden kann, ohne ihn zu ändern. Da es in BCL keinen binären Heap gibt, habe ich ihn selbst geschrieben:

 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(); } } 

Die entsprechende Implementierung der GetFiftyMostSimilarGroups Methode finden Sie im Quellcode des Artikels (Link unten).
Zusätzlich zum Heap wird möglicherweise ein binärer Suchbaum angezeigt. Ein ausgeglichener binärer Suchbaum kann das Einfügen von O (log N) ermöglichen, ein Maximum für O (log N) erhalten und ein Element für O (log N) entfernen. Der Vorteil einer solchen Struktur besteht darin, dass sie in aufsteigender Reihenfolge iteriert werden kann und außerdem der rot-schwarze Suchbaum in BCL in SortedSet implementiert ist (in einem großen Framework ist das Erhalten eines Maximums viel langsamer als in .netcore 3.0 und weist Speicher zu). Die Implementierung von GetFiftyMostSimilarGroups für SortedSet finden Sie im Quellcode des Artikels.
Benchmark-Ergebnisse für alle drei GetFiftyMostSimilarGroups Implementierungen:

Die ursprüngliche Implementierung mit einem Blatt gewinnt fast überall in der Zeit und sicherlich überall im Gedächtnis. Dies geschieht aufgrund der Tatsache, dass für einen Algorithmus mit einem Blatt die Einfügung in O (log N) für die Suche und fast O (1) für die Einfügung durchgeführt wird, weil Das Kopieren einer so kleinen Anzahl von Elementen erfolgt sehr schnell, wobei ein Maximum für O (1) erhalten wird und ein Element auch für O (1) gelöscht wird, weil In .net wird das Löschen des letzten Elements aus dem Blatt ersetzt, indem in das letzte Element ein leerer Wert geschrieben wird (im .net-Kern wird nichts in Strukturen geschrieben). Wenn es erforderlich wäre, nicht 50 auszugeben, aber sagen wir 1000 der ähnlichsten Gruppen, dann würde ein Algorithmus mit einem Blatt höchstwahrscheinlich nicht funktionieren. In der Tat ist dies alles eine kleine spekulative Argumentation, weil Sie können weiterhin jeden der Algorithmen anpassen.

Multithreading

Jetzt muss noch versucht werden, die Schleife selbst in GetFiftyMostSimilarGroups zu verbessern. Nur Multithreading fällt mir ein. Die Idee ist, die gesamte Liste der Gruppen in mehrere Pakete aufzuteilen. Suchen Sie in jedem Paket die 50 ähnlichsten Tag-Gruppen und unter ihnen die letzten 50 ähnlichsten.
Die Multithread-Version von GetFiftyMostSimilarGroups sieht GetFiftyMostSimilarGroups aus:

 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. , , .