كفاءة اجتياز من changelist

Question

لدي قائمة من التغييرات على قائمة - يضيف و يحذف.القائمة يمكن أن تكون ضخمة - يقول 10'000 البنود.

أريد أن أعرف دولة قائمة بعد تغيير 9'000.

أستطيع المشي قائمة من البداية وصولا إلى تغيير 9'000.يبدو أن قليلا مهزار لي.

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

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

أنا يمكن أن ذاكرة التخزين المؤقت دولة قائمة في كل 100 أو 1000 التغيير...ولكن مرة أخرى يا كبير يقول أن يقسم على عدد من البنود من قبل 'ن' لا تجعل الأمور أكثر كفاءة.

فما هي طريقة فعالة للقيام بذلك ؟ هل هناك طريقة فعالة للقيام بذلك ؟

مزيد من التفاصيل: على وجه التحديد, أنا تتبع عمليات تخصيص الذاكرة / deallocations في العرف allocater.كل تخصيص / deallocation هو الحدث في القائمة.كل تخصيص هوية فريدة من نوعها.أود أن أعرف ما هو المخصصة حاليا بعد (e.ز) 9'000 الأحداث.

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

أنا أحب نقطة أثارها مايك F - المشي من أقرب 100 البند هو وقت ثابت...

Answer 1

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

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

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

Answer 2

أي نوع من هيكل تعمل ؟ ليس هناك طريقة فعالة الأقدام عام بنية البيانات ، ولكن هناك الآلاف من تحسين طرق وأساليب فعالة محددة من الهياكل.

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

Answer 3

'الزمني أو علامة كل الإدراج والحذف ، ثم سيستغرق بسيط اجتياز العثور على التغييرات (O(n)).