منذ بعض الوقت ، طلب مني زميلي مساعدته في مشكلة واحدة. لقد قمت بحل المشكلة له ، لكن بالإضافة إلى ذلك ، بدا لي أنه عند حل هذه المشكلة ، يمكن شرح العديد من خوارزميات وتقنيات البرمجة. وتظهر أيضًا تسريع وقت تنفيذ الخوارزمية من 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 بسيط للتحقق من صحة العناصر المقابلة في صفيفات 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 مؤشر أدنى لهؤلاء الذين لديهم فهرس أقل في المجموعة الحالية الأصلية. يمكن العثور على مزيد من التفاصيل ، على سبيل المثال ، هنا: https://ru.wikipedia.org/wiki/Sustainable_Sort .
لحل هذه المشكلة ، قررت SimilarTagsCalculator فئة 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 مجموعة من العلامات ستكون أكثر ملائمة.

فيما يلي النتائج المرجعية لمليون مجموعة:

BenchmarkDotNet = v0.11.5 ، OS = Windows 10.0.17134.765 (1803 / April2018Update / Redstone4)
Intel Core i7-6700 CPU 3.40GHz (Skylake) و 1 CPU و 8 مراكز منطقية و 4 نوى فعلية
التردد = 3328126 هرتز ، القرار = 300.4694 نانوثانية ، الموقت = TSC
.NET Core SDK = 3.0.100-preview5-011568
[المضيف]: .NET Core 3.0.0-preview5-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 - التحقق من تعيين العلامات المقابلة في مجموعتين. دعنا نقدر الحالات التي ستكون فيها الحالة صحيحة ، لذلك سنضع جدولًا لحقيقة الحالة:

يتطابق جدول الحقيقة تمامًا مع المنطق "AND" ، أي تكون النتيجة صحيحة إذا وفقط إذا كانت كلتا العلامتين if (a.InnerTags[i] && b.InnerTags[i]) ، فيمكن تقليل الشرط إلى: if (a.InnerTags[i] && b.InnerTags[i]) . ولكن بهذه الطريقة لا تزال الحالة قائمة. في الخطوة التالية ، سوف نتأكد من أن الإضافة إلى النتيجة يتم تنفيذها دائمًا ، لذلك نعيد كتابة نص الحلقة مثل هذا:

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

ما زلنا لم نتخلص من الحالة وفي الواقع جعلنا الطريقة أبطأ. لكن أصبح من الواضح الآن أنه إذا InnerTags تغيير نوع InnerTags من منطقي إلى بايت (1 صحيح ، و 0 خطأ) ، فيمكنك التخلص من الحالة في عامل التشغيل الثلاثي. ثم TagsGroup الفئة 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. في result يتم تجميع نتيجة العملية "AND" ببساطة. ولكن نفس العملية المنطقية يمكن تطبيقها ليس فقط على أرقام بت واحدة. يتيح لك C # القيام بذلك دون أي مشاكل حتى أرقام 64 بت (يمكنك القيام بالمزيد من خلال BitArray ، لكن هذا ليس هو الحال). إذا قمنا بتمثيل مجموعتين من العلامات كمجموعة من أرقام 64 بت مع مجموعة وحدات البت المقابلة ، فسيكون من الممكن تنفيذ عملية "AND" على كل مجموعة من هذه الأرقام المكونة من 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] في بعض الصفيف ، وفي النتيجة لا تكتب إلا عدد الوحدات في هذه المجموعة. عند إجراء العملية AND على أرقام أكثر من n-bit ، ستكون النتيجة n-bit وستكون كافية فقط لمعرفة عدد البتات الموضوعة بين n. لم يتغير عدد وحدات البت المحددة في الرقم ، مما يعني أنه يمكنك حساب هذه الأرقام. ليس هناك نقطة في العد لمدة 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; } 

الآن يبدو مُنشئ TagsGroup هكذا:

 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 بت ، ونحن نقوم بتوصيل بيانات من 8 بت فيها. للقيام بذلك ، قم بزيادة حجم الحزمة التي يتم فيها تغليف العلامات الأصلية ، قم بزيادة 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 Core 3.0. على الرغم من أن هذا الإصدار لا يزال قيد المعاينة ، إلا أنه منذ البداية هناك تطبيق لبعض العناصر الداخلية. يحتوي دليل Intel Intrinsic على _mm_popcnt_u64 الجوهري. والتي ، كما هو موضح: " حساب عدد البتات المعينة إلى 1 في عدد صحيح 64 بت غير موقّع ، وإرجاع هذا العدد في التوقيت الصيفي. ". هذا هو بالضبط ما نحاول تحقيقه! في .NET Core 3.0 Preview 5 ، يتم تطبيق هذا System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount في System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount (كما هو موضح بشكل صحيح في تعليقات a-tk ، قبل استخدام intrinsics ، يجب عليك التحقق من أن المعالج يدعمها. في هذه الحالة ، تحقق من حالة System.Runtime.Intrinsics.X86.Popcnt.X64.IsSupported ). عند استخدامه ، MeasureSimilarity رمز طريقة MeasureSimilarity على 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 ؛
• إدراج المجموعة الجديدة المعنية في القائمة مع الحفاظ على الفرز ؛
• إذا كان هناك أكثر من خمسين عنصرًا في القائمة ، فقم بحذف المجموعة الأقل تشابهًا (سيكون كائن المعلومات الخاص به هو الأكبر وسيكون في نهاية list ) ؛

أي اتضح أننا بحاجة إلى العثور بسرعة أكبر عنصر في المجموعة ، حتى نتمكن من إدراج وحذف بسرعة. لحل هذه المشاكل ، هناك هياكل البيانات الخاصة. أول ما يتبادر إلى الذهن هو مجموعة . يتم إجراء الإدراج الخاص بها في O (log N) ، والحصول على الحد الأقصى في O (1) ، وإزالة عنصر في O (log N). المشكلة الوحيدة هي أنه لا يمكن تكرار الكومة بواسطة العناصر المتزايدة دون تعديلها. لا يوجد كومة ثنائية في 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 في التعليمات البرمجية المصدر للمادة (الرابط أدناه).
بالإضافة إلى الكومة ، قد تظهر شجرة بحث ثنائية . يمكن أن توفر شجرة البحث الثنائية المتوازنة إدخالًا لـ O (log N) ، والحصول على الحد الأقصى لـ O (log N) ، وإزالة عنصر O (log N). تتمثل ميزة هذا الهيكل في أنه يمكن التكرار بترتيب تصاعدي ، بالإضافة إلى ذلك ، يتم تنفيذ شجرة البحث باللون الأحمر والأسود في BCL داخل SortedSet (في إطار كبير ، يكون الحصول على الحد الأقصى أبطأ بكثير من في .netcore 3.0 ويخصص الذاكرة). يمكن العثور على تطبيق GetFiftyMostSimilarGroups لـ SortedSet في التعليمات البرمجية المصدر لهذه المقالة.
نتائج GetFiftyMostSimilarGroups تطبيقات GetFiftyMostSimilarGroups الثلاثة:

التنفيذ الأصلي مع ورقة يفوز في كل مكان تقريبا في الوقت المناسب ، وبالتأكيد في كل مكان في الذاكرة. يحدث هذا بسبب حقيقة أنه بالنسبة لخوارزمية مع ورقة ، يتم تنفيذ الإدراج في O (log N) للبحث ، وتقريبا O (1) للإدراج ، بسبب يحدث نسخ هذا العدد الصغير من العناصر بسرعة كبيرة ، حيث تحصل على الحد الأقصى لـ O (1) ، وحذف عنصرًا أيضًا لـ O (1) ، لأن في .net ، يتم استبدال حذف العنصر الأخير من الورقة بكتابة قيمة فارغة للعنصر الأخير (في .net لا تتم كتابة أي شيء على الهياكل). إذا كان مطلوبًا عدم إعطاء 50 ، ولكن دعنا نقول 1000 من أكثر المجموعات المماثلة ، على الأرجح ، لن تعمل خوارزمية مع ورقة. في الواقع ، كل هذا هو التفكير المضاربة قليلا ، لأنه لا يزال بإمكانك ضبط كل من الخوارزميات.

خاصية تعدد

الآن يبقى محاولة تحسين الحلقة نفسها في GetFiftyMostSimilarGroups . multithreading فقط يتبادر إلى الذهن. والفكرة هي تقسيم قائمة المجموعات بأكملها إلى عدة حزم. في كل حزمة ، ابحث عن أكثر من 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. , , .