العثور على فهرس إدخال في قائمة مرتبطة في وقت أفضل من O (n)

Question

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

الإدراج سهل ؛ يحتوي الإشعار على فهرس الهدف ومؤشر للعنصر. التحديث سهل ؛ أنا أنقل مؤشر إلى العنصر.

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

يمكنني القيام بذلك ، على سبيل المثال ، خريطة: std::map<item*, int>, ، ولكن عندما أقوم بإزالة عنصر ما ، يجب أن أذهب إلى إعادة عدد كل شيء الماضي ، وهو O (N).

ستكون قوائم العناصر هذه كبيرة لدرجة أن التكرار O (n) غير مقبول. أنا متأكد من أن هذه المشكلة قد تم حلها ، فأنا لا أعرف ما الذي سيطلق عليه الحل. البحث عن أي شيء يتعلق بـ "Linked List" يخلق الكثير من الضوضاء.

أحد الحلول الممكنة هو قائمة تخطي ، حيث تعرف كل عقدة في القواعد الفرعية عدد العقد في القائمة الرئيسية التي تتخطاها ، وبما أن البحث في قائمة تخطي هو o (log n) يمكننا تتبعه أثناء الذهاب والعثور على الفهرس في o (log n) وأيضًا حذف العناصر في O (log n).

ومع ذلك ، يبدو أن تطبيق قائمة التخطي مبالغة هنا ... هل هناك حل أبسط؟

تعديل:

شكرًا على اقتراحاتك ، لكنني أعتقد أنني أقنعت نفسي بأن قائمة التخطي هي الطريقة الصحيحة لحل هذه المشكلة هنا.

Answer 1

Skip List هو الحل الصحيح.

Answer 2

يرى أشجار الإصبع: بنية بيانات بسيطة للأغراض العامة بقلم هينز وباترسون.

انظر أيضًا الرسوم التوضيحية الجميلة في Markcc's منشور المدونة على أشجار الإصبع.

Answer 3

تحرير: كان حلي السابق معيبًا std :: vector :: erase () خطي عند تحريك العناصر. اقتراحي الجديد يمتد تعليقي السابق على سؤالك.

إذا كنت تعمل فقط مع مؤشرات في القائمة ، فيمكنك تعيين المؤشر على 0 بعد الاتصال بحذف المؤشر ، مع الحفاظ على مؤشرات/مفاتيح صالحة. ثم يجب أن تكون قادرًا على استخدام مؤشرات أكبر بشكل متزايد حتى يتجاوز الفهرس التالي std::numeric_limits<int>::max(). ثم ، عندما يحتوي جزء أكبر من قائمتك على عناصر مؤشر غير مستخدمة تم تعيينها على الصفر ، قم بإجراء تنظيف متزامن من الرميات الصفر على جانبي قناة الاتصال ، تليها إعادة حساب للمؤشرات. لا أعرف مجردة جيدة لهذا الكفة ، ولكن يمكنك تتبع عدد المؤشرات الصفر ، ومقارنتها بحجم القائمة العام.

بكلمات أقل ، نظرًا لأن حساب المؤشرات هو o (n) ، تأخيرها حتى تضطر إلى ذلك.

Answer 4

لا يمكنك الاحتفاظ بسجل الحذف وتعويض ذلك عندما تقوم بالبحث في std::map<item*, int>?

ما أعنيه هو أن الفهرس في std::map يمثل الفهرس الأصلي للعنصر ثم لديك خريطة auxillary std::map<int, int> ما هي المتاجر كم مرة تم حذف فهرس معين؟

item* todelete; //from somewhere
std::map<int, int> history; //stored somewhere
std::map<item*, int> itemIndices; //stored somewhere
const int originalIndex = itemIndices[todelete]; //index of item at insert time
int index = originalIndex;
for (std::map<int, int>::const_iterator it = history.begin(); it != history.end() && it->first < originalIndex; ++it) {
    index -= it->second;
}
// index has now been compensated for previous deletes
// ... send the delete request with 'index'
// update the history with this delete request
std::map<int, int>::iterator it = history.find(index);
if (history.end() == it) {
    history[index] = 1;
} else {
    ++it->second;
}

إن سرعة هذا سوف تعتمد بالطبع على حجم التاريخ.

/أب

Answer 5

كم مرة سيحدث الحذف؟ أفكر في الحفاظ على الحل الخاص بك باستخدام std::map<item*, int>, ، ولكن بدلاً من تحديث الخريطة عند الحذف ، استبدال العنصر في القائمة المرتبطة بـ "Null" -item للتأكد من أن المؤشرات في البحث الخاص بك لا تزال صالحة. قد لا يكون هذا حلاً جيدًا إذا كنت سترى عمليات حذف متكررة وهناك فرصة ستنفد الذاكرة. أيضًا ، يمكنك القيام بذلك والحصول على طريقة Reindex ()-تزيل أي عنصر فارغ من القائمة المرتبطة وتعيين مؤشرات جديدة لجميع العناصر.

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

Sidenote 2: فكر في استخدام boost::unordered_map على std::map.