أداء Hashset ADD VS يحتوي على العناصر الموجودة
-
06-07-2019 - |
سؤال
لسبب ما ، يبدو Add
العملية على HashSet
أبطأ من Contains
العملية عندما يكون العنصر موجود بالفعل في HashSet
.
هنا دليل:
Stopwatch watch = new Stopwatch();
int size = 10000;
int iterations = 10000;
var s = new HashSet<int>();
for (int i = 0; i < size; i++) {
s.Add(i);
}
Console.WriteLine(watch.Time(() =>
{
for (int i = 0; i < size; i++) {
s.Add(i);
}
}, iterations));
s = new HashSet<int>();
for (int i = 0; i < size; i++) {
s.Add(i);
}
// outputs: 47,074,764
Console.WriteLine(watch.Time(() =>
{
for (int i = 0; i < size; i++) {
if (!s.Contains(i))
s.Add(i);
}
}, iterations));
// outputs: 41,125,219
لماذا Contains
اسرع من Add
للعناصر الموجودة بالفعل؟
ملاحظة: أنا أستخدم هذا Stopwatch
تمديد من سؤال آخر.
public static long Time(this Stopwatch sw, Action action, int iterations) {
sw.Reset();
sw.Start();
for (int i = 0; i < iterations; i++) {
action();
}
sw.Stop();
return sw.ElapsedTicks;
}
تحديث: كشف الاختبار الداخلي أن فرق الأداء الكبير يحدث فقط في إصدار X64 من إطار .NET. مع وجود إصدار 32 بت من الإطار يحتوي على سرعة متطابقة لإضافة (في الواقع يبدو أن الإصدار الذي يحتوي على يحتوي على مئوية أبطأ في بعض عمليات الاختبار) على إصدارات X64 من الإطار ، يبدو أن الإصدار مع يحتوي على أنه يحتوي تشغيل حوالي 15 ٪ أسرع.
المحلول
يقوم Addifnotpresent بعمل فجوة إضافية لا تحتوي على. ألقِ نظرة على IL لـ:
IL_000a: call instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
IL_000f: stloc.0
IL_0010: ldarg.0
IL_0011: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_0016: ldloc.0
IL_0017: ldarg.0
IL_0018: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_001d: ldlen
IL_001e: conv.i4
IL_001f: rem
IL_0020: ldelem.i4
IL_0021: ldc.i4.1
IL_0022: sub
IL_0023: stloc.1
هذا هو حساب موقع الجرافة لرمز التجزئة. يتم حفظ النتيجة في موقع الذاكرة المحلية 1.
يقوم AddIfNotPresent بشيء مشابه ، لكنه يوفر أيضًا القيمة المحسوبة في الموقع 2 ، بحيث يمكنه إدراج العنصر في جدول التجزئة في هذا الموضع إذا لم يكن العنصر موجودًا. يقوم بذلك لأن أحد المواقع يتم تعديله لاحقًا في الحلقة التي تبحث عن العنصر. على أي حال ، إليك الكود ذي الصلة لـ Addifnotpresent:
IL_0011: call instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
IL_0016: stloc.0
IL_0017: ldloc.0
IL_0018: ldarg.0
IL_0019: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_001e: ldlen
IL_001f: conv.i4
IL_0020: rem
IL_0021: stloc.1
IL_0022: ldarg.0
IL_0023: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_0028: ldloc.0
IL_0029: ldarg.0
IL_002a: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_002f: ldlen
IL_0030: conv.i4
IL_0031: rem
IL_0032: ldelem.i4
IL_0033: ldc.i4.1
IL_0034: sub
IL_0035: stloc.2
على أي حال ، أعتقد أن الفجوة الإضافية هي سبب الإضافة إلى وقت أطول أكثر مما يحتوي. للوهلة الأولى ، يبدو أن هذا الفجوة الإضافية يمكن أن يتم أخذها في الاعتبار ، لكن لا يمكنني القول بالتأكيد دون أن أقضي وقتًا أطول قليلاً في فك رموز IL.
نصائح أخرى
مثيرة للاهتمام ، على الجهاز الخاص بي (Dell Latitude D630 ، Dual-Core 2.2 GHz) أحصل على نتائج متطابقة تقريبًا لكلا الاختبارين ما لم أدير ساعة توقيت مقابل أ null
العمل قبل الاختبارات. فمثلا:
أقوم بتشغيل الاختبارات باستخدام الكود الدقيق الذي قدمته في السؤال:
Without Contains(): 8205794
With Contains(): 8207596
إذا قمت بتعديل الكود بهذه الطريقة:
بعد، بعدما:
Stopwatch watch = new Stopwatch();
int size = 10000;
int iterations = 10000;
يضيف:
watch.Time(null, 0);
أصبحت نتائجي:
Without Contains(): 8019129
With Contains(): 8275771
يبدو لي أن شيئًا غريبًا يجري داخل Stopwatch
وهذا يسبب هذه التقلبات.
أظن أنك أجريت اختبارك من Visual Studio الذي تسبب في تحديث AddIfNotPresent
داخل Add
لكي يتم قمعها ، لذلك ترى نتيجة لمستوى إضافي من عدم التوجيه في مكالمات الطريقة.
إذا قمت بتجميع وركضت من سطر الأوامر لإزالة أي خداع مقابل ...
> csc /o+ /t:exe Program.cs
> Program.exe
... ثم لا يوجد فرق في الأداء.
مخرجات عينة (ممثل عدد أكبر من الاختبارات):
35036174
35153818
35225763
34862330
35047377
35033323