بحث القاموس (O (1)) مقابل LINQ حيث

Question

ما هو أسرع وهل يجب أن أضحي بمعايير LINQ لتحقيق السرعة (بافتراض أن البحث القاموس أسرع حقًا)؟ لذلك اسمحوا لي أن أوضح:

لدي ما يلي:

List<Product> products = GetProductList();

أحتاج إلى البحث عن منتج يعتمد على بعض السمات ، على سبيل المثال ، الرقم التسلسلي. يمكنني أولاً إنشاء قاموس ، ثم أملأه على النحو التالي:

Dictionary<string, Product> dict = new Dictionary<string, Product>();
foreach(Product p in products)
{
    dict.Add(p.serial, p);
}

عندما يحين الوقت للعثور على منتج ، استفد من O (1) المقدمة من خلال البحث عن القاموس:

string some_serial = ...;
try { Product p = dict[some_serial]; } catch(KeyNotFoundException) { }

بدلاً من ذلك ، باستخدام LINQ:

Product p = products.Where(p => p.serial.Equals(some_serial)).FirstOrDefault();

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

في الختام ، أود أن أؤكد ما إذا كان تعقيد نهج LINQ أعلاه هو بالفعل o (n) ولا أرى كيف يمكن أن يكون أفضل من ذلك.

Answer 1

على افتراض أنك تبدأ بتعداد الكائنات ولا تفعل ذلك إلا مرة واحدة ...

سيكون أسرع لفعل Where الطريقة بدلاً من إضافة إلى أ Dictionary<TKey,TValue> ثم البحث عنها احتياطيًا. السبب في أن طريقة القاموس هي ليس س (1). في هذا السيناريو ، تقوم بإضافة عناصر إلى القاموس ثم تبحث عنه. الجزء المضيف هو o (n) وهو مكلف مثل Where طريقة مع ذاكرة إضافية.

نقطة بسيطة أخرى يجب أن تكون على دراية بها هي ذلك Dictionary<TKey,TValue> ليس حقا يا (1). بدلاً من ذلك يقترب من O (1) ولكن يمكن أن يتحلل إلى أداء أقل في ظروف معينة (الكثير من مفاتيح الصدام على سبيل المثال).