لماذا استخدام البحث الثنائية إذا كان هناك الثلاثي البحث ؟

Question

سمعت مؤخرا عن الثلاثي البحث الذي قمنا بتقسيم مجموعة إلى 3 أجزاء و قارن.هنا سوف يكون هناك اثنين من المقارنات ولكنه يقلل من مجموعة n/3.لماذا لا يستخدم الناس هذا القدر ؟

Answer 1

في الواقع ، يستخدم الناس أشجار K-ary من أجل k التعسفي.

هذا ، ومع ذلك ، مفاضلة.

للعثور على عنصر في شجرة k-ary ، تحتاج إلى حول عمليات K*ln (n)/ln (k) (تذكر صيغة تغيير القاعدة). كلما زاد عدد العمليات الإجمالية التي تحتاجها.

الامتداد المنطقي لما تقوله هو "لماذا لا يستخدم الناس شجرة n لعناصر البيانات n؟". والتي ، بالطبع ، ستكون صفيف.

Answer 2

سيظل البحث الثلاثي يعطيك نفس التعقيد غير المقارب س (سجل ن) وقت البحث ، ويضيف التعقيد إلى التنفيذ.

يمكن قول نفس الحجة عن سبب عدم رغبتك في البحث عن رباعي أو أي ترتيب آخر.

Answer 3

البحث عن 1 مليار دولار (الولايات المتحدة مليار دولار - 1,000,000,000) فرز العناصر سوف تأخذ في المتوسط حوالي 15 يقارن مع الثنائية والبحث عن 9 يقارن مع الثلاثي البحث - ليس ميزة كبيرة.و لاحظ أن كل 'الثلاثي مقارنة' قد تنطوي على 2 الفعلية والمقارنات.

Answer 4

رائع. أظن أن الإجابات التي تم التصويت عليها تفتقد القارب على هذا واحد ، على ما أعتقد.

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

يمكن أن يكون لأشجار B فروع متعددة في كل عقدة ؛ Order-3 B-tree هو المنطق الثلاثية. ستأخذ كل خطوة لأسفل الشجرة مقارنتين بدلاً من إجراء ، وربما سيؤدي ذلك إلى أن يكون أبطأ في وقت وحدة المعالجة المركزية.

B Trees ، ومع ذلك ، شائعة جدا. إذا افترضت أنه سيتم تخزين كل عقدة في الشجرة في مكان ما على القرص ، فستقضي معظم وقتك في القراءة من القرص ... ولن تكون وحدة المعالجة المركزية عنق الزجاجة ، لكن القرص سيكون. لذلك تأخذ شجرة B مع 100000 طفل لكل عقدة ، أو أي شيء آخر سوف بالكاد تناسب كتلة واحدة من الذاكرة. نادراً ما تكون الأشجار B ذات هذا النوع من العوامل المتفرعة أكثر من ثلاث عقد ، ولن يكون لديك سوى ثلاث قراءات قرص - ثلاث محطات في عنق الزجاجة - للبحث في مجموعة بيانات هائلة وفخمة.

المراجعة:

• الأشجار الثلاثية لا تدعمها الأجهزة ، لذلك فهي تعمل بسرعة أقل.
• B-amp مع أوامر الكثير ، أعلى بكثير من 3 شائع في تحسين القرص لمجموعات البيانات الكبيرة ؛ بمجرد تجاوز 2 ، اذهب إلى أعلى من 3.

Answer 5

الطريقة الوحيدة الثلاثي البحث يمكن أن يكون أسرع من البحث الثنائية 3-طريقة التقسيم يمكن أن يتم تحديد أقل من حوالي 1.55 أضعاف تكلفة 2-طريقة المقارنة.إذا كان يتم تخزين العناصر في مجموعة فرزها ، 3-طريقة تحديد في المتوسط يكون 1.66 مرات مكلفة 2-طريقة التصميم.إذا كان يتم تخزين المعلومات في شجرة ، ومع ذلك ، فإن تكلفة جلب المعلومات هو ارتفاع نسبة إلى تكلفة في الواقع ومقارنة ذاكرة التخزين المؤقت محلة يعني تكلفة عشوائيا جلب زوج من البيانات ذات الصلة ليست أسوأ بكثير من تكلفة جلب واحد مسند, الثلاثي أو n-طريقة شجرة قد تحسين الكفاءة إلى حد كبير.

Answer 6

ما الذي يجعلك تعتقد الثلاثي البحث يجب أن تكون أسرع ؟

متوسط عدد المقارنات:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

أسوأ عدد من المقارنات:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

لذا يبدو الثلاثي البحث هو أسوأ من ذلك.

Answer 7

لاحظ أيضًا أن هذا التسلسل يعتمد على البحث الخطي إذا ذهبنا

Binary search
Ternary search
...
...
n-ary search ≡ linear search

لذلك ، في بحث n-ary ، سيكون لدينا "مقارن واحد فقط" والذي قد يستغرق الأمر مقارنات فعلية.

Answer 8

يعد البحث "Terinary" (Ternary؟) أكثر كفاءة في أفضل حالة ، والذي يتضمن البحث عن العنصر الأول (أو ربما الأخير ، اعتمادًا على المقارنة التي تقوم بها أولاً). بالنسبة للعناصر أبعد من النهاية ، تقوم بفحصها أولاً ، في حين أن مقارنتين ستضيق الصفيف بمقدار 2/3 في كل مرة ، فإن نفس المقارنتين مع البحث الثنائي من شأنه أن يضيق مساحة البحث بمقدار 3/4.

أضف إلى ذلك ، البحث الثنائي أبسط. يمكنك فقط المقارنة والحصول على نصف أو آخر ، بدلاً من المقارنة ، إذا كان أقل من الحصول على الثلث الأول ، أو قارن ، إذا كان أقل من الحصول على الثلث الثاني ، آخر الحصول على الثلث الأخير.

Answer 9

يمكن استخدام البحث الثلاثية بفعالية في البنية المتوازية - FPGAs و ASICs. على سبيل المثال ، إذا كانت ذاكرة FPGA الداخلية المطلوبة للبحث أقل من نصف مورد FPGA ، فيمكنك إنشاء كتلة ذاكرة مكررة. هذا من شأنه أن يسمح في وقت واحد بالوصول إلى عناوين ذاكرة مختلفة وإجراء جميع المقارنات في دورة ساعة واحدة. هذا هو أحد الأسباب التي تجعل FPGA 100 ميجا هرتز في بعض الأحيان يتفوق على وحدة المعالجة المركزية 4 جيجا هرتز :)

Answer 10

هنا بعض الأدلة التجريبية العشوائية التي لم أفحصها على الإطلاق يوضح أنه أبطأ من البحث الثنائي.

Answer 11

تقريبا كل الكتب والمواقع على أشجار البحث الثنائية لا حقا الحديث عن الأشجار الثنائية!أنها تظهر لك الثلاثي البحث الأشجار!صحيح الأشجار الثنائية تخزين البيانات في أوراق لا العقد الداخلية (باستثناء مفاتيح التنقل).البعض يطلق هذه أوراق الأشجار و جعل التمييز بين عقدة الأشجار يظهر في الكتب المدرسية:

ج.Nievergelt, C.-K.ونغ:الحدود العليا إجمالي طول المسار من الأشجار الثنائية ، مجلة ACM 20 (1973) 1-6.

التالية حول هذا من بيتر النحاس كتاب هياكل البيانات.

2.1 نموذجين من أشجار البحث

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

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

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

2. تأخذ اليسار فرع إذا كان الاستعلام الرئيسية هو أصغر من العقدة الرئيسية ؛ تأخذ الحق فرع إذا كان الاستعلام الرئيسية أكبر من العقدة الرئيسية ؛ و تأخذ الكائن الواردة في العقدة إذا كانت متساوية.

هذه نقطة ثانوية لديها عدد من النتائج:

{ في النموذج 1 الكامنة وراء الشجرة هي شجرة ثنائية ، بينما في نموذج 2 كل شجرة عقدة حقا الثلاثي عقدة خاصة الأوسط الجار.

{ في نموذج 1 كل الداخلية عقدة اليسار واليمين الشجرة (كل محتمل ورقة عقدة من شجرة) ، بينما في النموذج 2-يجب أن تسمح ناقصة العقد ، حيث اليسار أو اليمين الشجرة قد يكون في عداد المفقودين ، مقارنة كائن الرئيسية مضمونة الوجود.

لذا بنية شجرة البحث من نموذج 1 هو أكثر انتظاما من تلك الشجرة نموذج 2;هذا هو على الأقل من أجل تنفيذ ميزة واضحة.

{ في نموذج 1 ، تعبر الداخلية عقدة يتطلب واحد فقط على سبيل المقارنة ، بينما في النموذج 2-نحن بحاجة إلى اثنين من المقارنات للتحقق من ثلاثة الاحتمالات.

في الواقع, الأشجار من نفس الارتفاع في النماذج 1 و 2 تحتوي على معظم ما يقرب من نفس العدد من الكائنات ، ولكن يحتاج المرء مرتين العديد من المقارنات في نموذج 2 للوصول إلى أعمق الأشياء من الشجرة.بالطبع, في نموذج 2 ، هناك أيضا بعض الكائنات التي يتم التوصل إليها كثيرا في وقت سابق ؛ الكائن في جذر وجدت مع اثنين فقط من المقارنات, ولكن تقريبا جميع الكائنات على أو بالقرب من أعمق المستوى.

مبرهنه.شجرة من ارتفاع h نموذج 1 يحتوي على أكثر من 2^ح الكائنات.شجرة من ارتفاع h و نموذج 2 يحتوي على أكثر من 2^h+1 − 1 الكائنات.

ويعتبر هذا بسهولة لأن الشجرة من ارتفاع h قد اليسار واليمين الأشجار الفرعية a شجرة ارتفاعها في معظم h − 1 لكل منهما ، في نموذج 2 إضافية واحدة الكائن بين لهم.

{ في نموذج 1, مفاتيح الداخلية في العقد إلا على المقارنات قد الظهور في الأوراق تحديد الكائنات.في نموذج 2 كل يظهر مفتاح مرة واحدة فقط ، جنبا إلى جنب مع موضوعها.

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

نموذج 2 أصبح المفضل المدرسي الإصدار لأنه في معظم الكتب المدرسية التمييز بين وجوه رئيسية لم يتم:المفتاح هو كائن.ثم يصبح غير طبيعي مكررة الرئيسية في هيكل شجرة.ولكن في جميع تطبيقات حقيقية التمييز بين مفتاح كائن مهم جدا.واحد تقريبا لم يرغب في الحفاظ على المسار من مجرد مجموعة من الأرقام ؛ الأرقام عادة ما ترتبط مع بعض مزيد من المعلومات ، والتي في كثير من الأحيان الكثير أكبر من المفتاح نفسه.

Answer 12

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

Answer 13

من الناحية النظرية الحد الأدنى k/ln(k) يتحقق في ه ومنذ أن اقترب 3 من ه من 2 يتطلب مقارنات أقل. يمكنك التحقق من ذلك 3/ln(3) = 2.73.. و 2/ln(2) = 2.88.. السبب في أن البحث الثنائي قد يكون أسرع هو أن الكود الخاص به سيكون له فروع أقل وسيتم تشغيله بشكل أسرع على وحدات المعالجة المركزية الحديثة.

Answer 14

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

Answer 15

على الرغم من أنك تحصل على نفس التعقيد الكبير (LN N) في كل من أشجار البحث ، إلا أن الفرق في الثوابت. يجب عليك القيام بمزيد من المقارنات لشجرة البحث الثلاثية في كل مستوى. لذا فإن الفرق يتلخص في K/LN (K) لشجرة البحث K-ary. هذا له قيمة أدنى عند E = 2.7 و K = 2 يوفر النتيجة المثلى.