Beberapa waktu yang lalu, kolega saya meminta saya untuk membantunya dengan satu masalah. Saya memecahkan masalah untuknya, tetapi di samping itu, bagi saya tampaknya pada pemecahan masalah ini, beberapa algoritma dan teknik pemrograman dapat dijelaskan. Dan juga menunjukkan percepatan waktu eksekusi algoritma dari 25 detik menjadi 40 ms.

Pernyataan masalah

Untuk proyek pribadi, kolega saya membutuhkan algoritma untuk menemukan lima puluh video paling mirip untuk video yang diberikan. Kesamaan itu seharusnya diperkirakan dengan jumlah tag terbuka yang cocok. Semakin banyak tag yang cocok dengan video, semakin mirip. Dari sini kita dapat langsung menarik beberapa kesimpulan:

• Semua tag di bawah video dapat digabungkan menjadi satu grup;
• pasti tidak akan ada lagi grup seperti itu daripada video itu sendiri;
• jika video tersebut mirip dengan video lain dari grup tag tertentu, maka itu sama dengan video lain dari grup ini;

Ternyata cukup untuk hanya bekerja dengan grup tag. Pada versi pertama, seorang kolega memutuskan untuk menyimpan tag di tabel tag: setiap video memiliki tautan ke ID grup tag, dan grup itu sendiri adalah urutan nilai Boolean yang menunjukkan apakah tag yang sesuai telah diatur. Di C #, grup tag terlihat seperti ini:

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

Seorang kolega menyarankan bahwa di situs ia akan memiliki tidak lebih dari satu juta video, dan berbagai tag tidak lebih dari 4000, untuk akun bulat Anda dapat mengambil 4096 = 2 ^ 12.
Kemudian kelas TagsGroup dapat direpresentasikan seperti ini:

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

Sekarang Anda perlu memeriksa kesamaan kedua kelompok tag. Dalam kondisi saat ini, ini berubah menjadi pemeriksaan sederhana untuk true dalam elemen yang sesuai dari array InnerTags dari dua kelompok tag:

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

Sekarang tinggal menghitung kemiripan grup tag yang diinginkan dengan setiap grup yang ada dan memilih lima puluh yang paling mirip. Saya mengatur sendiri kondisi lain untuk memastikan stabilitas sampel, mis. dalam sampel akhir, akan ada lima puluh tag grup yang MeasureSimilarity memberikan hasil tertinggi, sedangkan grup tag dengan MeasureSimilarity sama MeasureSimilarity indeks yang lebih rendah bagi mereka yang memiliki indeks lebih rendah di grup asli yang ada. Detail lebih lanjut dapat ditemukan, misalnya, di sini: https://ru.wikipedia.org/wiki/Sustainable_Sort .
Untuk mengatasi masalah ini, saya memutuskan untuk membuat kelas SimilarTagsCalculator , berikut adalah kodenya:

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

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

Saya menyiapkan tiga tolok ukur untuk algoritma ini:

• tolok ukur yang sepenuhnya acak, mis. jumlah tag yang ditetapkan dalam grup adalah acak dan grup tag yang akan kita bandingkan juga acak;
• jumlah tag yang diatur dalam grup meningkat, kami akan membandingkannya dengan grup yang menetapkan semua tag. Ternyata beberapa grup tag terakhir harus yang paling cocok;
• sama seperti di atas, tetapi jumlah tag yang terbuka berkurang. 50 grup tag pertama akan paling cocok;

Berikut adalah hasil patokan untuk sejuta grup:

BenchmarkDotNet = v0.11.5, OS = Windows 10.0.17134.765 (1803 / April2018Update / Redstone4)
Intel Core i7-6700 CPU 3.40GHz (Skylake), 1 CPU, 8 core logis dan 4 fisik
Frekuensi = 3328126 Hz, Resolusi = 300.4694 ns, Timer = TSC
.NET Core SDK = 3.0.100-preview5-011568
[Host]: .NET Core 3.0.0-preview5-27626-15 (CoreCLR 4.6.27622.75, CoreFX 4.700.19.22408), 64bit RyuJIT

Penyebaran waktu eksekusi sangat besar, selain 25 detik adalah waktu yang sangat lama, kolega saya tidak setuju untuk menunggu begitu lama. Jadi mari kita lakukan optimasi. Sekarang ada tiga bidang utama untuk mempercepat program:

• Metode MeasureSimilarity ;
• sebuah algoritma dalam tubuh loop di GetFiftyMostSimilarGroups ;
• loop itu sendiri di GetFiftyMostSimilarGroups ;

Kami akan mempertimbangkan masing-masing dari tiga arah secara berurutan.

Prediksi cabang

Pertama, pertimbangkan metode 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; } 

Di benchmark sebelumnya, ada variasi yang sangat besar dalam runtime antara tes acak dan yang berurutan. Grup tag untuk pengujian berurutan dibuat dengan prinsip berikut:

• jumlah kelompok yang diperlukan dibagi menjadi beberapa paket. Jumlah paket - jumlah maksimum tag dalam grup;
• untuk setiap grup dalam paket ke-i, tag i pertama ditetapkan;

Ternyata setiap kelompok tag dalam pengujian ini terdiri dari dua bagian berturut-turut dari tag yang terbuka dan tidak terbuka. MeasureSimilarity memiliki semua prasyarat untuk prediksi cabang prosesor untuk memiliki efek signifikan dalam kondisi saat ini. Untuk memeriksanya, cukup tulis patokan yang membandingkan runtime MeasureSimilarity untuk data acak dan yang berurutan:

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

Satu juta grup tag diuji, tetapi pada Sorted di setiap grup pada awalnya ada beberapa tag yang terbuka, dan yang tidak terpapar, dan di Unsorted jumlah yang sama dari tag yang terbuka tersebar secara acak di seluruh grup.
Perbedaan 5 detik sangat mengesankan, dan sesuatu harus dilakukan. Untuk menyingkirkan pengaruh prediksi cabang dan umumnya mempercepat metode ini, Anda harus menyingkirkan cabang itu sendiri. Hanya ada satu cabang di MeasureSimilarity - memeriksa bahwa tag yang sesuai diatur dalam dua kelompok. Mari kita perkirakan dalam kondisi mana kondisinya akan benar, untuk ini kita akan membuat tabel kebenaran kondisi:

Tabel kebenaran sepenuhnya bertepatan dengan logika "DAN", mis. hasilnya benar jika dan hanya jika kedua tag itu benar, maka kondisinya dapat dikurangi menjadi: if (a.InnerTags[i] && b.InnerTags[i]) . Tetapi dengan cara ini kondisinya masih tetap. Pada langkah berikutnya, kami akan memastikan bahwa penambahan untuk hasil selalu dilakukan, untuk ini kami menulis ulang badan loop seperti ini:

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

Kami masih belum menyingkirkan kondisinya dan bahkan malah membuat metode ini lebih lambat. Tetapi sekarang sudah menjadi jelas bahwa jika jenis InnerTags diubah dari bool ke byte (1 untuk true, dan 0 untuk false), maka Anda dapat menyingkirkan kondisi di operator ternary. Maka kelas TagsGroup akan terlihat seperti ini:

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

Berikut adalah hasil patokan untuk MeasureSimilarity diperbarui:

tetapi untuk bechmark utama yang diperbarui:

Menurut saya, itu sudah bagus. Bagi mereka yang yakin bahwa semua akselerasi terjadi hanya karena tipe boolean diganti dengan byte, saya meluncurkan tolok ukur untuk badan loop seperti itu:

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

dan ini hasilnya:

Pengemasan data

Setiap grup memiliki banyak tag, dan jumlahnya tidak dapat dikurangi dengan cara apa pun. Selain itu, Anda harus membandingkan tag dengan indeks yang sama, dan Anda tidak dapat memberikan jawaban akhir tanpa memeriksa semua tag. Jadi, bagaimanapun juga, kita harus mengulangi seluruh kelompok tag. Akan lebih baik untuk dapat memparalelkan tugas ini, sehingga mungkin untuk memproses beberapa tag dalam satu operasi bersyarat. Anda dapat melakukan ini melalui paralelisasi nyata, atau Anda bisa melalui pengemasan data khusus, yang akan kami gunakan. Setiap tag sekarang mewakili 1 atau 0. Dalam result hasil operasi "DAN" hanya diakumulasikan. Tetapi operasi logis yang sama dapat diterapkan tidak hanya untuk nomor bit tunggal. C # memungkinkan Anda untuk melakukan ini tanpa masalah hingga angka 64 bit (Anda dapat melakukan lebih banyak melalui BitArray , tapi bukan itu). Jika kami mewakili dua grup tag sebagai satu set angka 64 bit dengan set bit yang sesuai, maka akan dimungkinkan untuk melakukan operasi "DAN" pada setiap grup nomor 64 bit tersebut. Tidak jelas apa yang harus dilakukan dengan hasilnya. Mari kita lihat kembali isi loop:

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

hasil bertambah 1 setiap kali t == 1 dan tidak berubah ketika t == 0. Akibatnya, hasilnya akan sama dengan berapa kali hasil a.InnerTags[i] & b.InnerTags[i] adalah satu. Oleh karena itu, dimungkinkan untuk menyimpan semua hasil dari a.InnerTags[i] & b.InnerTags[i] dalam beberapa jenis array, dan dalam hasilnya tulis hanya jumlah unit dalam array ini. Saat melakukan operasi AND pada lebih dari angka n-bit, hasil n-bit akan cukup dan hanya cukup untuk mengetahui berapa banyak bit yang ditetapkan di antara n. Jumlah bit yang diatur dalam angka tidak berubah, yang berarti Anda dapat menghitung angka-angka ini. Tidak ada gunanya menghitung untuk 64 bit, seperti kami tidak akan menemukan begitu banyak RAM. Untuk 32 bit Anda sudah dapat menemukan ruang pada komputer modern, tetapi ini masih sangat banyak. Memori di bawah 16 bit tidak sulit ditemukan, tetapi perhitungannya akan relatif lama. Sebagai kompromi, mari kita hitung untuk angka 8 bit:

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

sekarang konstruktor TagsGroup terlihat seperti ini:

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

Dan MeasureSimilarity mulai terlihat seperti ini:

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

Anda dapat menjalankan tolok ukur besar dan memastikan semuanya lebih baik:

Apakah mungkin untuk membuat metode MeasureSimilarity lebih cepat? Tentu saja! Untuk melakukan ini, cukup menyadari fakta bahwa register tujuan umum sekarang kebanyakan 64 bit, dan kami menggerakkan data delapan-bit di dalamnya. Untuk melakukan ini, tambah ukuran paket ke mana tag asli dikemas, tambah menjadi 64 bit dan tulis ulang metode yang diperlukan:

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

dan ternyata:

Kemudian Anda dapat memperluas loop dalam:

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

Apakah ini lebih cepat? Ya! Jika Anda menggunakan inovasi dari .NET Core 3.0. Meskipun versi ini masih dalam pratinjau, tetapi sejak awal ada implementasi beberapa intrinsik. Intel Intrinsic Guide memiliki _mm_popcnt_u64 intrinsik. Yang, seperti dijelaskan: " Hitung jumlah bit yang ditetapkan ke 1 dalam integer 64-bit unsigned, dan kembalikan jumlah itu dalam dst. ". Inilah yang ingin kami capai! Dalam .NET Core 3.0 Preview 5, intrinsik ini diimplementasikan dalam System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount (Sebagaimana dicatat dengan benar dalam komentar a-tk , Anda harus memverifikasi bahwa prosesor mendukungnya sebelum menggunakan intrinsik. Dalam kasus ini, periksa kondisi System.Runtime.Intrinsics.X86.Popcnt.X64.IsSupported ). Dengan menggunakannya, kode metode MeasureSimilarity akan menjadi seperti ini:

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

dan waktu eksekusi:

Mengesankan.
Saya tidak tahu cara yang secara signifikan dapat mempercepat MeasureSimilarity dan pada saat yang sama tidak terlalu merusak keterbacaan. Saya pikir Anda dapat mengakhiri metode ini.

Struktur data

Sekarang kita akan GetFiftyMostSimilarGroups dengan isi loop dalam metode 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; } 

Biarkan saya mengingat secara singkat apa yang terjadi di sini:

• di dalam daftar, daftar diurutkan dari lima puluh grup tag yang paling sesuai disimpan, bahkan dari yang lebih kecil ke yang lebih besar, jika Anda membandingkan TagsSimilarityInfo ;
• masukkan grup baru tersebut ke dalam daftar sambil mempertahankan penyortiran;
• jika ada lebih dari lima puluh elemen dalam daftar, maka hapus grup yang paling mirip (objek info-nya akan menjadi yang terbesar dan akan berada di bagian paling akhir list );

Yaitu ternyata kita perlu menemukan elemen terbesar dalam koleksi dengan sangat cepat, agar dapat dengan cepat menyisipkan dan menghapus. Untuk mengatasi masalah seperti itu, ada struktur data khusus. Hal pertama yang terlintas dalam pikiran adalah banyak . Sisipannya dilakukan dalam O (log N), mendapatkan maksimum dalam O (1), menghapus elemen dalam O (log N). Satu-satunya masalah adalah bahwa tumpukan tidak dapat diulangi oleh elemen yang meningkat tanpa mengubahnya. Tidak ada tumpukan biner di BCL, jadi saya menulisnya sendiri:

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

implementasi metode GetFiftyMostSimilarGroups sesuai dapat ditemukan dalam kode sumber artikel (tautan di bawah).
Selain tumpukan, pohon pencarian biner dapat muncul. Pohon pencarian biner seimbang dapat memberikan penyisipan untuk O (log N), mendapatkan maksimum untuk O (log N), menghapus elemen untuk O (log N). Keuntungan dari struktur seperti itu adalah bahwa ia dapat diulang dalam urutan menaik dan, di samping itu, pohon pencarian merah-hitam di BCL diimplementasikan di dalam SortedSet (dalam kerangka besar, memperoleh maksimum jauh lebih lambat daripada di .netcore 3.0 dan mengalokasikan memori). Implementasi GetFiftyMostSimilarGroups untuk SortedSet dapat ditemukan dalam kode sumber untuk artikel.
Hasil benchmark untuk ketiga implementasi GetFiftyMostSimilarGroups :

Implementasi asli dengan daun menang hampir di mana-mana dalam waktu, dan tentu saja di mana saja dalam memori. Ini terjadi karena fakta bahwa untuk suatu algoritma dengan lembar, penyisipan dilakukan dalam O (log N) untuk pencarian, dan hampir O (1) untuk penyisipan, karena menyalin sejumlah kecil elemen terjadi dengan sangat cepat, mendapatkan maksimum untuk O (1), menghapus elemen juga untuk O (1), karena di .net, menghapus elemen terakhir dari sheet diganti dengan menulis ke elemen terakhir nilai kosong (dalam .net core tidak ada yang ditulis ke struktur) Jika diminta untuk memberikan bukan 50, tetapi katakanlah 1000 dari kelompok yang paling mirip, maka kemungkinan besar, algoritma dengan lembar tidak akan berfungsi. Faktanya, semua ini adalah alasan spekulatif, karena Anda masih dapat menyesuaikan masing-masing algoritma.

Multithreading

Sekarang tetap mencoba untuk memperbaiki loop itu sendiri di GetFiftyMostSimilarGroups . Hanya multithreading yang muncul di pikiran. Idenya adalah untuk membagi seluruh daftar grup menjadi beberapa paket. Di setiap paket, temukan 50 grup tag paling mirip, dan di antara mereka menemukan 50 grup paling mirip.
Versi GetFiftyMostSimilarGroups multithreaded terlihat seperti ini:

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