خوارزمية تجزئة سريعة لرسم الخرائط / تحديد مجموعة من العوامات على مجموعة صغيرة من العوامات المصنفة

Question

مع طلبي ، لدي

• المجموعة س:الآلاف من أرقام الفاصلة العائمة مع نطاق القيمة [0 ، 1] ، غير مرتبة.
• جمع ذ:11 عوامات تتراوح بين [0 ، 1] ، مرتبة.
• حجم س معروف.فليكن ل.

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

مثال لجعله أكثر وضوحا قليلا,

• Y = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
• X = [0.678, 0.124, ..., 1.0, ., 0.013, 0.475]

أريد أن يكون إخراج الخوارزمية مؤشرات تستند إلى 0 مثل هذه:

• H(Y[0]) = H(0.678) = 6
• H(Y[1]) = H(0.124) = 1
• H(Y[n-2]) = H(0.013) = 0
• H(Y[n-1]) = H(0.475) = 4

محاولات

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

ومع ذلك ، فإن الأداء ليست جيدة بما فيه الكفاية لطلبي.يحدث هذا التكميم في مؤشر ترابط في الوقت الفعلي بحيث يكون الحساب البطيء غير مرغوب فيه.

السؤال

ما هي أفضل طريقة لهذا النوع من التجزئة / تكميم?لا يتم فرز س.

شكراً!

Answer 1

خذ س ، مضروبا في القول 10 ، 000 ، تقريب وصولا الى أقرب عدد صحيح.في عادي ج ، ض = (كثافة العمليات) (س مرات 10000.0).

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

ونتيجة لذلك ، يمكنك الحصول على القيمة الصحيحة ربما في 9 ، 980 من 10 ، 000 القيم ، ومن ثم استخدام أي خوارزمية بطيئة لديك لقيم 1 في 500 المتبقية.

ملاحظة.سيتم استخدام نفس حجم الجدول لأرقام الدقة المزدوجة.مهما كان حجم الجدول ، سيكون هناك عدد قليل فقط من القيم س التي لا يمكن تعيينها بشكل صحيح باستخدام هذه الطريقة ، ربما 10 أو 20.إذا كنت تأخذ جدولا بحجم 10000 ، فسيتم تعيين 99.8 ٪ أو 99.9 ٪ بشكل صحيح ، ويحتاج 0.1 ٪ أو 0.2 ٪ إلى خوارزمية بطيئة.نفس الشيء بالضبط يحدث مع ضعف.هل يمكن استخدام 1000 إدخالات ، ثم 10 أو 20 منها الفشل سيكون 1 ٪ أو 2٪.

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