تحسين عمليات البحث:قاموس مفتاح البحث مقابلمؤشر مجموعة عمليات البحث

Question

أنا أكتب 7 بطاقات البوكر ناحية مقيم باعتبارها واحدة من بلدي الحيوانات الأليفة المشاريع.بينما كان يحاول تحسين سرعته (أنا أحب التحدي) ، لقد صدمت لتجد أن أداء القاموس مفتاح عمليات البحث كانت بطيئة جدا مقارنة مع مؤشر مجموعة عمليات البحث.

على سبيل المثال, ركضت هذا نموذج التعليمات البرمجية التي يعدد على جميع 52 اختيار 7 = 133,784,560 ممكن 7 بطاقة اليدين:

var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
    intDict.Add(i, i);  
    intList.Add(i);
}

int result;

var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);

التي النواتج:

time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms

هذا النوع من السلوك المتوقع (انخفاض أداء بعامل 8)?IIRC, قاموس يحتوي في المتوسط O(1) عمليات البحث ، في حين أن مجموعة لديها أسوأ O(1) عمليات البحث ، لذلك أنا لا أتوقع مجموعة الأبحاث إلى أن يكون أسرع ، ولكن ليس قبل هذا بكثير!

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

Answer 1

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

على التوالي في مؤشر عمليات البحث ، المصفوفات هي في الأساس المثالي - انها مجرد حالة

pointer_into_array = base_pointer + offset * size

(ثم مؤشر إلغاء مرجعية.)

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

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

Answer 2

هل هذا النوع من السلوك المتوقع (انخفاض الأداء بعامل 8)؟

لما لا؟ كل بحث صفيف هو تقريبا / قابل للإهمال، في حين أن البحث في القاموس قد يحتاج إلى مكالمة دون روتين إضافية على الأقل.

إن نقطة كلاهما س (1) تعني أنه حتى لو كان لديك 50 مرة المزيد من العناصر في كل مجموعة، فإن انخفاض الأداء لا يزال فقط عامل كل ما هو عليه (8).

Answer 3

شيء يمكن أن يأخذ الألفية، ولا يزال س (1).

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

Answer 4

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

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

Answer 5

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

Answer 6

مرحبا بكم في تدوين كبير. يجب أن تنظر دائما في أن هناك عامل ثابت.

بطبيعة الحال بقيام عملية البحث عن DICT أكثر تكلفة بكثير من بحث صفيف.

Big-o يخبرك كيف حجم الخوارزميات. مضاعفة مقدار البحث ومعرفة كيفية تغيير الأرقام: يجب أن يستغرق كلاهما حول الوقت مرتين.

Answer 7

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

ستكون القائمة (بصرف النظر عن كونها كلمة القمامة المستخدمة لاستئصال صفيف بدلا من قائمة مرتبطة!) ستكون أسرع لأنها ستعود القيمة عن طريق حساب العنصر الذي تريده مباشرة.