هاشت مقابل.أداء القائمة

Question

ومن الواضح أن أداء البحث عام HashSet<T> الطبقة أعلى من العامة List<T> فصل.ما عليك سوى مقارنة المفتاح القائم على التجزئة مع النهج الخطي في ملف List<T> فصل.

ومع ذلك، فإن حساب مفتاح التجزئة قد يستغرق في حد ذاته بعض دورات وحدة المعالجة المركزية، لذلك بالنسبة لكمية صغيرة من العناصر، يمكن أن يكون البحث الخطي بديلاً حقيقيًا لـ HashSet<T>.

سؤالي:أين هو التعادل؟

لتبسيط السيناريو (وكي نكون منصفين) لنفترض أن List<T> يستخدم الفصل العنصر Equals() طريقة التعرف على العنصر.

Answer 1

يقول الكثير من الناس أنه بمجرد وصولك إلى الحجم الذي تكون فيه السرعة في الواقع مصدر قلق HashSet<T> سوف يفوز دائما List<T>, ، ولكن هذا يعتمد على ما تفعله.

لنفترض أن لديك List<T> والتي لن تحتوي إلا في المتوسط ​​على 5 عناصر.على مدى عدد كبير من الدورات، إذا تمت إضافة عنصر واحد أو إزالته في كل دورة، فقد يكون من الأفضل استخدام List<T>.

لقد أجريت اختبارًا لهذا على جهازي، حسنًا، يجب أن يكون صغيرًا جدًا للاستفادة منه List<T>.بالنسبة لقائمة السلاسل القصيرة، اختفت الميزة بعد الحجم 5، بالنسبة للكائنات بعد الحجم 20.

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

فيما يلي تلك البيانات المعروضة كرسم بياني:

إليك الكود:

static void Main(string[] args)
{
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}

Answer 2

أنت تنظر إلى هذا بشكل خاطئ.نعم، سيؤدي البحث الخطي للقائمة إلى التغلب على HashSet لعدد صغير من العناصر.لكن فرق الأداء عادة لا يهم بالنسبة للمجموعات الصغيرة.بشكل عام، يجب أن تقلق بشأن المجموعات الكبيرة، وهذا هو المكان الذي يجب عليك فعله فكر فيما يتعلق بـ Big-O.ومع ذلك، إذا قمت بقياس عنق الزجاجة الحقيقي في أداء HashSet، فيمكنك محاولة إنشاء قائمة/HashSet مختلطة، ولكنك ستفعل ذلك عن طريق إجراء الكثير من اختبارات الأداء التجريبية - وليس طرح أسئلة حول SO.

Answer 3

من غير المجدي في الأساس مقارنة بنيتين أداء التي تتصرف بشكل مختلف.استخدم البنية التي تنقل النية.حتى لو قلت الخاص بك List<T> لن تحتوي على نسخ مكررة ولا يهم ترتيب التكرار مما يجعلها قابلة للمقارنة بـ a HashSet<T>, ، لا يزال خيارًا سيئًا للاستخدام List<T> لأنه أقل تحملاً للخطأ نسبيًا.

ومع ذلك، سوف أقوم بالفحص بعض الجوانب الأخرى من الأداء،

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+

* Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it.

** The superior scalability of HashSet<T> has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.

Answer 4

ما إذا كان سيتم استخدام HashSet<> أو List<> يعود إلى كيف تحتاج للوصول إلى مجموعتك.إذا كنت بحاجة إلى ضمان ترتيب العناصر، استخدم القائمة.إذا لم تقم بذلك، استخدم HashSet.دع Microsoft تقلق بشأن تنفيذ خوارزميات التجزئة والكائنات الخاصة بها.

سوف يقوم HashSet بالوصول إلى العناصر دون الحاجة إلى تعداد المجموعة (تعقيد يا(1) أو بالقرب منها)، ولأن القائمة تضمن الترتيب، على عكس HashSet، يجب تعداد بعض العناصر (تعقيد O(n)).

Answer 5

اعتقدت أنني سأتوافق مع بعض المعايير لسيناريوهات مختلفة لتوضيح الإجابات السابقة:

1. عدد قليل (12 - 20) سلسلة صغيرة (يتراوح طولها بين 5 و10 أحرف)
2. العديد من السلاسل الصغيرة (~10K).
3. بضعة سلاسل طويلة (يتراوح طولها بين 200 و1000 حرف)
4. العديد من السلاسل الطويلة (~5K).
5. عدد قليل من الأعداد الصحيحة
6. العديد من الأعداد الصحيحة (~10K).

ولكل سيناريو، البحث عن القيم التي تظهر:

1. في بداية القائمة ("ابدأ"، الفهرس 0)
2. بالقرب من بداية القائمة ("مبكرًا"، الفهرس 1)
3. في منتصف القائمة ("الوسط"، عدد الفهرس/2)
4. بالقرب من نهاية القائمة ("متأخر"، عدد الفهرس -2)
5. في نهاية القائمة ("النهاية"، عدد الفهرس -1)

قبل كل سيناريو، قمت بإنشاء قوائم ذات حجم عشوائي من سلاسل عشوائية، ثم قمت بتغذية كل قائمة بمجموعة هاشتاج.تم تشغيل كل سيناريو 10000 مرة، بشكل أساسي:

(اختبار الكود الزائف)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

إخراج العينة

تم اختباره على نظام التشغيل Windows 7، وذاكرة الوصول العشوائي (RAM) سعة 12 جيجابايت، وإصدار 64 بت، ومعالج Xeon بسرعة 2.8 جيجا هرتز

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]

Answer 6

سيعتمد التعادل على تكلفة حساب التجزئة.يمكن أن تكون حسابات التجزئة تافهة، أو لا...:-) هناك دائمًا فئة System.Collections.Specialized.HybridDictionary لمساعدتك على عدم القلق بشأن نقطة التعادل.

Answer 7

الجواب كما هو الحال دائما هو "هذا يعتمد".أفترض من العلامات أنك تتحدث عن C#.

أفضل رهان لك هو تحديد

1. مجموعة من البيانات
2. متطلبات الاستخدام

وكتابة بعض حالات الاختبار.

يعتمد ذلك أيضًا على كيفية فرز القائمة (إذا تم فرزها على الإطلاق)، ونوع المقارنات التي يجب إجراؤها، والمدة التي تستغرقها عملية "المقارنة" لكائن معين في القائمة، أو حتى كيف تنوي استخدام القائمة. مجموعة.

بشكل عام، لا يعتمد الخيار الأفضل للاختيار على حجم البيانات التي تعمل معها، بل على الطريقة التي تنوي الوصول إليها.هل لديك كل قطعة من البيانات مرتبطة بسلسلة معينة أو بيانات أخرى؟من المحتمل أن تكون المجموعة القائمة على التجزئة هي الأفضل.هل ترتيب البيانات التي تخزنها مهم أم أنك ستحتاج إلى الوصول إلى جميع البيانات في نفس الوقت؟القائمة العادية قد تكون أفضل بعد ذلك.

إضافي:

بالطبع، تفترض تعليقاتي أعلاه أن "الأداء" يعني الوصول إلى البيانات.شيء آخر يجب مراعاته:ما الذي تبحث عنه عندما تقول "الأداء"؟هل يتم البحث عن القيمة الفردية للأداء؟هل هي إدارة مجموعات قيمة كبيرة (10000 أو 100000 أو أكثر)؟هل هو أداء ملء بنية البيانات بالبيانات؟هل تريد إزالة البيانات؟الوصول إلى البتات الفردية من البيانات؟استبدال القيم؟التكرار على القيم؟استخدام الذاكرة؟سرعة نسخ البيانات؟على سبيل المثال، إذا قمت بالوصول إلى البيانات من خلال قيمة سلسلة، ولكن متطلبات الأداء الرئيسية لديك هي الحد الأدنى من استخدام الذاكرة، فقد تواجه مشكلات متعارضة في التصميم.

Answer 8

يمكنك استخدام HybridDictionary الذي يكتشف نقطة التوقف تلقائيًا، ويقبل القيم الخالية، مما يجعله أساسيًا مثل HashSet.

Answer 9

هذا يعتمد.إذا كانت الإجابة الدقيقة مهمة حقًا، فقم ببعض التوصيف واكتشف ذلك.إذا كنت متأكدًا من أنك لن يكون لديك أبدًا أكثر من عدد معين من العناصر في المجموعة، فاستخدم القائمة.إذا كان الرقم غير محدود، استخدم HashSet.

Answer 10

يعتمد على ما تقوم بتجزئته.إذا كانت مفاتيحك عبارة عن أعداد صحيحة، فربما لا تحتاج إلى عدد كبير جدًا من العناصر قبل أن يصبح HashSet أسرع.إذا كنت تقوم بالضغط على سلسلة، فسيكون الأمر أبطأ، ويعتمد على سلسلة الإدخال.

بالتأكيد يمكنك رفع المعيار بسهولة تامة؟

Answer 11

أحد العوامل التي لا تأخذها في الاعتبار هو قوة وظيفة GetHashcode().مع وظيفة التجزئة المثالية، من الواضح أن HashSet سيكون لها أداء بحث أفضل.ولكن مع تضاؤل ​​​​وظيفة التجزئة، سيتضاءل أيضًا وقت البحث في HashSet.

Answer 12

يعتمد على الكثير من العوامل...تنفيذ القائمة، بنية وحدة المعالجة المركزية، JVM، دلالات الحلقة، تعقيد طريقة التساوي، إلخ...وبحلول الوقت الذي تصبح فيه القائمة كبيرة بما يكفي لتقييم (أكثر من 1000 عنصر) بشكل فعال، تتفوق عمليات البحث الثنائية القائمة على التجزئة على عمليات البحث الخطية بشكل مباشر، ولا يرتفع الفرق إلا من هناك.

أتمنى أن يساعدك هذا!