कुछ समय पहले, मेरे सहयोगी ने मुझे एक समस्या के साथ उसकी मदद करने के लिए कहा। मैंने उसके लिए समस्या को हल किया, लेकिन इसके अलावा, मुझे यह प्रतीत हुआ कि इस समस्या को हल करने पर, कई प्रोग्रामिंग एल्गोरिदम और तकनीकों को समझाया जा सकता है। और 25 सेकंड से 40 एमएस तक एल्गोरिथ्म के निष्पादन समय के त्वरण को भी दिखाते हैं।

समस्या का बयान

एक व्यक्तिगत परियोजना के लिए, मेरे सहयोगी को किसी दिए गए वीडियो के लिए पचास समान वीडियो खोजने के लिए एक एल्गोरिथ्म की आवश्यकता थी। मिलान किए गए टैग की संख्या से समानता का अनुमान लगाया जाना चाहिए था। वीडियो जितने टैग्स से मेल खाते हैं, वे उतने ही मिलते-जुलते हैं। इससे हम तुरंत कई निष्कर्ष निकाल सकते हैं:

• वीडियो के तहत सभी टैग को एक समूह में जोड़ा जा सकता है;
• निश्चित रूप से वीडियो से अधिक ऐसे समूह नहीं होंगे;
• यदि वीडियो टैग के एक निश्चित समूह के अन्य वीडियो के समान है, तो यह इस समूह के अन्य वीडियो के समान है;

यह पता चला है कि यह केवल टैग समूहों के साथ काम करने के लिए पर्याप्त है। पहले संस्करण में, एक सहकर्मी ने टैग तालिका में टैग संग्रहीत करने का निर्णय लिया: प्रत्येक वीडियो में टैग समूह आईडी का एक लिंक होता है, और समूह स्वयं बूलियन मानों का एक क्रम होते हैं जो इंगित करते हैं कि संबंधित टैग सेट है या नहीं। C # में, एक टैग समूह इस तरह दिखता है:

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

एक सहकर्मी ने सुझाव दिया कि साइट पर उसके पास एक मिलियन से अधिक वीडियो नहीं होंगे, और विभिन्न टैग 4000 से अधिक नहीं हैं, एक गोल खाते के लिए आप 4096 = 2 ^ 12 ले सकते हैं।
फिर इस तरह से TagsGroup वर्ग का प्रतिनिधित्व किया जा सकता है:

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

अब आपको समानता के लिए टैग के दो समूहों की जांच करने की आवश्यकता है। वर्तमान स्थितियों के तहत, यह टैग के दो समूहों के InnerTags सरणियों के संबंधित तत्वों में सच के लिए एक सरल जांच में बदल जाता है:

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

अब यह केवल प्रत्येक मौजूदा समूह के साथ वांछित टैग समूह की समानता की गणना करने और केवल पचास समान लोगों का चयन करने के लिए बनी हुई है। मैंने नमूने की स्थिरता सुनिश्चित करने के लिए खुद को एक और शर्त निर्धारित की, अर्थात्। अंतिम नमूने में, पचास टैग समूह होंगे, जिसके लिए MeasureSimilarity ने उच्चतम परिणाम दिया, जबकि समान MeasureSimilarity टैग समूहों के MeasureSimilarity उन लोगों के लिए MeasureSimilarity कम सूचकांक MeasureSimilarity जिनके पास मूल मौजूदा समूह में कम सूचकांक था। अधिक विवरण पाया जा सकता है, उदाहरण के लिए, यहाँ: https://ru.wikipedia.org/wiki/Sistentable_Sort ।
इस समस्या को हल करने के लिए, मैंने इसी तरह के SimilarTagsCalculator क्लास बनाने का फैसला किया, यहाँ इसका कोड है:

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

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

मैंने इस एल्गोरिथम के लिए तीन बेंचमार्क तैयार किए:

• पूरी तरह से यादृच्छिक बेंचमार्क, अर्थात्। समूहों में सेट टैग की संख्या यादृच्छिक है और टैग समूह जिसकी हम तुलना करेंगे, वह भी यादृच्छिक है;
• समूहों में सेट किए गए टैग की संख्या बढ़ रही है, हम उस समूह के साथ तुलना करेंगे जिसमें सभी टैग सेट हैं। यह पता चला है कि टैग के अंतिम समूहों में से कुछ सबसे उपयुक्त होना चाहिए;
• ऊपर जैसा है, लेकिन उजागर टैग की संख्या कम हो रही है। टैग के पहले 50 समूह सबसे उपयुक्त होंगे;

यहां एक लाख समूहों के लिए बेंचमार्क परिणाम हैं:

बेंचमार्कडॉटनेट = v0.11.5, ओएस = विंडोज 10.0.17134.765 (1803 / अप्रैल 2018 यूपीडेट / रेडस्टोन 4)
Intel Core i7-6700 CPU 3.40GHz (Skylake), 1 CPU, 8 तार्किक और 4 भौतिक कोर
फ्रीक्वेंसी = 3328126 हर्ट्ज, रिज़ॉल्यूशन = 300.4694 एनएस, टाइमर = टीएससी
.NET कोर एसडीके = 3.0.100-पूर्वावलोकन 5-011568
[होस्ट]: .NET कोर 3.0.0-पूर्वावलोकन 5-27626-15 (CoreCLR 4.6.27622.75, CoreFX 4.700.19.22408), 64 बिट RyuJIT

निष्पादन समय का प्रसार बहुत बड़ा है, इसके अलावा 25 सेकंड बहुत लंबा समय है, मेरे सहयोगी इतने लंबे समय तक इंतजार करने के लिए सहमत नहीं हैं। तो चलो अनुकूलन करते हैं। अब कार्यक्रम को गति देने के लिए तीन मुख्य क्षेत्र हैं:

• MeasureSimilarity ;
• GetFiftyMostSimilarGroups में पाश के शरीर में एक एल्गोरिथ्म;
• GetFiftyMostSimilarGroups में स्वयं लूप;

हम क्रम में तीन दिशाओं में से प्रत्येक पर विचार करेंगे।

शाखा की भविष्यवाणी

सबसे पहले, 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; } 

पिछले बेंचमार्क में, यादृच्छिक परीक्षण और क्रमिक किसी के बीच रनटाइम में बहुत बड़ी भिन्नता थी। अनुक्रमिक परीक्षणों के लिए टैग समूह निम्नलिखित सिद्धांत द्वारा बनाए गए थे:

• समूहों की आवश्यक संख्या को संकुल में विभाजित किया गया था। पैकेट की संख्या - समूह में टैग की अधिकतम संख्या;
• i-th पैकेज में प्रत्येक समूह के लिए, पहले i टैग सेट किए गए थे;

यह पता चलता है कि इन परीक्षणों में टैग के प्रत्येक समूह में उजागर और अनएम्पोज़्ड टैग के दो लगातार भाग होते हैं। MeasureSimilarity में प्रोसेसर की पूर्व स्थिति के लिए सभी आवश्यक शर्तें हैं जो वर्तमान परिस्थितियों में महत्वपूर्ण प्रभाव डालती हैं। इसे जांचने के लिए, बस एक मानदंड लिखें, जो यादृच्छिक डेटा के लिए और अनुक्रमिक लोगों के लिए माप-क्षमता के क्रम की तुलना करता है:

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

एक लाख टैग समूहों का परीक्षण किया गया था, लेकिन पहले प्रत्येक समूह में Sorted से कई उजागर टैग थे, और फिर अनएक्सपोज़्ड वाले, और Unsorted में समान संख्या में उजागर किए गए टैग यादृच्छिक रूप से पूरे समूह में बिखरे हुए थे।
5 सेकंड का अंतर प्रभावशाली है, और कुछ करने की आवश्यकता है। शाखा भविष्यवाणी के प्रभाव से छुटकारा पाने के लिए और आम तौर पर इस विधि को गति देने के लिए, आपको खुद शाखाओं से छुटकारा पाने की आवश्यकता है। MeasureSimilarity में केवल एक शाखा है - यह जांचना कि संबंधित टैग दो समूहों में सेट किए गए हैं। आइए अनुमान लगाते हैं कि किन स्थितियों में स्थिति सही होगी, इसके लिए हम स्थिति की सच्चाई की एक तालिका बनाएंगे:

सत्य तालिका पूरी तरह से तार्किक "और" के साथ मेल खाती है, अर्थात। परिणाम सही है अगर और केवल यदि दोनों टैग सत्य हैं, तो स्थिति को कम किया जा सकता है: if (a.InnerTags[i] && b.InnerTags[i]) । लेकिन इस तरह से हालत अभी भी बनी हुई है। अगले चरण में, हम यह सुनिश्चित करेंगे कि परिणाम में वृद्धि हमेशा की जाती है, इसके लिए हम लूप के शरीर को फिर से लिखते हैं जैसे:

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

हमने अभी भी हालत से छुटकारा नहीं पाया है और वास्तव में भी इस विधि को धीमा कर दिया है। लेकिन अब यह स्पष्ट हो गया है कि अगर InnerTags प्रकार बूल से बाइट में बदल जाता है (सच के लिए 1, और गलत के लिए 0), तो आप टर्नरी ऑपरेटर में स्थिति से छुटकारा पा सकते हैं। तब TagsGroup क्लास इस तरह दिखाई देगी:

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

यहाँ अद्यतन MeasureSimilarity लिए बेंचमार्क परिणाम हैं:

लेकिन अद्यतन किए गए मुख्य बीचमार्क के लिए:

मेरी राय में, यह पहले से ही बहुत अच्छा था। उन लोगों के लिए जो आश्वस्त थे कि सभी त्वरण केवल इसलिए हुए क्योंकि बूलियन प्रकार को बाइट के साथ बदल दिया गया था, मैंने ऐसे लूप बॉडी के लिए एक बेंचमार्क लॉन्च किया:

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

और ये परिणाम हैं:

डेटा पैकेजिंग

प्रत्येक समूह के कई टैग हैं, और उनकी संख्या किसी भी तरह से कम नहीं की जा सकती है। इसके अलावा, आपको एक ही सूचकांक के साथ टैग्स की तुलना करनी चाहिए, और आप सभी टैगों की जांच किए बिना अंतिम जवाब नहीं दे सकते। इसलिए, किसी भी मामले में, हमें टैग के पूरे समूह पर पुनरावृति करनी होगी। इस कार्य को किसी भी तरह से समानांतर करने में सक्षम होना बहुत अच्छा होगा, ताकि एक सशर्त संचालन में कई टैग को संसाधित करना संभव होगा। आप इसे वास्तविक समानांतरकरण के माध्यम से कर सकते हैं, या आप विशेष डेटा पैकेजिंग के माध्यम से कर सकते हैं, जिसका हम उपयोग करेंगे। प्रत्येक टैग अब 1 या 0. का प्रतिनिधित्व करता है। परिणाम में, ऑपरेशन "AND" का परिणाम केवल जमा होता है। लेकिन एक ही तार्किक संचालन न केवल एकल-बिट संख्याओं पर लागू किया जा सकता है। C # आपको बिना किसी समस्या के 64 बिट नंबर तक करने की अनुमति देता है (आप BitArray माध्यम से अधिक कर सकते हैं, लेकिन ऐसा नहीं है)। यदि हम संबंधित बिट्स के सेट के साथ 64 बिट नंबरों के समूह के रूप में टैग के दो समूहों का प्रतिनिधित्व करते हैं, तो 64 बिट संख्याओं के ऐसे प्रत्येक समूह पर एक "और" ऑपरेशन करना संभव होगा। यह स्पष्ट नहीं है कि परिणाम के साथ क्या करना है। आइए फिर से लूप के शरीर पर नज़र डालें:

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

परिणाम 1 हर बार t == 1 से बढ़ता है और जब t == 0. नहीं बदलता है, तो परिणाम के रूप में परिणाम कितने बार के बराबर होगा। a.InnerTags[i] & b.InnerTags[i] एक था। तदनुसार, किसी सरणी में a.InnerTags[i] & b.InnerTags[i] सभी परिणाम सहेजना संभव होगा, और परिणाम में इस सरणी में केवल इकाइयों की संख्या लिखें। एन-बिट संख्या से अधिक पर एंड ऑपरेशन करते समय, एक एन-बिट परिणाम होगा और यह केवल यह जानने के लिए पर्याप्त होगा कि एन के बीच कितने बिट सेट हैं। संख्या में सेट बिट्स अपरिवर्तित हैं, जिसका अर्थ है कि आप इन संख्याओं को गिन सकते हैं। 64 बिट्स की गिनती के लिए कोई मतलब नहीं है, जैसा कि हमें इतनी रैम नहीं मिलेगी। 32 बिट्स के लिए आप पहले से ही आधुनिक कंप्यूटर पर जगह पा सकते हैं, लेकिन यह अभी भी बहुत अधिक है। 16 बिट्स के तहत मेमोरी को ढूंढना मुश्किल नहीं है, लेकिन गणना अपेक्षाकृत लंबी होगी। एक समझौते के रूप में, आइए 8 बिट संख्याओं के लिए गणना करें:

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

अब टैगग्रुप कंस्ट्रक्टर इस तरह दिखता है:

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

और MeasureSimilarity इस तरह दिखना शुरू हुई:

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

आप एक बड़ा बेंचमार्क चला सकते हैं और सुनिश्चित कर सकते हैं कि सब कुछ बेहतर है:

क्या MeasureSimilarity विधि को और भी तेज करना संभव है? बेशक! ऐसा करने के लिए, यह इस तथ्य को महसूस करने के लिए पर्याप्त है कि सामान्य प्रयोजन रजिस्टर अब ज्यादातर 64 बिट हैं, और हम उनमें आठ-बिट डेटा चलाते हैं। ऐसा करने के लिए, पैकेट का आकार बढ़ाएं जिसमें मूल टैग पैक किए गए हों, 64 बिट तक बढ़ें और आवश्यक विधियों को फिर से लिखें:

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

और यह पता चला है:

फिर आप आंतरिक लूप का विस्तार कर सकते हैं:

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

क्या यह और भी तेज है? हाँ! यदि आप .NET कोर 3.0 से नवाचारों का उपयोग करते हैं। हालांकि यह संस्करण अभी भी पूर्वावलोकन में है, लेकिन शुरुआत से ही कुछ आंतरिक विषयों का कार्यान्वयन है। इंटेल आंतरिक गाइड में आंतरिक _mm_popcnt_u64 । जैसा कि वर्णित है: " अहस्ताक्षरित 64-बिट पूर्णांक में 1 में सेट बिट्स की संख्या की गणना करें, और उस dst में लौटें। " यह वास्तव में हम क्या हासिल करने की कोशिश कर रहे हैं! .NET Core 3.0 पूर्वावलोकन 5 में, यह आंतरिक System.Runtime.Intrinsics.X86.Popcnt.X64.IsSupported System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount में लागू किया गया है (जैसा कि सही ढंग से एक tk की टिप्पणियों में उल्लेख किया गया है, आपको सत्यापित करना चाहिए कि प्रोसेसर आंतरिक का उपयोग करने से पहले उनका समर्थन करता है। इस मामले में, System.Runtime.Intrinsics.X86.Popcnt.X64.IsSupported स्थिति की जांच करें। System.Runtime.Intrinsics.X86.Popcnt.X64.IsSupported )। इसका उपयोग करते हुए, MeasureSimilarity विधि का कोड इस तरह बन जाएगा:

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

और निष्पादन समय:

प्रभावशाली।
मुझे उन तरीकों की जानकारी नहीं है, जो MeasureSimilarity काफी तेजी ला सकते हैं और साथ ही साथ पठनीयता को बहुत खराब नहीं करते हैं। मुझे लगता है कि आप इस विधि को समाप्त कर सकते हैं।

डेटा संरचनाएं

अब हम GetFiftyMostSimilarGroups विधि में लूप के शरीर के साथ 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; } 

मुझे संक्षेप में याद दिलाएं कि यहां क्या हो रहा है:

• सूची के अंदर, पचास सबसे उपयुक्त टैग समूहों की एक क्रमबद्ध सूची संग्रहीत की जाती है, वास्तव में छोटे से बड़े तक, यदि आप TagsSimilarityInfo तुलना TagsSimilarityInfo ;
• छँटाई को संरक्षित करते हुए सूची में नए समूह को सम्मिलित करें;
• यदि सूची में पचास से अधिक तत्व हैं, तो कम से कम समान समूह को हटा दें (इसकी जानकारी-वस्तु सबसे बड़ी होगी और list के बहुत अंत में होगी);

यानी यह पता चला है कि हमें संग्रह में सबसे बड़ा तत्व खोजने की आवश्यकता है, जल्दी से डालने और हटाने में सक्षम हो। ऐसी समस्याओं को हल करने के लिए, विशेष डेटा संरचनाएं हैं। पहली बात जो मन में आती है वह है एक गुच्छा । उसकी प्रविष्टि O (लॉग एन) में की जाती है, ओ (1 एन) में एक तत्व को हटाते हुए, ओ (1) में अधिकतम हो रही है। एकमात्र समस्या यह है कि ढेर को संशोधित किए बिना बढ़ते तत्वों द्वारा पुनरावृत्त नहीं किया जा सकता है। BCL में कोई बाइनरी हीप नहीं है, इसलिए मैंने इसे स्वयं लिखा:

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

GetFiftyMostSimilarGroups विधि का संगत कार्यान्वयन लेख के स्रोत कोड (नीचे लिंक) में पाया जा सकता है।
ढेर के अलावा, एक बाइनरी सर्च ट्री ऊपर आ सकता है। एक संतुलित बाइनरी सर्च ट्री ओ (लॉग एन) के लिए प्रविष्टि प्रदान कर सकता है, ओ के लिए अधिकतम प्राप्त कर सकता है (लॉग एन), ओ (लॉग एन) के लिए एक तत्व को हटा सकता है। इस संरचना का लाभ यह है कि इसे आरोही क्रम में पुनरावृत्त किया जा सकता है और, इसके अलावा, बीसीएल में लाल-काले रंग के खोज को सॉर्टेडसेट (एक बड़े ढांचे में, अधिकतम .net 3.0 की तुलना में धीमी गति से प्राप्त करना और मेमोरी आवंटित करना) में लागू किया जाता है। GetFiftyMostSimilarGroups लिए GetFiftyMostSimilarGroups का कार्यान्वयन लेख के स्रोत कोड में पाया जा सकता है।
सभी तीन GetFiftyMostSimilarGroups कार्यान्वयन के लिए बेंचमार्क परिणाम:

एक पत्ते के साथ मूल कार्यान्वयन लगभग हर जगह समय में जीतता है, और निश्चित रूप से हर जगह स्मृति में। यह इस तथ्य के कारण होता है कि शीट के साथ एल्गोरिथ्म के लिए, खोज के लिए ओ (लॉग एन) में सम्मिलित किया जाता है, और डालने के लिए लगभग ओ (1), क्योंकि तत्वों की इतनी कम संख्या की नकल करना बहुत जल्दी होता है, ओ (1) के लिए अधिकतम प्राप्त करना, ओ (1) के लिए भी एक तत्व को हटाना, क्योंकि , .net, शीट से अंतिम तत्व को हटाकर अंतिम तत्व को एक खाली मान लिखकर बदल दिया जाता है (इन .net कोर कुछ भी संरचनाओं के लिए नहीं लिखा जाता है) यदि इसे 50 नहीं देने की आवश्यकता होती है, लेकिन चलो 1000 सबसे समान समूहों को कहते हैं, तो सबसे अधिक संभावना है, शीट के साथ एक एल्गोरिथ्म काम नहीं करेगा। वास्तव में, यह सब थोड़ा सट्टा तर्क है, क्योंकि आप अभी भी प्रत्येक एल्गोरिदम को समायोजित कर सकते हैं।

बहु सूत्रण

अब यह GetFiftyMostSimilarGroups में पाश को बेहतर बनाने की कोशिश करने के लिए बनी हुई है। केवल मल्टीथ्रेडिंग दिमाग में आता है। विचार समूहों की पूरी सूची को कई पैकेजों में विभाजित करना है। प्रत्येक पैकेज में, 50 सबसे समान टैग समूह ढूंढें, और फिर उनमें से अंतिम 50 सबसे समान मिलते हैं।
GetFiftyMostSimilarGroups का बहु-संस्करण संस्करण इस तरह दिखता है:

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