لماذا يكون الإدراج في شجرتي أسرع عند الإدخال المفرز مقارنة بالإدخال العشوائي؟
https://stackoverflow.com/questions/2437733
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لقد سمعت دائمًا أن إنشاء أشجار البحث الثنائية أسرع من البيانات المحددة عشوائيًا مقارنة بالبيانات المطلوبة، وذلك ببساطة لأن البيانات المطلوبة تتطلب إعادة توازن صريحة للحفاظ على ارتفاع الشجرة عند الحد الأدنى.
لقد قمت مؤخرًا بتنفيذ برنامج غير قابل للتغيير فخ, ، نوع خاص من شجرة البحث الثنائية التي تستخدم التوزيع العشوائي للحفاظ على توازنها نسبيًا.وعلى عكس ما كنت أتوقعه، وجدت أنه يمكنني دائمًا إنشاء خطوة أسرع بحوالي 2x وأكثر توازنًا بشكل عام من البيانات المطلوبة مقارنة بالبيانات غير المرتبة - وليس لدي أي فكرة عن السبب.
وهنا تنفيذ فخ بلدي:
وهنا برنامج اختبار:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace ConsoleApplication1
{
class Program
{
static Random rnd = new Random();
const int ITERATION_COUNT = 20;
static void Main(string[] args)
{
List<double> rndTimes = new List<double>();
List<double> orderedTimes = new List<double>();
rndTimes.Add(TimeIt(50, RandomInsert));
rndTimes.Add(TimeIt(100, RandomInsert));
rndTimes.Add(TimeIt(200, RandomInsert));
rndTimes.Add(TimeIt(400, RandomInsert));
rndTimes.Add(TimeIt(800, RandomInsert));
rndTimes.Add(TimeIt(1000, RandomInsert));
rndTimes.Add(TimeIt(2000, RandomInsert));
rndTimes.Add(TimeIt(4000, RandomInsert));
rndTimes.Add(TimeIt(8000, RandomInsert));
rndTimes.Add(TimeIt(16000, RandomInsert));
rndTimes.Add(TimeIt(32000, RandomInsert));
rndTimes.Add(TimeIt(64000, RandomInsert));
rndTimes.Add(TimeIt(128000, RandomInsert));
string rndTimesAsString = string.Join("\n", rndTimes.Select(x => x.ToString()).ToArray());
orderedTimes.Add(TimeIt(50, OrderedInsert));
orderedTimes.Add(TimeIt(100, OrderedInsert));
orderedTimes.Add(TimeIt(200, OrderedInsert));
orderedTimes.Add(TimeIt(400, OrderedInsert));
orderedTimes.Add(TimeIt(800, OrderedInsert));
orderedTimes.Add(TimeIt(1000, OrderedInsert));
orderedTimes.Add(TimeIt(2000, OrderedInsert));
orderedTimes.Add(TimeIt(4000, OrderedInsert));
orderedTimes.Add(TimeIt(8000, OrderedInsert));
orderedTimes.Add(TimeIt(16000, OrderedInsert));
orderedTimes.Add(TimeIt(32000, OrderedInsert));
orderedTimes.Add(TimeIt(64000, OrderedInsert));
orderedTimes.Add(TimeIt(128000, OrderedInsert));
string orderedTimesAsString = string.Join("\n", orderedTimes.Select(x => x.ToString()).ToArray());
Console.WriteLine("Done");
}
static double TimeIt(int insertCount, Action<int> f)
{
Console.WriteLine("TimeIt({0}, {1})", insertCount, f.Method.Name);
List<double> times = new List<double>();
for (int i = 0; i < ITERATION_COUNT; i++)
{
Stopwatch sw = Stopwatch.StartNew();
f(insertCount);
sw.Stop();
times.Add(sw.Elapsed.TotalMilliseconds);
}
return times.Average();
}
static void RandomInsert(int insertCount)
{
Treap<double> tree = new Treap<double>((x, y) => x.CompareTo(y));
for (int i = 0; i < insertCount; i++)
{
tree = tree.Insert(rnd.NextDouble());
}
}
static void OrderedInsert(int insertCount)
{
Treap<double> tree = new Treap<double>((x, y) => x.CompareTo(y));
for(int i = 0; i < insertCount; i++)
{
tree = tree.Insert(i + rnd.NextDouble());
}
}
}
}
وإليك مخططًا يقارن أوقات الإدراج العشوائية والمرتبة بالمللي ثانية:
Insertions Random Ordered RandomTime / OrderedTime
50 1.031665 0.261585 3.94
100 0.544345 1.377155 0.4
200 1.268320 0.734570 1.73
400 2.765555 1.639150 1.69
800 6.089700 3.558350 1.71
1000 7.855150 4.704190 1.67
2000 17.852000 12.554065 1.42
4000 40.157340 22.474445 1.79
8000 88.375430 48.364265 1.83
16000 197.524000 109.082200 1.81
32000 459.277050 238.154405 1.93
64000 1055.508875 512.020310 2.06
128000 2481.694230 1107.980425 2.24
لا أرى أي شيء في الكود يجعل الإدخال المرتب أسرع بشكل غير مقارب من الإدخال غير المرتب، لذا فأنا في حيرة من أمري لشرح الفرق.
لماذا يعد إنشاء خطوة من المدخلات المطلوبة أسرع بكثير من بناء المدخلات العشوائية؟
المحلول
أشجار التوازن الذاتي موجودة ل يصلح المشاكل المرتبطة بالبيانات غير الموزعة عشوائيا.بحكم التعريف، فإنهم يستبدلون قليلاً من أفضل أداء الحالة لتحسين أداء أسوأ الحالات بشكل كبير المرتبط بـ BSTs غير المتوازنة، وتحديداً المدخلات المصنفة.
أنت في الواقع تبالغ في التفكير في هذه المشكلة، لأن الإدراج البطيء للبيانات العشوائية مقابل الإدراج البطيء للبيانات العشوائية.البيانات المطلوبة هي سمة من سمات أي شجرة متوازنة.جربه على AVL وسترى نفس النتائج.
كاميرون كان لديه الفكرة الصحيحة، حيث قام بإزالة فحص الأولوية لفرض أسوأ الحالات.إذا قمت بذلك وقمت بتجهيز شجرتك حتى تتمكن من رؤية عدد عمليات إعادة التوازن التي تحدث لكل إدخال، يصبح في الواقع ما يحدث واضحًا جدًا.عند إدراج بيانات مرتبة، تدور الشجرة دائمًا إلى اليسار ويكون الفرع الأيمن للجذر فارغًا دائمًا.يؤدي الإدراج دائمًا إلى إعادة توازن واحدة تمامًا لأن عقدة الإدراج لا تحتوي على أي عناصر فرعية ولا يحدث أي تكرار.من ناحية أخرى، عند تشغيله على البيانات العشوائية، تبدأ على الفور تقريبًا في رؤية عمليات إعادة توازن متعددة تحدث في كل إدراج، ما يصل إلى 5 أو 6 منها في أصغر حالة (50 إدخالًا)، لأن ذلك يحدث على الأشجار الفرعية مثل حسنًا.
مع إعادة تشغيل التحقق من الأولوية، لا تتم عمليات إعادة التوازن فقط عادةً أقل غلاء بسبب دفع المزيد من العقد إلى الشجرة الفرعية اليسرى (حيث لا تخرج أبدًا بسبب عدم حدوث أي إدخالات هناك)، ولكنها أيضًا أقل احتمالا أن يحدث.لماذا؟لأنه في الخطوة، تطفو العقد ذات الأولوية العالية إلى الأعلى، وتبدأ الدورات المستمرة لليسار (غير المصحوبة بدورات لليمين) في دفع جميع العقد ذات الأولوية العالية إلى الشجرة الفرعية اليسرى أيضًا.والنتيجة هي أن عمليات إعادة التوازن تحدث بشكل أقل تواترا بسبب التوزيع غير المتكافئ للاحتمالات.
إذا استخدمت رمز إعادة التوازن، فسوف ترى أن هذا صحيح؛بالنسبة لكل من المدخلات المصنفة والعشوائية، ينتهي بك الأمر بأعداد متطابقة تقريبًا من الدورات إلى اليسار، لكن الإدخال العشوائي يعطي أيضًا نفس العدد من الدورات إلى اليمين، مما يؤدي إلى ضعف العدد الإجمالي.لا ينبغي أن يكون هذا مفاجئًا - يجب أن يؤدي الإدخال الغاوسي إلى توزيع التدويرات الغاوسي.سترى أيضًا أن هناك حوالي 60-70% فقط من عمليات إعادة التوازن ذات المستوى الأعلى للمدخلات التي تم فرزها، والتي ربما يكون من المثير للدهشة، ومرة أخرى، أن هذا بسبب المدخلات المصنفة التي تعبث بالتوزيع الطبيعي للأولويات.
يمكنك أيضًا التحقق من ذلك عن طريق فحص الشجرة الكاملة في نهاية حلقة الإدراج.مع الإدخال العشوائي، تميل الأولويات إلى الانخفاض بشكل خطي إلى حد ما حسب المستوى؛مع المدخلات المصنفة، تميل الأولويات إلى البقاء عالية جدًا حتى تصل إلى مستوى أو مستويين من الأسفل.
آمل أن أكون قد قمت بعمل لائق في شرح هذا ...اسمحوا لي أن أعرف إذا كان أي منها غامضا للغاية.
نصائح أخرى
ركضت الكود الخاص بك، وأعتقد أن الأمر يتعلق بعدد الدوران. أثناء الإدخال المطلوب، فإن عدد الدوران الأمثل، ولن تضطر الشجرة إلى تدوير الظهر.
خلال إدخال عشوائي، يجب أن تضطر الشجرة إلى إجراء المزيد من الدورات، لأنه قد تضطر إلى تدوير ذهابا وإيابا.
لمعرفة ذلك حقا، يجب أن أضيف عدادات لأرقام التناوب اليمنى واليمين لكل تشغيل. ربما يمكنك القيام بذلك بنفسك.
تحديث:
وضعت نقاط التوقف على rotateleft و surnatoright. أثناء ترتيب المدخلات الدوارة لا يستخدم أبدا. أثناء إدخال عشوائي، يضرب كلاهما، ويبدو لي أنهم يستخدمون بشكل متكرر.
تحديث 2:
أضفت بعض الإخراج إلى العنصر 50 المطلوب (استبدال مع الأعداد الصحيحة للوضوح)، لمعرفة المزيد:
TimeIt(50, OrderedInsert)
LastValue = 0, Top.Value = 0, Right.Count = 0, Left.Count = 0
RotateLeft @value=0
LastValue = 1, Top.Value = 1, Right.Count = 0, Left.Count = 1
LastValue = 2, Top.Value = 1, Right.Count = 1, Left.Count = 1
LastValue = 3, Top.Value = 1, Right.Count = 2, Left.Count = 1
RotateLeft @value=3
RotateLeft @value=2
RotateLeft @value=1
LastValue = 4, Top.Value = 4, Right.Count = 0, Left.Count = 4
LastValue = 5, Top.Value = 4, Right.Count = 1, Left.Count = 4
LastValue = 6, Top.Value = 4, Right.Count = 2, Left.Count = 4
RotateLeft @value=6
LastValue = 7, Top.Value = 4, Right.Count = 3, Left.Count = 4
LastValue = 8, Top.Value = 4, Right.Count = 4, Left.Count = 4
RotateLeft @value=8
RotateLeft @value=7
LastValue = 9, Top.Value = 4, Right.Count = 5, Left.Count = 4
LastValue = 10, Top.Value = 4, Right.Count = 6, Left.Count = 4
RotateLeft @value=10
RotateLeft @value=9
RotateLeft @value=5
RotateLeft @value=4
LastValue = 11, Top.Value = 11, Right.Count = 0, Left.Count = 11
LastValue = 12, Top.Value = 11, Right.Count = 1, Left.Count = 11
RotateLeft @value=12
LastValue = 13, Top.Value = 11, Right.Count = 2, Left.Count = 11
RotateLeft @value=13
LastValue = 14, Top.Value = 11, Right.Count = 3, Left.Count = 11
LastValue = 15, Top.Value = 11, Right.Count = 4, Left.Count = 11
RotateLeft @value=15
RotateLeft @value=14
LastValue = 16, Top.Value = 11, Right.Count = 5, Left.Count = 11
LastValue = 17, Top.Value = 11, Right.Count = 6, Left.Count = 11
RotateLeft @value=17
LastValue = 18, Top.Value = 11, Right.Count = 7, Left.Count = 11
LastValue = 19, Top.Value = 11, Right.Count = 8, Left.Count = 11
RotateLeft @value=19
LastValue = 20, Top.Value = 11, Right.Count = 9, Left.Count = 11
LastValue = 21, Top.Value = 11, Right.Count = 10, Left.Count = 11
RotateLeft @value=21
LastValue = 22, Top.Value = 11, Right.Count = 11, Left.Count = 11
RotateLeft @value=22
RotateLeft @value=20
RotateLeft @value=18
LastValue = 23, Top.Value = 11, Right.Count = 12, Left.Count = 11
LastValue = 24, Top.Value = 11, Right.Count = 13, Left.Count = 11
LastValue = 25, Top.Value = 11, Right.Count = 14, Left.Count = 11
RotateLeft @value=25
RotateLeft @value=24
LastValue = 26, Top.Value = 11, Right.Count = 15, Left.Count = 11
LastValue = 27, Top.Value = 11, Right.Count = 16, Left.Count = 11
RotateLeft @value=27
LastValue = 28, Top.Value = 11, Right.Count = 17, Left.Count = 11
RotateLeft @value=28
RotateLeft @value=26
RotateLeft @value=23
RotateLeft @value=16
RotateLeft @value=11
LastValue = 29, Top.Value = 29, Right.Count = 0, Left.Count = 29
LastValue = 30, Top.Value = 29, Right.Count = 1, Left.Count = 29
LastValue = 31, Top.Value = 29, Right.Count = 2, Left.Count = 29
LastValue = 32, Top.Value = 29, Right.Count = 3, Left.Count = 29
RotateLeft @value=32
RotateLeft @value=31
LastValue = 33, Top.Value = 29, Right.Count = 4, Left.Count = 29
RotateLeft @value=33
RotateLeft @value=30
LastValue = 34, Top.Value = 29, Right.Count = 5, Left.Count = 29
RotateLeft @value=34
LastValue = 35, Top.Value = 29, Right.Count = 6, Left.Count = 29
LastValue = 36, Top.Value = 29, Right.Count = 7, Left.Count = 29
LastValue = 37, Top.Value = 29, Right.Count = 8, Left.Count = 29
RotateLeft @value=37
LastValue = 38, Top.Value = 29, Right.Count = 9, Left.Count = 29
LastValue = 39, Top.Value = 29, Right.Count = 10, Left.Count = 29
RotateLeft @value=39
LastValue = 40, Top.Value = 29, Right.Count = 11, Left.Count = 29
RotateLeft @value=40
RotateLeft @value=38
RotateLeft @value=36
LastValue = 41, Top.Value = 29, Right.Count = 12, Left.Count = 29
LastValue = 42, Top.Value = 29, Right.Count = 13, Left.Count = 29
RotateLeft @value=42
LastValue = 43, Top.Value = 29, Right.Count = 14, Left.Count = 29
LastValue = 44, Top.Value = 29, Right.Count = 15, Left.Count = 29
RotateLeft @value=44
LastValue = 45, Top.Value = 29, Right.Count = 16, Left.Count = 29
LastValue = 46, Top.Value = 29, Right.Count = 17, Left.Count = 29
RotateLeft @value=46
RotateLeft @value=45
LastValue = 47, Top.Value = 29, Right.Count = 18, Left.Count = 29
LastValue = 48, Top.Value = 29, Right.Count = 19, Left.Count = 29
LastValue = 49, Top.Value = 29, Right.Count = 20, Left.Count = 29
تتم إضافة العناصر المطلوبة دائما إلى الجانب الأيمن من الشجرة، بطبيعة الحال. عندما يصبح الجانب الأيمن أكبر من اليسار، يحدث Rotateleft. الدوار لا يحدث أبدا. يتم تحديد عقدة أعلى جديدة تقريبا في كل مرة تتضاعف الشجرة. العشوائية من قيمة الأولوية تقييدها قليلا، لذلك يذهب 0، 1، 4، 11، 29 في هذا المدى.
يركض تشغيل عشوائي شيء مثير للاهتمام:
TimeIt(50, RandomInsert)
LastValue = 0,748661640914465, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 0
LastValue = 0,669427539533669, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 1
RotateRight @value=0,669427539533669
LastValue = 0,318363281115127, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 2
RotateRight @value=0,669427539533669
LastValue = 0,33133987678743, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 3
RotateLeft @value=0,748661640914465
LastValue = 0,955126694382693, Top.Value = 0,955126694382693, Right.Count = 0, Left.Count = 4
RotateRight @value=0,669427539533669
RotateLeft @value=0,33133987678743
RotateLeft @value=0,318363281115127
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
LastValue = 0,641024029180884, Top.Value = 0,641024029180884, Right.Count = 3, Left.Count = 2
LastValue = 0,20709771951991, Top.Value = 0,641024029180884, Right.Count = 3, Left.Count = 3
LastValue = 0,830862050331599, Top.Value = 0,641024029180884, Right.Count = 4, Left.Count = 3
RotateRight @value=0,20709771951991
RotateRight @value=0,318363281115127
LastValue = 0,203250563798123, Top.Value = 0,641024029180884, Right.Count = 4, Left.Count = 4
RotateLeft @value=0,669427539533669
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
LastValue = 0,701743399585478, Top.Value = 0,641024029180884, Right.Count = 5, Left.Count = 4
RotateLeft @value=0,669427539533669
RotateRight @value=0,701743399585478
RotateLeft @value=0,641024029180884
LastValue = 0,675667521858433, Top.Value = 0,675667521858433, Right.Count = 4, Left.Count = 6
RotateLeft @value=0,33133987678743
RotateLeft @value=0,318363281115127
RotateLeft @value=0,203250563798123
LastValue = 0,531275219531392, Top.Value = 0,675667521858433, Right.Count = 4, Left.Count = 7
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
RotateLeft @value=0,701743399585478
LastValue = 0,704049674190604, Top.Value = 0,675667521858433, Right.Count = 5, Left.Count = 7
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
LastValue = 0,161392807104342, Top.Value = 0,161392807104342, Right.Count = 13, Left.Count = 0
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateLeft @value=0,161392807104342
LastValue = 0,167598206162266, Top.Value = 0,167598206162266, Right.Count = 13, Left.Count = 1
LastValue = 0,154996359793002, Top.Value = 0,167598206162266, Right.Count = 13, Left.Count = 2
RotateLeft @value=0,33133987678743
LastValue = 0,431767346538495, Top.Value = 0,167598206162266, Right.Count = 14, Left.Count = 2
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateLeft @value=0,167598206162266
LastValue = 0,173774613614089, Top.Value = 0,173774613614089, Right.Count = 14, Left.Count = 3
RotateRight @value=0,830862050331599
LastValue = 0,76559642412029, Top.Value = 0,173774613614089, Right.Count = 15, Left.Count = 3
RotateRight @value=0,76559642412029
RotateLeft @value=0,748661640914465
RotateRight @value=0,955126694382693
RotateLeft @value=0,704049674190604
RotateLeft @value=0,675667521858433
LastValue = 0,75742144871383, Top.Value = 0,173774613614089, Right.Count = 16, Left.Count = 3
LastValue = 0,346844367844446, Top.Value = 0,173774613614089, Right.Count = 17, Left.Count = 3
RotateRight @value=0,830862050331599
LastValue = 0,787565814232251, Top.Value = 0,173774613614089, Right.Count = 18, Left.Count = 3
LastValue = 0,734950566540915, Top.Value = 0,173774613614089, Right.Count = 19, Left.Count = 3
RotateLeft @value=0,20709771951991
RotateRight @value=0,318363281115127
RotateLeft @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
RotateLeft @value=0,173774613614089
LastValue = 0,236504829598826, Top.Value = 0,236504829598826, Right.Count = 17, Left.Count = 6
RotateLeft @value=0,830862050331599
RotateLeft @value=0,787565814232251
RotateLeft @value=0,76559642412029
RotateRight @value=0,955126694382693
LastValue = 0,895606500048007, Top.Value = 0,236504829598826, Right.Count = 18, Left.Count = 6
LastValue = 0,599106418713511, Top.Value = 0,236504829598826, Right.Count = 19, Left.Count = 6
LastValue = 0,8182332901369, Top.Value = 0,236504829598826, Right.Count = 20, Left.Count = 6
RotateRight @value=0,734950566540915
LastValue = 0,704216948572647, Top.Value = 0,236504829598826, Right.Count = 21, Left.Count = 6
RotateLeft @value=0,346844367844446
RotateLeft @value=0,33133987678743
RotateRight @value=0,431767346538495
RotateLeft @value=0,318363281115127
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
LastValue = 0,379157059536854, Top.Value = 0,236504829598826, Right.Count = 22, Left.Count = 6
RotateLeft @value=0,431767346538495
LastValue = 0,46832062046431, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 6
RotateRight @value=0,154996359793002
LastValue = 0,0999000217299443, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 7
RotateLeft @value=0,20709771951991
LastValue = 0,229543754006524, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 8
RotateRight @value=0,8182332901369
LastValue = 0,80358425984326, Top.Value = 0,236504829598826, Right.Count = 24, Left.Count = 8
RotateRight @value=0,318363281115127
LastValue = 0,259324726769386, Top.Value = 0,236504829598826, Right.Count = 25, Left.Count = 8
RotateRight @value=0,318363281115127
LastValue = 0,307835293145774, Top.Value = 0,236504829598826, Right.Count = 26, Left.Count = 8
RotateLeft @value=0,431767346538495
LastValue = 0,453910283024381, Top.Value = 0,236504829598826, Right.Count = 27, Left.Count = 8
RotateLeft @value=0,830862050331599
LastValue = 0,868997387527021, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 8
RotateLeft @value=0,20709771951991
RotateRight @value=0,229543754006524
RotateLeft @value=0,203250563798123
LastValue = 0,218358597354199, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 9
RotateRight @value=0,0999000217299443
RotateRight @value=0,161392807104342
LastValue = 0,0642934488431986, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 10
RotateRight @value=0,154996359793002
RotateLeft @value=0,0999000217299443
LastValue = 0,148295871982489, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 11
LastValue = 0,217621828065078, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 12
RotateRight @value=0,599106418713511
LastValue = 0,553135806020878, Top.Value = 0,236504829598826, Right.Count = 29, Left.Count = 12
LastValue = 0,982277666210326, Top.Value = 0,236504829598826, Right.Count = 30, Left.Count = 12
RotateRight @value=0,8182332901369
LastValue = 0,803671114520948, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 12
RotateRight @value=0,203250563798123
RotateRight @value=0,218358597354199
LastValue = 0,19310415405459, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 13
LastValue = 0,0133136604043253, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 14
RotateLeft @value=0,46832062046431
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
LastValue = 0,483394719419719, Top.Value = 0,236504829598826, Right.Count = 32, Left.Count = 14
RotateLeft @value=0,431767346538495
RotateRight @value=0,453910283024381
LastValue = 0,453370328738061, Top.Value = 0,236504829598826, Right.Count = 33, Left.Count = 14
LastValue = 0,762330518459124, Top.Value = 0,236504829598826, Right.Count = 34, Left.Count = 14
LastValue = 0,699010426969738, Top.Value = 0,236504829598826, Right.Count = 35, Left.Count = 14
تحدث التناوب ليس كثيرا لأن الشجرة غير متوازنة، ولكن بسبب الأولويات، والتي يتم تحديدها بشكل عشوائي. على سبيل المثال، نحصل على 4 تنازلات في الإدراج الثالث عشر. لدينا شجرة متوازنة في 5/7 (وهذا ما يرام)، ولكن الحصول على 13/0! يبدو أن استخدام الأولويات العشوائية يستحق تحقيق مزيد من التحقيق. على أي حال، من السهل أن نرى أن إدراجات عشوائية تسبب دورات أكثر بكثير، من الإدراجات المطلوبة.
أضفت حساب الانحراف المعياري، وقمت بتغيير الاختبار الخاص بك لتشغيلها بأولوية قصوى (للحد من الضوضاء قدر الإمكان). هذه هي النتائج:
Random Ordered
0,2835 (stddev 0,9946) 0,0891 (stddev 0,2372)
0,1230 (stddev 0,0086) 0,0780 (stddev 0,0031)
0,2498 (stddev 0,0662) 0,1694 (stddev 0,0145)
0,5136 (stddev 0,0441) 0,3550 (stddev 0,0658)
1,1704 (stddev 0,1072) 0,6632 (stddev 0,0856)
1,4672 (stddev 0,1090) 0,8343 (stddev 0,1047)
3,3330 (stddev 0,2041) 1,9272 (stddev 0,3456)
7,9822 (stddev 0,3906) 3,7871 (stddev 0,1459)
18,4300 (stddev 0,6112) 10,3233 (stddev 2,0247)
44,9500 (stddev 2,2935) 22,3870 (stddev 1,7157)
110,5275 (stddev 3,7129) 49,4085 (stddev 2,9595)
275,4345 (stddev 10,7154) 107,8442 (stddev 8,6200)
667,7310 (stddev 20,0729) 242,9779 (stddev 14,4033)
لقد قمت بتشغيل ملفات تعريف أخذ العينات وهنا النتائج (مقدار الأوقات التي كان فيها البرنامج في هذه الطريقة):
Method Random Ordered
HeapifyRight() 1.95 5.33
get_IsEmpty() 3.16 5.49
Make() 3.28 4.92
Insert() 16.01 14.45
HeapifyLeft() 2.20 0.00
الخلاصة: يحتوي العشوائي على توزيع معقول إلى حد ما بين الدوران الأيسر والأيمن، في حين أن الأمر لم يدور أبدا اليسار.
هنا هو برنامج "المعدل" المحسن:
static void Main(string[] args)
{
Thread.CurrentThread.Priority = ThreadPriority.Highest;
Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime;
List<String> rndTimes = new List<String>();
List<String> orderedTimes = new List<String>();
rndTimes.Add(TimeIt(50, RandomInsert));
rndTimes.Add(TimeIt(100, RandomInsert));
rndTimes.Add(TimeIt(200, RandomInsert));
rndTimes.Add(TimeIt(400, RandomInsert));
rndTimes.Add(TimeIt(800, RandomInsert));
rndTimes.Add(TimeIt(1000, RandomInsert));
rndTimes.Add(TimeIt(2000, RandomInsert));
rndTimes.Add(TimeIt(4000, RandomInsert));
rndTimes.Add(TimeIt(8000, RandomInsert));
rndTimes.Add(TimeIt(16000, RandomInsert));
rndTimes.Add(TimeIt(32000, RandomInsert));
rndTimes.Add(TimeIt(64000, RandomInsert));
rndTimes.Add(TimeIt(128000, RandomInsert));
orderedTimes.Add(TimeIt(50, OrderedInsert));
orderedTimes.Add(TimeIt(100, OrderedInsert));
orderedTimes.Add(TimeIt(200, OrderedInsert));
orderedTimes.Add(TimeIt(400, OrderedInsert));
orderedTimes.Add(TimeIt(800, OrderedInsert));
orderedTimes.Add(TimeIt(1000, OrderedInsert));
orderedTimes.Add(TimeIt(2000, OrderedInsert));
orderedTimes.Add(TimeIt(4000, OrderedInsert));
orderedTimes.Add(TimeIt(8000, OrderedInsert));
orderedTimes.Add(TimeIt(16000, OrderedInsert));
orderedTimes.Add(TimeIt(32000, OrderedInsert));
orderedTimes.Add(TimeIt(64000, OrderedInsert));
orderedTimes.Add(TimeIt(128000, OrderedInsert));
var result = string.Join("\n", (from s in rndTimes
join s2 in orderedTimes
on rndTimes.IndexOf(s) equals orderedTimes.IndexOf(s2)
select String.Format("{0} \t\t {1}", s, s2)).ToArray());
Console.WriteLine(result);
Console.WriteLine("Done");
Console.ReadLine();
}
static double StandardDeviation(List<double> doubleList)
{
double average = doubleList.Average();
double sumOfDerivation = 0;
foreach (double value in doubleList)
{
sumOfDerivation += (value) * (value);
}
double sumOfDerivationAverage = sumOfDerivation / doubleList.Count;
return Math.Sqrt(sumOfDerivationAverage - (average * average));
}
static String TimeIt(int insertCount, Action<int> f)
{
Console.WriteLine("TimeIt({0}, {1})", insertCount, f.Method.Name);
List<double> times = new List<double>();
for (int i = 0; i < ITERATION_COUNT; i++)
{
Stopwatch sw = Stopwatch.StartNew();
f(insertCount);
sw.Stop();
times.Add(sw.Elapsed.TotalMilliseconds);
}
return String.Format("{0:f4} (stddev {1:f4})", times.Average(), StandardDeviation(times));
}
نعم إنه عدد الدوران الذي يسبب الوقت الإضافي. إليك ما فعلته:
- إزالة خطوط التحقق من الأولوية في
HeapifyLeftوHeapifyRightلذلك يتم التناوب دائما. - وأضاف أ
Console.WriteLineبعد إذا فيRotateLeftوRotateRight. - وأضاف أ
Console.WriteLineفي الIsEmptyجزء منInsertطريقة لمعرفة ما يجري إدراجه. - ركض الاختبار مرة واحدة مع 5 قيم لكل منهما.
انتاج:
TimeIt(5, RandomInsert)
Inserting 0.593302943554382
Inserting 0.348900582338171
RotateRight
Inserting 0.75496212381635
RotateLeft
RotateLeft
Inserting 0.438848891499848
RotateRight
RotateLeft
RotateRight
Inserting 0.357057290783644
RotateLeft
RotateRight
TimeIt(5, OrderedInsert)
Inserting 0.150707998383189
Inserting 1.58281302712057
RotateLeft
Inserting 2.23192588297274
RotateLeft
Inserting 3.30518679009061
RotateLeft
Inserting 4.32788012657682
RotateLeft
النتيجة: 2 مرات أكبر عدد ممكن من الدوران على البيانات العشوائية.
أنت فقط ترى فرقا في حوالي 2x. ما لم تقلع في ضوء النهار من هذا الرمز، هذا في الأساس في الضوضاء. يمكن أن تحصل معظم البرامج المكتوبة بشكل جيد، وخاصة تلك التي تنطوي على هيكل البيانات، الحصول بسهولة أكبر مجال للتحسين من ذلك. هنا مثال.
أنا فقط ركضت الكود الخاص بك وأخذت بضع عدد قليل من stackshots. إليك ما رأيته:
إدراج عشوائي:
1 Insert:64 -> HeapifyLeft:81 -> RotateRight:150
1 Insert:64 -> Make:43 ->Treap:35
1 Insert:68 -> Make:43
مطلوب إدراج:
1 Insert:61
1 OrderedInsert:224
1 Insert:68 -> Make:43
1 Insert:68 -> HeapifyRight:90 -> RotateLeft:107
1 Insert:68
1 Insert:68 -> Insert:55 -> IsEmpty.get:51
هذا عددا صغيرا جدا من العينات، لكنه يقترح في حالة إدخال عشوائي يجعل (السطر 43) يستهلك جزء كبير من الوقت. هذا رمز:
private Treap<T> Make(Treap<T> left, T value, Treap<T> right, int priority)
{
return new Treap<T>(Comparer, left, value, right, priority);
}
ثم أخذت 20 Stackshots من رمز إدراج عشوائي للحصول على فكرة أفضل عما كان يفعل:
1 Insert:61
4 Insert:64
3 Insert:68
2 Insert:68 -> Make:43
1 Insert:64 -> Make:43
1 Insert:68 -> Insert:57 -> Make:48 -> Make:43
2 Insert:68 -> Insert:55
1 Insert:64 -> Insert:55
1 Insert:64 -> HeapifyLeft:81 -> RotateRight:150
1 Insert:64 -> Make:43 -> Treap:35
1 Insert:68 -> HeapifyRight:90 -> RotateLeft:107 -> IsEmpty.get:51
1 Insert:68 -> HeapifyRight:88
1 Insert:61 -> AnonymousMethod:214
هذا يكشف عن بعض المعلومات.
تم إنفاق 25٪ من الوقت في الكتابة: 43 أو Callees.
تم إنفاق 15٪ من الوقت في هذا الخط، وليس في روتين معترف به، وبعبارة أخرى new صنع عقدة جديدة.
يتم إنفاق 90٪ من الزمن في خطوط إدراج: 64 و 68 (التي تصنعها وأرسمها.
تم إنفاق 10٪ من الوقت في rotateleft واليمين.
ينفق 15٪ من الزمن في أقصى أو كوارها.
لقد قمت أيضا بكمية عادلة من خطوة واحدة (على مستوى المصدر)، وجاءت إلى الشك في ذلك، نظرا لأن الشجرة غير قابلة للتغيير، فإنها تنفق الكثير من الوقت في صنع العقد الجديدة لأنها لا ترغب في تغيير تلك القديمة. ثم القديمة هي القمامة التي تم جمعها لأن لا أحد يشير إليهم بعد الآن.
هذا يجب أن يكون غير فعال.
ما زلت لا أجيب على سؤالك في سبب إدراج الأرقام المطلوبة أسرع من الأرقام التي تم إنشاؤها عشوائيا، لكنها لا تفاجئني حقا، لأن الشجرة غير قابلة للتغيير.
لا أعتقد أنه يمكنك أن تتوقع أي منطق الأداء حول خوارزميات الأشجار بتحمل بسهولة أشجار ثابتة، لأن أدنى تغيير في أعماق الشجرة يسبب إعادة بنائه في طريقه إلى الخارج، بتكلفة عالية في newجمع وقمامة القمامة.
ggug. صحيح. ومع ذلك فهناك قليلا قليلا قليلا لذلك. أنا لا أقول أنه أكبر عامل في هذه الحالة - ومع ذلك، فمن الصعب فعل أي شيء حيال ذلك.
للحصول على إدخال مرتبة، من المرجح أن تلمس البحث العقد الساخنة في ذاكرة التخزين المؤقت. (هذا صحيح بشكل عام للأشجار المتوازنة مثل أشجار AVL والأشجار الحمراء السوداء، أشجار B، إلخ)
نظرا لأن إدراجها تبدأ بطريقة بحث، فإن هذا له تأثير على أداء إدراج / حذف كذلك.
مرة أخرى، أنا لا أدعي أنه هو أهم عامل في كل الحالات. ومع ذلك، فمن المحتمل أن ينتج عنه مدخلات مرتبة أسرع دائما بشكل أسرع من تلك العشوائية في هياكل البيانات هذه.
أرونوت لقد قام بعمل لائق حقًا في شرح هذا.
بالنسبة لهاتين الحالتين الخاصتين، أجد أنه من الأسهل فهمهما من حيث أطوال مسار الإدراج.
بالنسبة للإدخال العشوائي، ينتقل مسار الإدراج الخاص بك إلى إحدى الأوراق ويكون طول المسار - وبالتالي عدد الدورات - محددًا بارتفاع الشجرة.
في الحالة التي تم فرزها، يمكنك المشي على العمود الفقري الأيمن من المداس والحد هو طول العمود الفقري، وهو أقل من أو يساوي الارتفاع.
نظرًا لأنك تقوم بتدوير العقد على طول مسار الإدراج ويكون مسار الإدراج الخاص بك هو العمود الفقري في هذه الحالة، فإن هذه التدويرات ستؤدي دائمًا إلى تقصير العمود الفقري (مما سيؤدي إلى مسار إدراج أقصر في عملية الإدراج التالية، نظرًا لأن مسار الإدراج هو العمود الفقري فقط وما إلى ذلك). )
يحرر:بالنسبة للحالة العشوائية، يكون مسار الإدراج أطول بمقدار 1.75 مرة.
جرب هذا: قاعدة البيانات على Treap.
