* بكل شيء ، أعني التنفيذ السريع نسبيًا للعمليات على عنصر واحد من المصفوفة.اكتمال هياكل البيانات التي تنفذ القائمة. لكل شخص مزاياه وعيوبه. على سبيل المثال ، في عالم Java - اعتمادًا على العمليات الضرورية - يمكنك استخدام:- add (obj)، get (obj)، set (index، obj): مجموعة أساسية من جميع القوائم تقريبًا ، مثل ArrayList.
- add (index، obj): هياكل شبيهة بالأشجار ، مثل TreeList من مجموعات أباتشي الشائعة.
- إزالة (الفهرس): نفس المذكور أعلاه.
- يحتوي على (obj) و indexOf (obj): يمكنك استخدام مجموعة من ArrayList و HashMap.
- إزالة (obj): ... أجد صعوبة في الإجابة. في بعض الحالات ، يمكنك الحصول على LinkedHashSet. يتم حلها بشكل تافه في وجود النقطتين السابقتين ، ولكن أي الهياكل يمكن كلاهما بسرعة؟
عندما كنت بحاجة إلى بنية ذات إضافة سريعة (obj) ، احصل على (index) ، وأزل (index) و indexOf (obj) ، ثم لم تقدم Google إجابة. لم أجد أي أمثلة كود أو أوصاف لهذه الهياكل. ربما لم أكن أنظر هناك ، كان عليّ اختراعه بنفسي. ولكن إذا أسقط شخص ما الرابط في التعليقات ، فسأقدر ذلك كثيرًا.ربما أدرك شخص ما أنه يمكنك أخذ TreeList ، والذي يمكنه إدراج / إزالة العناصر بسرعة في منتصف القائمة وإضافة HashMap من الكائن إلى الفهرس في TreeList من أجل التنفيذ السريع لـ indexOf (obj). وسيكون قرارًا بسيطًا وأنيقًا ولكنه غير صحيح. بعد كل شيء ، عند الإضافة إلى المنتصف أو الإزالة من المنتصف ، سيكون من الضروري إعادة حساب المؤشرات ، في المتوسط ، لنصف العناصر. سيؤدي ذلك إلى انخفاض الأداء إلى O (n).بعد ذلك سأتحدث عن بنية بيانات يمكنها القيام بكل ما سبق. الذي ينفذ أي عملية على عنصر واحد في وقت O (تسجيل (ن)). حسنًا ، تقريبًا - يتم تنفيذ اللوغاريتم في حالة اختلاف جميع الكائنات في القائمة. إذا كانت القائمة تحتوي على نفس الكائنات ، فمن الممكن أن يتدهور الأداء حتى O (تسجيل (n) ^ 2).سأحذرك على الفور أنني لن أرسم الرمز هنا. يمكن أن يكون معقدًا جدًا للمقال. لكنه مكتوب بلغة جافا. استنادًا إلى فئة TreeList من مجموعات أباتشي الشائعة. طلب السحب موجود بالفعل ، ولكن في وقت كتابة هذا التقرير ، لم يتم سكب المقالة بعد.أيضا ، لن أصف الخوارزميات المعروفة. على سبيل المثال ، خوارزميات موازنة الأشجار. بالنسبة للكثيرين ، قد يكون من الكافي أن نعترف بأن الشجرة يمكن أن تبقى متوازنة. هذا لا يؤثر على فهم الفكرة العامة. يمكن لأولئك الذين يريدون معرفة المزيد العثور على المعلومات بسهولة. لكني سأخبرك باختصار شديد عن بعض الأشياء الأساسية ، لأنه بدون معرفة الأساسيات ، لا يمكن فهم العديد من العناصر الرئيسية.ستكون الروابط في النهاية.لماذا هو ضروري
في الواقع ، ليس من السهل ابتكار المواقف التي تتطلب كل شيء مباشرة من القائمة. من غير المحتمل أن يكون هذا نوعًا من البنية الضرورية للغاية ، وإلا فسيعرف الجميع عنه. ومع ذلك ، يمكن إعطاء بعض الأمثلة حيث يمكن أن تكون هذه القائمة مفيدة.أدرك أن العديد من الأمثلة بعيدة المنال. يمكن حل كل أو كل شيء تقريبًا بطريقة أخرى.التخزين المؤقت والضغط
مهمتي الأولية ، التي بدأت من خلالها البحث في هذه المسألة. لعبت مع ضغط بيانات معينة وتحتاج إلى قائمة لذاكرة التخزين المؤقت للكائن.الفكرة هي: عند معالجة كائن آخر ، نبحث عنه في القائمة. إذا لم يتم العثور عليه ، قم بحفظ الكائن وإضافته إلى أعلى القائمة. إذا تم العثور عليها ، فإننا نأخذ فهرسها في القائمة وبدلاً من الكائن نحفظ فهرسها فقط ، وبعد ذلك ننقل الكائن إلى أعلى القائمة. وبالتالي ، ستتلقى الكائنات التي تحدث في كثير من الأحيان فهارس صغيرة ، وستنتقل الكائنات التي تحدث مرة واحدة فقط في نهاية الأمر إلى نهاية القائمة وسيتم حذفها.منعطف أو دور
إذا تم استخدام بنية مماثلة بدلاً من قائمة الانتظار FIFO المعتادة ، فيمكن عندئذٍ تنفيذ العمليات التالية:- أجب عن السؤال: كم عدد المهام الموجودة في قائمة الانتظار قبل هذه المهمة.
- إزالة المهام من قائمة الانتظار.
إنها مثل السوبر ماركت. إذا أتيت للحصول على لوح شوكولاتة ، ولكنك ترى أن الخط يتحرك ببطء ، فربما لا تكون هناك حاجة ماسة إلى شريط الشوكولاتة؟ :)جدول درجات عالية
افترض أننا نريد تخزين الوقت الذي يكمل فيه اللاعبون مستوى في لعبة. هناك العديد من اللاعبين وجميعهم يتنافسون ، محاولين إظهار الحد الأدنى من الوقت. يمكن وضع بيانات اللاعب في مصفوفة وفرزها حسب الوقت. باستخدام هذا الهيكل ، يمكنك:- انقل اللاعبين إلى أعلى القائمة إذا أظهروا نتائج أفضل من ذي قبل.
- قم بإزالة اللاعبين من القائمة ، على سبيل المثال ، في حالة حظر الغش.
- أظهر لكل لاعب مكان وجوده.
- إظهار جدول السجلات صفحة بصفحة.
- إظهار جدول متناثر في الأماكن ، على سبيل المثال ، الوقت 1 ، 2 ، 3 ، 5 ، 10 ، 20 ، 50 ، 100 ، 1000 ، 10000 مكان.
هيكل البيانات
يعتمد الهيكل على شجرة بمفتاح ضمني. على هذا النهج ، على سبيل المثال ، تقوم TreeList في مجموعات أباتشي الشائعة. من أجل المضي قدمًا ، تحتاج إلى فهم كيفية عمل هذا الهيكل.شجرة مفاتيح ضمنية
تتكون الشجرة من العقد (العقد). تحتوي كل عقدة على ارتباط إلى كائن تم تخزينه في العقدة ورابطين إلى عقد أخرى: اليسار واليمين. تسمى العقدة العليا العقدة الجذرية. في أبسط الحالات ، تبدو العقدة شيئًا مثل هذا:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
}
في الشجرة الثنائية الكلاسيكية لكل عقدة في الشجرة الفرعية اليسرى ، تكون جميع الكائنات أصغر من العقدة الحالية ، وفي اليمين - كبير. على سبيل المثال: [ element: 25 ]
/ \
/ \
[ element: 14 ] [ element: 45 ]
/ \ / \
/ \ / \
[ element: 10 ] [ element: 22 ] [ element: 27 ] [ element: 90 ]
/ \ /
/ \ /
[ element: 17 ] [ element: 23 ] [ element: 80 ]
ولكن لغرضنا ، هذه الشجرة ليست مناسبة. لا نحتاج إلى تخزين الكائنات التي تم فرزها ، ولكننا بحاجة إلى الوصول إليها حسب الفهرس ، كما هو الحال في الصفيف.كيف يمكنني وضع مصفوفة في شجرة؟ دعنا نختار عنصرًا بمؤشر i من منتصف المصفوفة. ضع العنصر ith من المصفوفة في العقدة الجذرية. تخرج شجرتان فرعيتان من العقدة الجذرية. في الشجرة الفرعية اليسرى نضع نصف الصفيف مع الفهرس <i ، وفي الشجرة اليمنى مع الفهرس> i. كيف افعلها؟ بنفس الطريقة: نختار عنصرًا من المنتصف في مصفوفة فرعية ونضع هذا العنصر في عقدة ونحصل على مصفحتين فرعيتين أصغر. وهكذا حتى نضع جميع عناصر المصفوفة في عقد الشجرة.على سبيل المثال ، قد يبدو المصفوفة التي تحتوي على العناصر ["q" و "w" و "e" و "r" و "t" و "y" و "u"] كما يلي: [el: r, size: 7]
/ : \
/ : \
[el: w, size: 3] : [el: y, size: 3]
/ : \ : / : \
/ : \ : / : \
[el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
العنصر الأوسط في الصفيف "r" ، نضعه في العقدة الجذرية. يتم وضع مصفوفتين فرعيتين ["q" و "w" و "e"] و ["t" و "y" و "u"] في المقاطع الفرعية اليسرى واليمنى. لهذا ، يتم اختيار العناصر المركزية من المصفوفات الفرعية ، في حالتنا هذه هي "w" و "y" ، وتقع في عقد المستوى التالي. وما إلى ذلك.في حالتنا ، الشجرة متوازنة ، وعمق كل الشجرة الفرعية هو نفسه. ولكن هذا لا يجب أن يكون كذلك.في الصورة أعلاه ، تحتوي كل عقدة ، بالإضافة إلى العنصر والروابط إلى العقد اليمنى واليسرى ، على عدد عناصر الشجرة الفرعية بأكملها. يجب تحديث هذه المعلومات بشكل صحيح عندما تتغير الشجرة.دعونا نرى كيف نجد ، على سبيل المثال ، عنصرًا بمؤشر = 4 في مثل هذه الشجرة.نبدأ الزحف من العقدة الجذرية (الجذر ، في حالتنا مع العنصر "r"). لدينا 3 خيارات: نحن بالفعل على العقدة اليمنى ، العقدة اليمنى على اليسار ، العقدة اليمنى على اليمين. لفهم مكان البحث عن العنصر المطلوب ، تحتاج إلى مقارنة حجم الشجرة الفرعية اليسرى (في حالتنا left.size = 3) والفهرس الحالي (في حالتنا 4). إذا كان هذان الرقمان متساويين ، فقد وجدنا العقدة اللازمة والعنصر المطلوب فيه. إذا كان حجم الشجرة الفرعية اليسرى أكبر ، فإن العقدة المطلوبة في الشجرة الفرعية اليسرى. إذا كان أقل ، فأنت بحاجة إلى النظر في الشجرة الفرعية اليمنى ، ولكنك تحتاج إلى تقليل الفهرس المطلوب: index = index - left.size - 1.نظرًا لأننا في حالتنا left.size <index ، فإننا نبحث في الشجرة الفرعية الصحيحة للعنصر باستخدام الفهرس الجديد 4 - 3 - 1 = 0. انتقل إلى العقدة مع العنصر "y".ثم نقوم بنفس الشيء الذي قمنا به في العقدة الجذرية. قارن حجم اليسار والفهرس. منذ 1> 0 ، ننظر في الشجرة الفرعية اليسرى ، وننتقل إلى العقدة بالعنصر "t".لا توجد شجرة فرعية متبقية في هذه العقدة ، وحجمها هو 0. index = left.size ، مما يعني أننا وجدنا عقدة مع الفهرس 4 ويمكننا الحصول على العنصر المطلوب "t" منها.في الكود الزائف ، يبدو كالتالي:function get(node: Node<T>, index: int): T {
val leftSize: int = (node.left == null) ? 0 : node.left.size;
if (leftSize == index) {
return node.obj;
} else if (leftSize > index) {
return get(node.left, index);
} else {
return get(node.right, index — leftSize — 1);
}
}
حاولت أن أصف المبدأ الأساسي لكيفية وضع مصفوفة في شجرة. يعمل هذا الهيكل ، بالطبع ، أبطأ من المصفوفة الكلاسيكية ، لـ O (log (n)) مقابل O (1). ولكن لها ميزة مهمة: إضافة عنصر إلى الوسط أو الإزالة من الوسط يعمل أيضًا مع O (log (n)) مقابل O (n) للصفيف. بالطبع ، شريطة أن تكون الشجرة متوازنة إلى حد ما. هناك العديد من الخوارزميات للحفاظ على شجرة بطريقة متوازنة تقريبًا. على سبيل المثال ، شجرة حمراء سوداء ، شجرة AVL ، شجرة ديكارتية. لن أكتب تفاصيل موازنة الشجرة ، أي خوارزمية مناسبة لنا. لنفترض فقط أن الشجرة متوازنة في المتوسط وأن عمقها الأقصى لا يختلف كثيرًا عن الحد الأدنى.تحسين طفيف
النهج الموصوف أعلاه ، مع التحقق من حجم الشجرة على اليسار مناسب للإدراك ، ولكن يمكن القيام به بشكل أكثر كفاءة. لكي لا ننظر إلى الشجرة الفرعية اليسرى في كل مرة ، بدلاً من حجم الشجرة ، يمكن للمرء تخزين موضعه في العقدة بالنسبة لموضع العقدة الأصلية. تخزن العقدة الجذرية موضعًا مطلقًا يتطابق مع حجم الشجرة الفرعية اليسرى. [el: r, pos: 3]
/ : \
/ : \
[el: w, pos: -2] : [el: y, pos: +2]
/ : \ : / : \
/ : \ : / : \
[el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
على سبيل المثال ، العقدة الجذر "r" لها الموضع 3. العقدة "w" لها الموضع -2 بالنسبة إلى العقدة الأصلية أو الموضع المطلق 3 + (-2) = 1. وبالمثل ، يمكنك النزول إلى مستوى واحد آخر ، على سبيل المثال ، العقدة "e" لها الموضع 3 + (-2) + (+1) = 2. أي ، مؤشر العقدة هو مجموع المواضع من جذر الشجرة إلى هذه العقدة.هذا التحسين ، بالإضافة إلى البحث السريع عن عنصر في القائمة ، سيوفر بحثًا أسرع وأسهل عن الفهرس على العقدة. ولكن ، بالطبع ، أصبح تحديث الموقف بشكل صحيح عند تغيير الشجرة أكثر صعوبة.إضافة فهرسة
لذا ، في الشجرة يمكننا أخذ عنصر حسب الفهرس ، وتغيير قيمته ، وإضافة عناصر إلى الوسط وحذفه. بشكل أساسي ، نحتاج فقط إلى إضافة بحث سريع في الفهرس حسب القيمة ، indexOf (obj). ثم يحتوي على (obj) وسيتم إزالة (obj) بشكل تافه.لكن أولاً ، دعنا نبسط المهمة قليلاً. دعونا نصنع هيكلًا يخزن فقط العناصر الفريدة.من أجل البحث بسرعة عن شيء ما ، عادة ما يستخدمون جدولًا. في عالم Java ، تسمى الجداول Map ؛ لها تطبيقان رئيسيان: HashMap و TreeMap. سيكون مفتاح الجدول رابطًا للكائن ، وستكون القيمة رابطًا لعقدة:class IndexedTreeListSet<T> {
root: Node<T>
indexMap: Map<T, Node<T>>
}
أولئك. يتكون الهيكل من جزأين: شجرة القائمة نفسها والجدول الذي يحتوي على روابط إلى كائنات وعقد هذه الشجرة. عند تحديث الشجرة ، يجب أيضًا تحديث الجدول. لن أصف العملية بالتفصيل. بشكل حدسي ، يجب أن يكون مفهوما: أضف عقدة - ضعها في الجدول ، احذف العقدة - احذفها من الجدول. من الناحية العملية ، هناك فروق دقيقة في موازنة الشجرة: يجب أن تغير الخوارزمية الروابط بين العقد ، وليس نقل الكائنات بين العقد. خلاف ذلك ، سيكون عليك القيام بالكثير من التحديثات في الجدول وسوف ينخفض الأداء.حسنًا ، سنفترض أنه يمكننا العثور بسرعة على العقدة حسب العنصر الذي تحتوي عليه. وماذا في ذلك؟ نحن بحاجة إلى العثور على فهرسها ، ولكن لا يمكن القيام بذلك حتى الآن. ولكن يمكننا تعقيد فئة العقدة بحيث لا تحتوي فقط على روابط إلى العقد اليسرى واليمنى ، ولكن أيضًا إلى أصلها:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
parent: Node<T>
pos: int
}
بالطبع ، تحديث الشجرة أكثر تعقيدًا قليلاً ، لأننا الآن بحاجة إلى تحديث الرابط إلى الوالد بعناية. ولكن الآن ، عند معرفة العقدة ، يمكننا صعود الشجرة وحساب فهرس أي عقدة. إذا استخدمنا التحسين من الفصل السابق ، فنحن بحاجة فقط إلى حساب مجموع المواضع من العقدة الحالية إلى الجذر.للحصول على قائمة تحتوي على عناصر فريدة ، يمكن اعتبار المشكلة محلولة.صحيح ، لدينا مشكلة صغيرة. لنفترض أننا نسمي مجموعة (فهرس ، كائن). يمكننا بسهولة استبدال عنصر واحد في عقدة بعنصر آخر ، ولكن فقط إذا لم يكن هناك عنصر جديد في القائمة حتى الآن. وإذا كان الأمر كذلك ، فماذا أفعل؟ إزالة العنصر الزائد من الموضع القديم ووضعه في عنصر جديد؟ أو العكس ، أضف أولاً ثم احذف؟ قد تكون النتيجة مختلفة. ولا يمكنك فعل أي شيء على الإطلاق أو الاستثناء. لا يوجد حل مثالي.الفرز بالطرق القياسية مثل هذه القائمة ، على الأرجح ، لن تعمل أيضًا. بعد كل شيء ، لن تعرف خوارزمية الفرز الحاجة إلى تفرد الكائنات وستنشئ نسخًا مكررة عند نقل العناصر في القائمة.نزيل التفرد
حسنًا ، ما يزيد الأمور تعقيدًا ، دعونا نحتفظ بنفس الأشياء. من الواضح أنك بحاجة إلى القيام بشيء ما مع الجدول. لا تبدو الفكرة الأولى لتخزين قائمة العقد فيها جيدة جدًا: مع زيادة طول القائمة ، سيتدهور الأداء. حتى O (n) إذا كانت جميع عناصر القائمة متماثلة.ثم دعنا نحاول تخزين شجرة من العقد مرتبة في جدول بدلاً من قائمة. مرتبة حسب الموضع في القائمة.class IndexedTreeList<T> {
root: Node<T>
indexMap: Map<T, TreeSet<Node<T>>>
}
بعد ذلك ، سيحدث الإدراج / الحذف من / إلى TreeSet <عقدة> بالحجم m أثناء مقارنات السجل (m) لمواقع العقد ، وستحدث كل مقارنة عبر وقت التسجيل (n). سيحدث التعقيد النهائي للإدراج أو الحذف في بنية مماثلة في O (log (n) * (1 + log (m))) ، حيث n هو العدد الإجمالي للعناصر في القائمة و m هو عدد العناصر في القائمة يساوي العناصر المدرجة / المحذوفة. في أسوأ الحالات ، عندما تكون جميع العناصر متساوية مع بعضها البعض ، نحصل على التعقيد O (log (n) ^ 2).ربما يعترض القارئ اليقظ: ولكن ماذا عن الثبات؟ بعد كل شيء ، لا يمكننا تغيير الكائنات إذا كانت مفاتيح الجدول؟ بشكل عام ، هو كذلك. ومع ذلك ، بالنسبة للشجرة التي تقوم بتخزين الكائنات المصنفة في المفاتيح ، بالإضافة إلى القواعد القياسية للمقارنات ، يكفي الحفاظ على الثابت: إذا كانت العلامة <b ، فيجب ألا تتغير هذه الخاصية بمرور الوقت. هذه هي حالتنا فقط: إذا كان موضع عقدة واحدة أقل من موضع عقدة أخرى ، فسيتم الاحتفاظ بهذه الخاصية بغض النظر عن عدد العقد التي تم إضافتها أو حذفها فيما بينها.هل من الممكن أن تجعل الهيكل ثابتًا؟
إجابة مختصرة: لا ، هذا مستحيل. بسبب الارتباط الثنائي للشجرة ، من الجذر إلى الأوراق والظهر ، لدينا كل عقدة من الشجرة متصلة ببعضها. لا يمكن تحقيق الثبات بهذه الطريقة ؛ يجب عليك إعادة بناء الهيكل بأكمله بأي تغيير.لكني أفهم كيفية تنفيذ بنية مستمرة للحالات التي لا نحتاج فيها لإدراج عناصر في منتصف القائمة. يمكنك إضافة عناصر إلى البداية أو النهاية ، ويمكنك الحذف من المنتصف. الخصائص المتبقية هي نفسها.إذا كنت مهتمًا ، فسأحاول كتابة مقال حول هذا الهيكل. ربما أقوم بتطبيقه في Java أو Kotlin أو Scala. ولكن ، على الأرجح ، لن يكون ذلك قريبًا.بعض ميزات التنفيذ
أريد هنا أن أصف بعض الميزات التي كان علي مواجهتها.حول أحد التحسينات حول تخزين موضع العقدة في القائمة ، كتبت أعلاه. هنا تتجلى قوة المصدر المفتوح: لقد أخذت كود TreeList الجاهز ولم أخوض في تفاصيل شجرة AVL ، وتناوب العقدة ، وتحديثات الموضع ، إلخ.ميزة أخرى موروثة من TreeList هي الروابط إلى الأشجار الفرعية في أوراق الشجرة. تخزن كل عقدة منطقية leftIsefore و rightIsNext. تشير هذه المتغيرات إلى وجود أو عدم وجود شجرة فرعية يسار / يمين. إذا لم يكن هناك شجرة فرعية ، في اليسار / اليمين ، بدلاً من ارتباط إلى الشجرة الفرعية ، يتم تخزين ارتباط العقدة التي تتوافق مع العنصر السابق أو التالي. في مثالنا ، ["q" ، "w" ، "e" ، "r" ، "t" ، "y" ، "u"] العقدة "e" مورقة ، ليس لها أشجار فرعية. وبناءً على ذلك ، فإن rightIs Former و rightIsNext صحيحان ، ويشيران يسارًا ويمينًا إلى العقدتين "w" و "r" ، على التوالي. يساعد هذا الأسلوب على تكرار القائمة بشكل أسرع. ويتداخل مع برمجة الميزات الجديدة :)قليلا عن العمل مع عقدة كائن الجدول →. من الناحية المثالية ، تحتاج إلى وضع عنصر في الجدول مرة واحدة عند إضافته إلى الهيكل وحذفه مرة واحدة عند الحذف من الهيكل. عمليا ، لم أستطع تحقيق ذلك. عند إضافة عنصر ، يتم إضافته إلى الجدول ، كل شيء كما ينبغي. ومع ذلك ، عند حذف عنصر ، تقوم خوارزمية الموازنة أحيانًا بنقل العناصر بين العقد. تكون النتيجة حذفان وسجل واحد في الجدول بدلاً من حذف واحد. يمكن إصلاح هذا إذا قمت بإزالة التحسين من leftIs previous و rightIsNext. وحتى الحصول على مكاسب صغيرة في الأداء ، وليس فقط أثناء الإزالة. في بعض الاختبارات ، كانت الزيادة 10-20٪. لكن سرعة التكرار تنخفض بشكل ملحوظ ، 1.5-2.5 مرة في اختباراتي. قررت ترك التحسين في الوقت الحالي.في Java ، الأنواع الرئيسية للجداول هي HashMap و TreeMap. للجدول ، يستخدم كائن ← عقدة HashMap بشكل افتراضي. ومع ذلك ، يمكنك استخدام TreeMap مع مقارنة خاصة بالمهمة. في هذه الحالة ، سيقوم indexOf (obj) و remove (obj) بالبحث / حذف الكائن الذي يساوي الكائن المحدد وفقًا لكود المقارنة. على سبيل المثال ، نقوم بتخزين قائمة المستخدمين ، ويقارن المقارنة المستخدمين بالاسم فقط. ثم يمكننا الإجابة على السؤال "ما هي مواضع القائمة التي يحملها المستخدمون باسم" نابليون؟ ". أو إزالة جميع نابليون من القائمة :).البنية لا تدعم فارغة. يمكنك إصلاحه ، ولكن لا يوجد شعور بأنه ضروري.فيما يتعلق بحقيقة أن الهيكل "يعرف كل شيء" ، بالطبع ، كنت مضللاً بعض الشيء. بالطبع ، عند العمل مع عناصر مفردة ، كل شيء على ما يرام وفي ظل ظروف معينة حتى بالنسبة للوغاريتم. ومع ذلك ، فهي لا تعرف بعض الأشياء التي يمكن أن تفعلها الهياكل الأخرى. على سبيل المثال ، شجرة ديكارتية بمفتاح ضمني ، كانت هناك مقالات حولها على المحور لا يعرف كيفية القيام بسرعة indexOf ، لكنه يعرف كيف يصنع قائمة فرعية وسلس قائمتين في واحدة للوغاريتم (في المتوسط ، غير مضمون) ، بالإضافة إلى أنه يمكن جعله ثابتًا.أداء
في Java ، يتم قياس الأداء عادةً باستخدام إطار jmh. تم إجراء الاختبارات على MacBook Pro 2017 تحت Java11.لقد قارنت أداء ArrayList القياسي ، TreeList من مجموعات أباتشي المشتركة ، وفئتي IndexedTreeList و IndexedTreeListSet في عدة سيناريوهات. في كل سيناريو ، تم تنفيذ 1000 عملية من نفس النوع ، لذلك يجب ضرب النتيجة في 1000.كود تحت المفسد@Fork(1)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public class PerformanceCompare {
public static final Map<String, Class> CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,
ArrayList.class)
.collect(Collectors.toMap(c -> c.getSimpleName(), c -> c));
public static final int ITERATIONS = 1000;
@State(Scope.Benchmark)
public static class Plan {
@Param({"10", "100", "1000", "10000", "100000", "1000000"/*, "10000000"*/})
public int size;
@Param({"ArrayList", "TreeList", "IndexedTreeList", "IndexedTreeListSet"})
public String className;
private Random random;
private List<Integer> list;
@Setup
public void init() throws IllegalAccessException, InstantiationException {
random = new Random();
list = (List<Integer>) CLASSES.get(className).newInstance();
for (int i = 0; i < size; i++) {
list.add(i);
}
}
}
@Benchmark
public void indexOfKnown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value = list.indexOf(random.nextInt(plan.size));
}
blackhole.consume(value);
}
@Benchmark
public void indexOfUnknown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.indexOf(random.nextInt());
}
blackhole.consume(value);
}
@Benchmark
public void addRemoveRandom(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
list.add(random.nextInt(list.size() + 1), random.nextInt());
value += list.remove(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Benchmark
public void get(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.get(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(PerformanceCompare.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
بادئ ذي بدء ، قارنت سرعة الحصول على عنصر عشوائي من القائمة. سأحذرك على الفور أن النفقات العامة في هذا الاختبار مهمة جدًا. النتائج التي تقترب من 100000 * 1000 عملية في الثانية مشوهة بشدة.احصل على نتيجة الاختبارPerformanceCompare.get ArrayList 10 thrpt 5 79865.412 ± 10145.202 ops/s
PerformanceCompare.get ArrayList 100 thrpt 5 81862.243 ± 983.727 ops/s
PerformanceCompare.get ArrayList 1000 thrpt 5 81033.507 ± 4540.206 ops/s
PerformanceCompare.get ArrayList 10000 thrpt 5 64096.123 ± 1430.361 ops/s
PerformanceCompare.get ArrayList 100000 thrpt 5 41289.491 ± 11286.114 ops/s
PerformanceCompare.get ArrayList 1000000 thrpt 5 8598.944 ± 2048.461 ops/s
PerformanceCompare.get TreeList 10 thrpt 5 33912.275 ± 3754.284 ops/s
PerformanceCompare.get TreeList 100 thrpt 5 21346.854 ± 863.588 ops/s
PerformanceCompare.get TreeList 1000 thrpt 5 14808.414 ± 508.098 ops/s
PerformanceCompare.get TreeList 10000 thrpt 5 8679.384 ± 109.250 ops/s
PerformanceCompare.get TreeList 100000 thrpt 5 4605.998 ± 1028.945 ops/s
PerformanceCompare.get TreeList 1000000 thrpt 5 2241.381 ± 768.147 ops/s
PerformanceCompare.get IndexedTreeList 10 thrpt 5 34054.357 ± 3682.829 ops/s
PerformanceCompare.get IndexedTreeList 100 thrpt 5 21934.002 ± 2339.947 ops/s
PerformanceCompare.get IndexedTreeList 1000 thrpt 5 14626.691 ± 369.893 ops/s
PerformanceCompare.get IndexedTreeList 10000 thrpt 5 7386.863 ± 342.150 ops/s
PerformanceCompare.get IndexedTreeList 100000 thrpt 5 4562.126 ± 352.772 ops/s
PerformanceCompare.get IndexedTreeList 1000000 thrpt 5 2105.718 ± 702.064 ops/s
PerformanceCompare.get IndexedTreeListSet 10 thrpt 5 33317.503 ± 2307.829 ops/s
PerformanceCompare.get IndexedTreeListSet 100 thrpt 5 21247.440 ± 1253.386 ops/s
PerformanceCompare.get IndexedTreeListSet 1000 thrpt 5 14665.557 ± 487.833 ops/s
PerformanceCompare.get IndexedTreeListSet 10000 thrpt 5 7667.214 ± 80.093 ops/s
PerformanceCompare.get IndexedTreeListSet 100000 thrpt 5 3454.023 ± 82.994 ops/s
PerformanceCompare.get IndexedTreeListSet 1000000 thrpt 5 1768.701 ± 35.878 ops/s
هنا ، ومن الغريب ، فإن أكبر اهتمام هو ArrayList القياسي. من الناحية النظرية ، يجب أن تكون سرعة الخروج منه ثابتة ولا تعتمد على عدد العناصر. من الناحية العملية ، يحتفظ الأداء أولاً بحوالي 90،000 * 1000 عملية في الثانية (تذكر النفقات العامة) ، ولكن مع طول قائمة عدة آلاف من العناصر ، يبدأ في الترهل. ويرجع ذلك إلى فقدان ذاكرة التخزين المؤقت بشكل متكرر بشكل متزايد: لا تحتوي ذاكرة التخزين المؤقت للمعالج على البيانات اللازمة ، وفي كثير من الأحيان تحتاج إلى البحث عن البيانات في ذاكرة الوصول العشوائي. مع وجود مليون عنصر ، تكون سرعة الاختبار أقل بعشر مرات ، ولكن عمليًا ، يكون انخفاض الأداء أكبر.من المتوقع أن تُظهر TreeList و IndexedTreeList و IndexedTreeListSet نتائج مماثلة. متوقع أبطأ بكثير من ArrayList. حتى مع وجود عدد قليل من العناصر ، فإن TreeList أبطأ عدة مرات من ArrayList ، على الرغم من أن الاختبار يظهر الفرق مرتين فقط.الاختبار التالي هو addRemoveRandom. هنا ، في كل اختبار ، أدرج عنصرًا في موضع عشوائي وأزيل عنصرًا من موضع عشوائي.نتيجة اختبار AddRemoveRandomPerformanceCompare.addRemoveRandom ArrayList 10 thrpt 5 12440.764 ± 485.642 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100 thrpt 5 9880.123 ± 464.014 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000 thrpt 5 5288.905 ± 1219.055 ops/s
PerformanceCompare.addRemoveRandom ArrayList 10000 thrpt 5 1024.942 ± 179.366 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100000 thrpt 5 91.219 ± 25.380 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000000 thrpt 5 5.499 ± 0.400 ops/s
PerformanceCompare.addRemoveRandom TreeList 10 thrpt 5 6242.607 ± 350.290 ops/s
PerformanceCompare.addRemoveRandom TreeList 100 thrpt 5 3117.945 ± 116.066 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000 thrpt 5 1829.778 ± 80.516 ops/s
PerformanceCompare.addRemoveRandom TreeList 10000 thrpt 5 1230.077 ± 53.381 ops/s
PerformanceCompare.addRemoveRandom TreeList 100000 thrpt 5 443.571 ± 69.207 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000000 thrpt 5 308.963 ± 84.077 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10 thrpt 5 3556.511 ± 144.596 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100 thrpt 5 2120.777 ± 83.848 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000 thrpt 5 1211.112 ± 92.288 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10000 thrpt 5 789.458 ± 19.450 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100000 thrpt 5 302.989 ± 40.030 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000000 thrpt 5 178.822 ± 92.853 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10 thrpt 5 4138.007 ± 119.943 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100 thrpt 5 2435.803 ± 20.276 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000 thrpt 5 1445.054 ± 276.909 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10000 thrpt 5 972.256 ± 19.987 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100000 thrpt 5 366.608 ± 94.487 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000000 thrpt 5 227.677 ± 48.276 ops/s
يمكن افتراض أن ArrayList أسرع في القوائم الصغيرة. ومع ذلك ، فإن حقيقة فوزه في هذا الاختبار على قوائم تصل إلى 10000 عنصر تبدو مثيرة للاهتمام. على ما يبدو ، تم تحسين System.arrayCopy بشكل جيد للغاية ويستخدم جميع ميزات المعالجات الحديثة. بدءًا من 10000 عنصر ، بدأت هياكل البيانات المتخصصة في الفوز. مع 1000000 عنصر ، فرق السرعة هو 30-50 مرة.من المتوقع أن يكون IndexedTreeList و IndexedTreeListSet أبطأ من TreeList. حوالي 1.5 - 2 مرة.يجب أن يثبت الاختباران المتبقيان indexOfKnown و indexOfUnknown السمة الرئيسية لهذا الهيكل. الفرق بين الاختبارات هو أننا في حالة واحدة نبحث عن عنصر موجود في القائمة ، وفي الحالة الأخرى نبحث عن عنصر غير موجود في القائمة.اختبار نتيجة indexOfKnown و indexOfUnknownPerformanceCompare.indexOfKnown ArrayList 10 thrpt 5 41424.356 ± 549.047 ops/s
PerformanceCompare.indexOfKnown ArrayList 100 thrpt 5 17216.477 ± 1444.744 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000 thrpt 5 2296.306 ± 76.372 ops/s
PerformanceCompare.indexOfKnown ArrayList 10000 thrpt 5 233.863 ± 26.926 ops/s
PerformanceCompare.indexOfKnown ArrayList 100000 thrpt 5 23.208 ± 2.776 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000000 thrpt 5 0.919 ± 0.455 ops/s
PerformanceCompare.indexOfKnown TreeList 10 thrpt 5 26740.708 ± 1323.125 ops/s
PerformanceCompare.indexOfKnown TreeList 100 thrpt 5 5670.923 ± 99.638 ops/s
PerformanceCompare.indexOfKnown TreeList 1000 thrpt 5 745.408 ± 26.827 ops/s
PerformanceCompare.indexOfKnown TreeList 10000 thrpt 5 52.288 ± 1.362 ops/s
PerformanceCompare.indexOfKnown TreeList 100000 thrpt 5 4.224 ± 0.855 ops/s
PerformanceCompare.indexOfKnown TreeList 1000000 thrpt 5 0.193 ± 0.052 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10 thrpt 5 34485.128 ± 1582.703 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100 thrpt 5 29209.412 ± 1544.268 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000 thrpt 5 21139.584 ± 1442.867 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10000 thrpt 5 12544.306 ± 312.097 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100000 thrpt 5 3538.201 ± 272.537 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000000 thrpt 5 1420.119 ± 538.476 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10 thrpt 5 39201.995 ± 1887.065 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100 thrpt 5 34204.112 ± 1122.517 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000 thrpt 5 25374.557 ± 1596.746 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10000 thrpt 5 14291.317 ± 391.180 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100000 thrpt 5 4215.898 ± 283.680 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000000 thrpt 5 1729.100 ± 1260.815 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10 thrpt 5 59053.313 ± 1845.665 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100 thrpt 5 10867.572 ± 142.823 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000 thrpt 5 1186.583 ± 28.003 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10000 thrpt 5 120.953 ± 4.146 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100000 thrpt 5 11.936 ± 0.320 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000000 thrpt 5 0.566 ± 0.335 ops/s
PerformanceCompare.indexOfUnknown TreeList 10 thrpt 5 28134.237 ± 2291.670 ops/s
PerformanceCompare.indexOfUnknown TreeList 100 thrpt 5 3153.930 ± 158.734 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000 thrpt 5 322.383 ± 44.245 ops/s
PerformanceCompare.indexOfUnknown TreeList 10000 thrpt 5 25.674 ± 1.787 ops/s
PerformanceCompare.indexOfUnknown TreeList 100000 thrpt 5 1.867 ± 0.291 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000000 thrpt 5 0.093 ± 0.008 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10 thrpt 5 66625.126 ± 5232.668 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100 thrpt 5 70038.055 ± 5803.848 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000 thrpt 5 63240.467 ± 885.956 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10000 thrpt 5 54731.988 ± 3950.150 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100000 thrpt 5 22049.476 ± 821.924 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000000 thrpt 5 9459.862 ± 804.738 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10 thrpt 5 70274.968 ± 15830.355 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100 thrpt 5 71017.685 ± 6920.447 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000 thrpt 5 66405.960 ± 1127.231 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10000 thrpt 5 57983.963 ± 3276.142 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100000 thrpt 5 41277.110 ± 9919.893 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000000 thrpt 5 9840.185 ± 2159.352 ops/s
هنا ، ArrayList و TreeList ليس لديهم مفاجآت تقريبًا. مع زيادة الحجم ، تنخفض السرعة بشكل خطي تقريبًا. من المتوقع أن يكون البحث عن عنصر من قائمة غير قائمة أبطأ مرتين من البحث عن عنصر من القائمة ، لأن تحتاج إلى مراجعة المجموعة الكاملة بدلاً من النصف في المتوسط.لكن IndexedTreeList و IndexedTreeListSet هنا تظهر النتيجة الجيدة المتوقعة. تُظهر هياكل البيانات هذه سرعة تنفيذ indexOf مماثلة لـ ArrayList حتى مع 10 عناصر. مع 1000 عنصر ، هذه الهياكل أسرع 10 مرات ، مع 1،000،000 أسرع 1000 مرة. عند البحث عن عنصر غير موجود في القائمة ، يُتوقع أن تعطي سرعة أفضل من البحث عن عنصر من القائمة.ما يثير الاهتمام أيضًا هو انخفاض أداء IndexedTreeList و IndexedTreeListSet في اختبار indexOfUnknown. هنا الوضع مشابه لذلك الموجود في الاختبار مع ArrayList.get. من الناحية النظرية ، لم يكن يجب أن نحصل على انخفاض في الأداء ، ولكن من الناحية العملية ، بسبب فقدان ذاكرة التخزين المؤقت ، فقد حصلنا عليها ، علاوة على ذلك ، بشكل ملحوظ.بدلا من الاستنتاج
ما زلت لا أعرف ما إذا كان الهيكل المقترح له حداثة أم لا. من ناحية ، الفكرة ليست معقدة إذا كنت تعرف كيف تعمل الشجرة بمفتاح ضمني. من ناحية أخرى ، لم أر وصفًا لهيكل به مثل هذه الخصائص. وإذا كان الأمر كذلك ، فمن المنطقي جعل الهيكل أكثر شهرة ، فقد يكون مفيدًا لشخص ما.ولكن حتى لو كانت هذه دراجة أخرى ، حاولت أن أجعلها مفيدة. تم إنشاء طلب سحب في مجموعات مشتركة ، ولكن في وقت كتابة هذا المقال لم يتم سكب هذا المقال بعد. بمعرفة مدى بطء حدوث كل شيء في المصدر المفتوح ، لن أفاجأ إذا استمرت العملية لأشهر.فوجئت إلى حد ما بنتيجة مقارنة أداء ArrayList و TreeList. أظهرت الاختبارات أن TreeList لا معنى لاستخدام ما يصل إلى 10000 عنصر في حجم القائمة. سيكون من المثير للاهتمام تجربة شجرة b بدلاً من شجرة ثنائية. يجب أن تستخدم هذه البنية الذاكرة بشكل أكثر دقة ، وعلى الأرجح ، تعمل بشكل أسرع. ولها يمكنك تكييف الفكرة مع الفهرسة.على أي حال ، من الممتع أن يكون لديك أداة في الترسانة يمكنها (تقريبًا) القيام بكل شيء مع تعقيد يمكن التنبؤ به.المراجع
مشروع
طلب سحب أصلي في تذكرة مجموعات أباتشي المشتركةفي جيرا