لماذا فرز سريع هو أكثر شعبية من الرقم الأساسي-نوع ؟

Question

لماذا فرز سريع(أو introsort) ، أو أي مقارنة على أساس خوارزمية الفرز هو أكثر شيوعا من الرقم الأساسي-نوع ؟ خاصة لفرز الأرقام.

Radix-النوع لا مقارنة على أساس ، ومن ثم قد يكون أسرع مما O(nlogn).في الواقع, فمن O(kن) ، حيث k هو عدد البتات المستخدمة لتمثيل كل بند.و الذاكرة العلوية ليست حرجة ، حيث يمكنك اختيار عدد من الدلاء إلى استخدام الذاكرة المطلوبة قد تكون أقل من mergesort متطلبات.

لا مع التخزين المؤقت ؟ أو ربما الوصول العشوائي بايت من الاعداد الصحيحه في المصفوفة ؟

Answer 1

تتبادر إلى ذهني حجتين:

1. Quicksort/introsort أكثر مرونة:

   تعمل Quicksort و introsort بشكل جيد مع جميع أنواع البيانات. كل ما تحتاجه للفرز هو إمكانية مقارنة العناصر. هذا تافهة بالأرقام ولكن يمكنك فرز البيانات الأخرى أيضًا.

   فرز Radix من ناحية أخرى فقط يفرز الأشياء عن طريق تمثيلها الثنائي. لا يقارن العناصر مع بعضها البعض.

2. يحتاج Radix إلى المزيد من الذاكرة.

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

   إذا كنت أتذكر الحق في مكان وجود خوارزمية راديكس-سورت على الورق على الرغم من.

Answer 2

إحدى الإجابة الواضحة هي أنه يمكنك فرز أنواع تعسفية باستخدام Quicksort (أي أي شيء قابلي للمقارنة) ، بينما تقتصر على الأرقام فقط مع Radix. و IMO Quicksort هو أكثر بكثير.

Answer 3

يعد نوع Radix أبطأ لحالات استخدام العالم الحقيقي (معظمها).

أحد الأسباب هو تعقيد الخوارزمية:

إذا كانت العناصر فريدة من نوعها ، k> = log (n). حتى مع العناصر المكررة ، فإن مجموعة المشكلات التي تكون فيها K <log (n) صغيرة.

آخر هو التنفيذ:

إن متطلبات الذاكرة الإضافية (التي تكون ذاتية عيب) ، تؤثر على أداء ذاكرة التخزين المؤقت سلبًا.

أعتقد أنه من الآمن القول إن العديد من المكتبات ، مثل المكتبة القياسية ، تستخدم Quicksort لأنها تعمل بشكل أفضل في معظم الحالات. لا أعتقد أن "التنفيذ الصعب" أو "أقل بديهية" من العوامل الرئيسية.

Answer 4

كما ذكر في ويكيبيديا

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

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

العامل الحاسم هو كيف يتم توزيع المفاتيح.أفضل حالة radix النوع هو أنها تؤخذ باعتبارها متتالية أنماط بت.وهذا سيجعل مفاتيح قصيرة كما أنها يمكن أن تكون لا تزال على افتراض أنها متميزة.وهذا يجعل radix نوع O(n·log(n)) ، ولكن المقارنة على أساس النوع لن تكون فعالة ، كما المقارنات لن تكون ثابتة تحت هذا الافتراض.إذا نحن بدلا من ذلك نفترض أن المفاتيح هي بت أنماط من طول k·log(n) عن ثابت k > 1 و 2 أساسي سجل وأنهم موحد عشوائية ، ثم radix النوع سوف يكون لا يزال O(n·log(n)) ، ولكن ذلك سوف المقارنة على أساس أنواع ، "إضافية" طول يجعل حتى مفاتيح متتالية في فرز النتيجة تختلف يكفي أن المقارنات وقت ثابت في المتوسط. إن مفاتيح أطول من O(log(n)) ، ولكن عشوائية ، ثم radix النوع سوف تكون أقل شأنا. هناك العديد من الافتراضات الأخرى التي يمكن أن تكون مصنوعة وكذلك معظم تتطلب دراسة متأنية لجعل الصحيح المقارنة.

Answer 5

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

... حقيقة أن خوارزميات الفرز الافتراضية للأرقام يتم تنفيذها باستخدام QuickSort. خاصة التطبيقات في المكتبات ...

Quicksort هو الخيار "الآمن". يعد وقت التشغيل المحتمل لنوع Radix استنادًا إلى نوع العد جذابًا للغاية ، نعم ، لكن نوع Radix محتمل للأداء بشكل سيئ على مجموعات البيانات الضارة/المؤسفة. إذا اقترب عدد أرقام المفاتيح التي يتم فرزها من عدد المفاتيح التي يتم فرزها ، فإن Radix Sort يؤدي على N^2 إلى جانب تعقيد الفضاء غير المهم من أرقام المفاتيح التي يجري فرزها.
Mergesort جذاب لأن سلوكها ، في بعض النواحي ، تشبه إلى مقطع سريع يختار محورًا مثاليًا في كل فرصة (الوسيط). ومع ذلك ، فإنه يأتي مع تعقيد الفضاء الملموس. ليس من المميز للبيانات الخبيثة/المؤسفة مثل Radix ، ولكنه لا يوفر أيضًا وقت التشغيل المحتمل الجذاب. يعمل Quicksort الأساسي بشكل جيد للغاية على معظم مجموعات البيانات باستثناء ما يقرب من (أو تمامًا) المصنفة ، ويأتي مع تعقيد مساحة صغيرة.
يتم التعامل بسهولة مع ضعف Quicksort من خلال تحويله إلى Quicksort العشوائي. يتم حل ضعف Radix Sort عن طريق وضع قيود على المفاتيح التي يتم فرزها ، والتي من شأنها أن تحد بطبيعتها لمستخدمي المكتبة. يعد Quicksort أكثر أداءً من دمج مجموعات البيانات الصغيرة ، ويؤدي بشكل معقول عندما يكون الدمج أسرع.
عند تنفيذ مكتبة ، تريد أن تجعلها مفيدة بشكل عام. خذ هذه الأمثلة ، تطبيق ويب وجهاز صغير مع متحكم مقيد للغاية. تحتاج تطبيقات الويب إلى التعامل مع البيانات الخبيثة بشكل منتظم ، وكذلك لديها مجموعة واسعة من الاحتياجات. من غير المرجح أن تكون المكتبة ذات القيود المسبقة للشرافين مفيدة. في حالة متحكم ، قد يكون محدودًا بشكل مقيد على الفضاء وغير قادر على التخلي عن أدنى عدد حيث يمكن حفظ المرء. يوفر Quicksort المساحة ، وسيكمل أبطأ فقط من خلال مضاعف ثابت إذا نشأ الموقف بأنه أبطأ.
باختصار -
1.) غالباً ما يتم ترميز المكتبات بأكبر قدر ممكن من الاستخدام العام
2.) الأداء الجيد في كل مكان مقبول ، خاصة إذا كان في كثير من الحالات ، أفضل أداء
3.) الفضاء ليس دائمًا مشكلة أساسية ، ولكن عندما يكون الأمر كذلك ، فغالبًا ما يكون ذلك بشكل صريح

Answer 6

كفاءة Radix Sort = O (CN) حيث C = أكبر عدد من الأرقام بين مجموعة مفاتيح الإدخال. n = عدد المفاتيح في مجموعة مفاتيح الإدخال.

أفضل حالة من النوع السريع = o (n. log n) حيث n = عدد المفاتيح في مجموعة مفاتيح الإدخال.

افترض أن يتم فرز 16 رقمًا بـ 6 أرقام لكل منها:

نوع Radix = 16 * 6 = 96 وحدة زمنية. فرز سريع = 16 * 4 = 64 وحدات زمنية.

الدرس: عندما يكون "C" أقل ، يفوز Radix. عندما يكون مرتفعا ، فإنه يخسر. النوع السريع مستقل عن عدد الأرقام في المفتاح وهذا يجعله أفضل إلى حد ما وأكثر قبولًا عمليًا