وهو أسرع ، تجزئة بحث أو الثنائية البحث ؟

Question

عندما تعطى مجموعة ثابتة من الكائنات (ثابت بمعنى أنه بمجرد تحميله نادرا ما التغييرات) التي تتكرر المتزامنة عمليات البحث اللازمة مع الأداء الأمثل ، الذي هو أفضل ، HashMap أو صفيف ثنائي البحث باستخدام بعض مخصص للمقارنة?

هو الجواب وظيفة من كائن أو البنية النوع ؟ تجزئة و/أو المساواة في وظيفة الأداء ؟ تجزئة تفرد ؟ قائمة الحجم ؟ Hashset حجم/تعيين الحجم ؟

حجم المجموعة التي أنا أنظر يمكن أن يكون في أي مكان من 500 ألف إلى 10m - أكان ذلك من المعلومات المفيدة.

بينما أنا أبحث عن C# الجواب أعتقد صحيح الرياضية الجواب لا يكمن في اللغة ، لذلك أنا لا بما في ذلك الوسم.ومع ذلك ، إذا كان هناك C# محددة الأشياء أن تكون على علم من أن المعلومات المطلوبة.

Answer 1

حسنا سأحاول أن تكون قصيرة.

C# إجابة قصيرة:

اختبار نهجين مختلفين.

.صافي يعطيك أدوات تغيير النهج الخاص بك مع سطر من التعليمات البرمجية.وإلا استخدام النظام.مجموعات.Generic.قاموس تأكد من تهيئة مع عدد كبير الأولي قدرة أو عليك تمرير بقية حياتك إدراج البنود بسبب العمل GC وقد فعله جمع دلو المصفوفات.

أطول الجواب:

وهو hashtable تقريبا ثابتة البحث مرات والحصول على بند في جدول تجزئة في العالم الحقيقي لا تتطلب فقط لحساب التجزئة.

للوصول إلى البند الخاص بك hashtable سوف تفعل شيئا مثل هذا:

• الحصول على التجزئة الرئيسية
• الحصول على دلو عدد تجزئة (عادة وظيفة الخريطة يبدو مثل هذا دلو = hash % bucketsCount)
• اجتياز البنود سلسلة (أساسا انها قائمة من العناصر التي تشترك في نفس دلو معظم hashtables استخدام هذا الأسلوب من التعامل مع دلو/تجزئة التصادم) أن يبدأ في ذلك دلو ومقارنة كل مفتاح مع واحد البند كنت تحاول إضافة/حذف/تحديث/التحقق من إذا الوارد.

البحث الأوقات تعتمد على كيفية "جيد" (كيف متفرق هو الإخراج) و سريعة هي وظيفة تجزئة عدد من الدلاء كنت تستخدم و كيف سريع هو مفاتيح comparer, أنها ليست دائما أفضل حل.

أفضل و أعمق التفسير: http://en.wikipedia.org/wiki/Hash_table

Answer 2

على مجموعات صغيرة جدا الفرق ستكون ضئيلة.في الطرف الأدنى من النطاق الخاص بك (500k البنود) سوف تبدأ في رؤية الفرق إذا كنت تفعل الكثير من البحث.البحث الثنائي ستكون O(log n) ، في حين تجزئة البحث سيتم O(1) ، المطفأة.هذا ليس نفس حقا ثابتا ، ولكن كنت لا تزال لديها رهيب جدا تجزئة الوظيفة للحصول على أداء أسوء من البحث الثنائية.

(عندما أقول "الرهيب تجزئة" ، أعني شيئا مثل:

hashCode()
{
    return 0;
}

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

ialiashkevich كتب بعض التعليمات البرمجية C# باستخدام مجموعة وقاموس مقارنة طريقتين لكنها كانت طويلة قيم مفاتيح.أردت أن أختبر شيئا في الواقع تنفذ وظيفة تجزئة أثناء البحث ، لذا تعديل هذا القانون.لقد غيرت لاستخدام سلسلة القيم ، وأنا ريفاكتوريد تعبئة و بحث أقسام إلى أساليب خاصة بهم لذلك فإنه من السهل أن نرى في منشئ ملفات التعريف.أنا أيضا تركت في التعليمات البرمجية التي تستخدم طويلة القيم فقط وعلى سبيل المقارنة.وأخيرا تخلصت من العرف وظيفة البحث الثنائية المستخدمة في Array فئة.

هذا الكود:

class Program
{
    private const long capacity = 10_000_000;

    private static void Main(string[] args)
    {
        testLongValues();
        Console.WriteLine();
        testStringValues();

        Console.ReadLine();
    }

    private static void testStringValues()
    {
        Dictionary<String, String> dict = new Dictionary<String, String>();
        String[] arr = new String[capacity];
        Stopwatch stopwatch = new Stopwatch();

        Console.WriteLine("" + capacity + " String values...");

        stopwatch.Start();

        populateStringArray(arr);

        stopwatch.Stop();
        Console.WriteLine("Populate String Array:      " + stopwatch.ElapsedMilliseconds);

        stopwatch.Reset();
        stopwatch.Start();

        populateStringDictionary(dict, arr);

        stopwatch.Stop();
        Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds);

        stopwatch.Reset();
        stopwatch.Start();

        Array.Sort(arr);

        stopwatch.Stop();
        Console.WriteLine("Sort String Array:          " + stopwatch.ElapsedMilliseconds);

        stopwatch.Reset();
        stopwatch.Start();

        searchStringDictionary(dict, arr);

        stopwatch.Stop();
        Console.WriteLine("Search String Dictionary:   " + stopwatch.ElapsedMilliseconds);

        stopwatch.Reset();
        stopwatch.Start();

        searchStringArray(arr);

        stopwatch.Stop();
        Console.WriteLine("Search String Array:        " + stopwatch.ElapsedMilliseconds);

    }

    /* Populate an array with random values. */
    private static void populateStringArray(String[] arr)
    {
        for (long i = 0; i < capacity; i++)
        {
            arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness
        }
    }

    /* Populate a dictionary with values from an array. */
    private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr)
    {
        for (long i = 0; i < capacity; i++)
        {
            dict.Add(arr[i], arr[i]);
        }
    }

    /* Search a Dictionary for each value in an array. */
    private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr)
    {
        for (long i = 0; i < capacity; i++)
        {
            String value = dict[arr[i]];
        }
    }

    /* Do a binary search for each value in an array. */
    private static void searchStringArray(String[] arr)
    {
        for (long i = 0; i < capacity; i++)
        {
            int index = Array.BinarySearch(arr, arr[i]);
        }
    }

    private static void testLongValues()
    {
        Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue);
        long[] arr = new long[capacity];
        Stopwatch stopwatch = new Stopwatch();

        Console.WriteLine("" + capacity + " Long values...");

        stopwatch.Start();

        populateLongDictionary(dict);

        stopwatch.Stop();
        Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds);

        stopwatch.Reset();
        stopwatch.Start();

        populateLongArray(arr);

        stopwatch.Stop();
        Console.WriteLine("Populate Long Array:      " + stopwatch.ElapsedMilliseconds);

        stopwatch.Reset();
        stopwatch.Start();

        searchLongDictionary(dict);

        stopwatch.Stop();
        Console.WriteLine("Search Long Dictionary:   " + stopwatch.ElapsedMilliseconds);

        stopwatch.Reset();
        stopwatch.Start();

        searchLongArray(arr);

        stopwatch.Stop();
        Console.WriteLine("Search Long Array:        " + stopwatch.ElapsedMilliseconds);
    }

    /* Populate an array with long values. */
    private static void populateLongArray(long[] arr)
    {
        for (long i = 0; i < capacity; i++)
        {
            arr[i] = i;
        }
    }

    /* Populate a dictionary with long key/value pairs. */
    private static void populateLongDictionary(Dictionary<long, long> dict)
    {
        for (long i = 0; i < capacity; i++)
        {
            dict.Add(i, i);
        }
    }

    /* Search a Dictionary for each value in a range. */
    private static void searchLongDictionary(Dictionary<long, long> dict)
    {
        for (long i = 0; i < capacity; i++)
        {
            long value = dict[i];
        }
    }

    /* Do a binary search for each value in an array. */
    private static void searchLongArray(long[] arr)
    {
        for (long i = 0; i < capacity; i++)
        {
            int index = Array.BinarySearch(arr, arr[i]);
        }
    }

    /**
     * Generate a random string of a given length.
     * Implementation from https://stackoverflow.com/a/1344258/1288
     */
    private static String generateRandomString(int length)
    {
        var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        var stringChars = new char[length];
        var random = new Random();

        for (int i = 0; i < stringChars.Length; i++)
        {
            stringChars[i] = chars[random.Next(chars.Length)];
        }

        return new String(stringChars);
    }
}

وهنا النتائج مع العديد من أحجام مختلفة من المجموعات.(مرات في ميلي ثانية.)

500000 طويلة القيم...
ملء طويلة القاموس:26
تعبئة مجموعة طويلة:2
البحث طويلة القاموس:9
البحث مجموعة طويلة:80

500000 سلسلة القيم...
تعبئة صفيف سلسلة:1237
تعبئة سلسلة القاموس:46
نوع صفيف سلسلة:1755
سلسلة البحث في القاموس:27
البحث صفيف سلسلة:1569

1000000 طويلة القيم...
ملء طويلة القاموس:58
تعبئة مجموعة طويلة:5
البحث طويلة القاموس:23
البحث مجموعة طويلة:136

1000000 سلسلة القيم...
تعبئة صفيف سلسلة:2070
تعبئة سلسلة القاموس:121
نوع صفيف سلسلة:3579
سلسلة البحث في القاموس:58
البحث صفيف سلسلة:3267

3000000 طويلة القيم...
ملء طويلة القاموس:207
تعبئة مجموعة طويلة:14
البحث طويلة القاموس:75
البحث مجموعة طويلة:435

3000000 سلسلة القيم...
تعبئة صفيف سلسلة:5553
تعبئة سلسلة القاموس:449
نوع صفيف سلسلة:11695
سلسلة البحث في القاموس:194
البحث صفيف سلسلة:10594

10000000 طويلة القيم...
ملء طويلة القاموس:521
تعبئة مجموعة طويلة:47
البحث طويلة القاموس:202
البحث مجموعة طويلة:1181

10000000 سلسلة القيم...
تعبئة صفيف سلسلة:18119
تعبئة سلسلة القاموس:1088
نوع صفيف سلسلة:28174
سلسلة البحث في القاموس:747
البحث صفيف سلسلة:26503

و المقارنة هنا التعريف إخراج آخر تشغيل للبرنامج (10 مليون سجل عمليات البحث).سلطت الضوء على المهام ذات الصلة.أنها جميلة عن كثب أتفق مع ساعة توقيت توقيت المقاييس المذكورة أعلاه.

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

Answer 3

والأجوبة من قبل بوبي، بيل وكوربن خاطئة. O (1) ليست أبطأ من O (سجل ن) ل/ ن يحدها الثابتة:

وسجل (ن) هو ثابت، لذلك يعتمد على وقت ثابت.

وعن وظيفة تجزئة بطيئة، سمعت من MD5؟

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

وأنت قد تكون قادرة على (جزئيا) استخدام الجذر. إذا كان يمكنك تقسيم في 256 كتل بنفس الحجم تقريبا، وكنت أبحث في 2K إلى 40K البحث الثنائي. من المرجح أن تقدم أداء أفضل من ذلك بكثير.

[عدل] الكثير من الناس التصويت ما أسفل أنهم لا يفهمون.

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

Answer 4

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

1. كتبت "خوارزميات التجزئة هي O(1) حين البحث الثنائية O(log n)."- كما لوحظ في التعليقات يا كبير التدوين تقديرات التعقيد ، وليس السرعة.هذا صحيح تماما.ومن الجدير بالذكر أن نستخدمها عادة التعقيد للحصول على شعور من خوارزمية وقت متطلبات المساحة.لذلك ، في حين أنه من الحماقة أن نفترض التعقيد بدقة نفس السرعة تقدير تعقيد دون وقت أو مساحة في الجزء الخلفي من عقلك غير عادية.توصيتي:تجنب يا كبير التدوين.
2. كتبت "وذلك ن النهج اللانهاية"هذا هو أغبى شيء قد شملت في الجواب.اللانهاية لا علاقة له مع المشكلة الخاصة بك.كنت أذكر الحد الأعلى من 10 مليون دولار.تجاهل ما لا نهاية.كما المعلقين يشيرون إلى أعداد كبيرة جدا من شأنها خلق كل أنواع المشاكل مع تجزئة.(أعداد كبيرة جدا لا تجعل البحث الثنائية المشي في الحديقة أيضا.) توصيتي:لا أذكر اللانهاية إلا إذا كنت تعني ما لا نهاية.
3. أيضا من تعليقات:حذار الافتراضي سلسلة التجزئة (أنت تجزئة السلاسل ؟ لا تذكر.), فهارس قاعدة البيانات غالبا ب-الأشجار (الفكر).توصيتي:النظر في جميع الخيارات الخاصة بك.في هياكل البيانات النهج...مثل الطراز القديم trie (لتخزين واسترجاع السلاسل) أو R-شجرة (للبيانات المكانية) أو MA-الجيش السوري الحر (الحد الأدنى احلقي الدولة المحدودة إنسان - تخزين صغيرة البصمة).

نظرا التعليقات ، قد تفترض أن الناس الذين يستخدمون الجداول التجزئة هي مختل.هي الجداول التجزئة متهورة وخطيرة ؟ هؤلاء الناس مجانين ؟

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

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

الجواب الأصلية:

---

خوارزميات التجزئة هي O(1) حين البحث الثنائية O(log n).حتى ن نهج اللانهاية ، تجزئة يحسن الأداء النسبي ثنائي البحث.الأميال الخاص بك سوف تختلف اعتمادا على n, التجزئة الخاصة بك تنفيذ و البحث الثنائية التنفيذ.

مناقشة مثيرة للاهتمام على س(1).اقتبس:

س(1) لا يعني لحظية.فهذا يعني أن الأداء لا تغيير حجم n ينمو.يمكنك تصميم خوارزمية التجزئة هذا هو بطيء جدا لا أحد من أي وقت مضى استخدام ذلك فإنه لا يزال O(1).أنا واثق إلى حد ما .NET/C# لا تعاني من التكلفة الباهظة تجزئة ، ومع ذلك ;)

Answer 5

إذا لديك مجموعة من الأشياء هو ثابت حقا وثابتة، يمكنك استخدام الكمال التجزئة ل الحصول O (1) أداء مضمون. رأيت gperf المذكورة عدة مرات، على الرغم من أنني لم أصب المناسبة لاستخدامه نفسي.

Answer 6

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

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

Answer 7

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

وأعتقد أن استخدام بعض نسخة من هذا في جهاز التوجيه على عمليات البحث الملكية الفكرية.

نص الارتباط

Answer 8

القاموس/Hashtable هو استخدام المزيد من الذاكرة و يأخذ المزيد من الوقت لملء مقارنة مع مجموعة.ولكن يتم البحث بشكل أسرع عن طريق قاموس بدلا من البحث الثنائية ضمن مجموعة.

وهنا هي الأرقام 10 مليون Int64 البنود البحث و تعبئة.بالإضافة إلى نموذج التعليمات البرمجية يمكنك تشغيل من قبل نفسك.

قاموس الذاكرة: 462,836

مجموعة الذاكرة: 88,376

نشر القاموس: 402

تعبئة مجموعة: 23

البحث القاموس: 176

البحث مجموعة: 680

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace BinaryVsDictionary
{
    internal class Program
    {
        private const long Capacity = 10000000;

        private static readonly Dictionary<long, long> Dict = new Dictionary<long, long>(Int16.MaxValue);
        private static readonly long[] Arr = new long[Capacity];

        private static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();

            stopwatch.Start();

            for (long i = 0; i < Capacity; i++)
            {
                Dict.Add(i, i);
            }

            stopwatch.Stop();

            Console.WriteLine("Populate Dictionary: " + stopwatch.ElapsedMilliseconds);

            stopwatch.Reset();

            stopwatch.Start();

            for (long i = 0; i < Capacity; i++)
            {
                Arr[i] = i;
            }

            stopwatch.Stop();

            Console.WriteLine("Populate Array:      " + stopwatch.ElapsedMilliseconds);

            stopwatch.Reset();

            stopwatch.Start();

            for (long i = 0; i < Capacity; i++)
            {
                long value = Dict[i];
//                Console.WriteLine(value + " : " + RandomNumbers[i]);
            }

            stopwatch.Stop();

            Console.WriteLine("Search Dictionary:   " + stopwatch.ElapsedMilliseconds);

            stopwatch.Reset();

            stopwatch.Start();

            for (long i = 0; i < Capacity; i++)
            {
                long value = BinarySearch(Arr, 0, Capacity, i);
//                Console.WriteLine(value + " : " + RandomNumbers[i]);
            }

            stopwatch.Stop();

            Console.WriteLine("Search Array:        " + stopwatch.ElapsedMilliseconds);

            Console.ReadLine();
        }

        private static long BinarySearch(long[] arr, long low, long hi, long value)
        {
            while (low <= hi)
            {
                long median = low + ((hi - low) >> 1);

                if (arr[median] == value)
                {
                    return median;
                }

                if (arr[median] < value)
                {
                    low = median + 1;
                }
                else
                {
                    hi = median - 1;
                }
            }

            return ~low;
        }
    }
}

Answer 9

وأشك بقوة أن في مشكلة مجموعة من حجم ~ 1M، تجزئة سيكون أسرع.

وفقط لأرقام:

وبحث ثنائي يتطلب ~ 20 يقارن (2 ^ 20 == 1M)

وعلى بحث تجزئة سيتطلب 1 حساب تجزئة على مفتاح البحث، وربما عدد قليل من يقارن بعد ذلك لحل الاصطدامات المحتملة

وتحرير: الأرقام:

    for (int i = 0; i < 1000 * 1000; i++) {
        c.GetHashCode();
    }
    for (int i = 0; i < 1000 * 1000; i++) {
        for (int j = 0; j < 20; j++)
            c.CompareTo(d);
    }

ومرات: ج = "ABCDE"، د = "rwerij" شفرة التجزئة: 0.0012 ثانية. قارن: 2.4 ثواني.

تنويه: القياس الواقع على بحث التجزئة مقابل بحث ثنائي قد يكون أفضل من هذا الاختبار لا-تماما-ذات الصلة. أنا لست متأكدا حتى إذا كان يحصل على memoized GetHashCode تحت غطاء محرك السيارة

Answer 10

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

ولكن في معظم الحالات يجب أن تكون الخريطة التجزئة بشكل أسرع.

Answer 11

وأتساءل لماذا لم يذكر أحد الكمال التجزئة .

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

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

Answer 12

وذلك يعتمد على كيفية التعامل مع مكررة للجداول التجزئة (على كل حال). إذا كنت لا تريد أن تسمح مكررة مفتاح الشباك (أي وظيفة التجزئة على ما يرام)، ويبقى O (1) للبحث المفتاح الأساسي ولكن البحث وراء لقيمة "الحق" قد يكون مكلفا. الجواب هو بعد ذلك، theorically أكثر من مرة، تجزئات أسرع. YMMV اعتمادا على البيانات التي وضعت هناك ...

Answer 13

هنا انها وصفت كيف يتم بناؤها التجزئة ولأن الكون من مفاتيح كبيرة معقولة ومبنية ظائف التجزئة أن يكون "injective جدا" بحيث اصطدام نادرا ما يحدث وقت الوصول للجدول تجزئة ليس O (1) فعلا ... انها شيء استنادا إلى بعض الاحتمالات. ولكن، فمن المعقول أن نقول أن وقت وصول من تجزئة هو دائما تقريبا أقل من O الوقت (log_2 (ن))

Answer 14

وبطبيعة الحال، التجزئة هي الأسرع لمثل مجموعة بيانات كبيرة.

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

Answer 15

الجواب يعتمد.يتيح أعتقد أن عدد من عناصر 'n' هو كبير جدا.إذا كنت جيدة في كتابة أفضل دالة البعثرة التي أقل التصادم ، ثم تجزئة هو أفضل.علما بأن وظيفة تجزئة يتم تنفيذها مرة واحدة فقط في البحث وأنه توجه إلى المقابلة دلو.لذلك ليس كبيرا النفقات العامة إذا كان n عالية.
المشكلة في Hashtable: ولكن المشكلة في تجزئة الجداول إذا كانت وظيفة تجزئة ليست جيدة (أكثر التصادم يحدث) ، ثم البحث ليس O(1).فإنه يميل إلى O(n) لأن البحث في دلو هي خطي البحث.يمكن أن يكون أسوأ من شجرة ثنائية. مشكلة في شجرة ثنائية: في شجرة ثنائية ، إذا كانت الشجرة ليست متوازنة ، كما أنه يميل إلى O(n).على سبيل المثال إذا قمت بإدراج 1,2,3,4,5 إلى شجرة ثنائية من شأنها أن تكون أكثر عرضة قائمة. لذلك ، إذا كنت يمكن أن نرى جيدا تجزئة منهجية استخدام hashtable إن لم يكن من الأفضل استخدام شجرة ثنائية.

Answer 16

هذا هو أكثر تعليق على مشروع قانون الجواب لأن جوابه يكون الكثير من القطرية على الرغم من الخطأ.لذلك اضطررت إلى ما بعد هذا.

أرى الكثير من النقاش حول ما هو أسوأ الأحوال تعقيد بحث في hashtable ، ما يعتبر المطفأة تحليل / ما هو.يرجى مراجعة الرابط أدناه

جدول تجزئة وقت التعقيد (إدراج البحث وحذف)

أسوأ حالة التعقيد(ن) O لا O(1) خلافا لما يقول بيل.وبالتالي له س(1) التعقيد لا يستهلك منذ هذا التحليل يمكن أن تستخدم فقط في أسوأ الحالات (كما بلده ويكيبيديا الرابط يقول ذلك)

https://en.wikipedia.org/wiki/Hash_table

https://en.wikipedia.org/wiki/Amortized_analysis

Answer 17

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

ولكن عند تمكين الأمثل مترجم، وحاول نفس الاختبار مع عدد أقل من عينات نقول أقل من 10،000، فاق أداء البحث الثنائي وبحث التجزئة من خلال استغلال هياكل البيانات الصديقة للذاكرة التخزين المؤقت.