كيفية البحث عن النطاق من مجموعة النطاقات المتجاورة لرقم معين
-
20-12-2019 - |
سؤال
بكل بساطة، هذا ما أحاول القيام به:
لدي مجموعة من Range
كائنات متجاورة (غير متداخلة، مع عدم وجود فجوات بينها)، يحتوي كل منها على أ start
و end
int، وإشارة إلى كائن آخر obj
.هذه النطاقات ليست ذات حجم ثابت (الأول يمكن أن يكون 1-49، والثاني 50-221، وما إلى ذلك).يمكن أن تنمو هذه المجموعة لتصبح كبيرة جدًا.
آمل أن أجد طريقة للبحث عن النطاق (أو بشكل أكثر تحديدًا، الكائن الذي يشير إليه) الذي يتضمن رقمًا محددًا دون الحاجة إلى التكرار على المجموعة بأكملها للتحقق من كل نطاق لمعرفة ما إذا كان يتضمن الرقم.سيتم إجراء عمليات البحث هذه بشكل متكرر، لذا فإن السرعة/الأداء هو المفتاح.
هل يعرف أحد خوارزمية/معادلة قد تساعدني هنا؟أنا أكتب بلغة جافا.يمكنني تقديم المزيد من التفاصيل إذا لزم الأمر، لكنني اعتقدت أنني سأحاول إبقاء الأمر بسيطًا.
شكرًا.
المحلول
إذا كان يبدو أنك تريد استخدام أ TreeMap
, ، حيث يكون المفتاح في أسفل النطاق، وتكون القيمة هي Range
هدف.
ثم لتحديد النطاق الصحيح، فقط استخدم floorEntry()
طريقة للحصول بسرعة على الأقرب (أقل أو يساوي) Range
, ، والتي يجب أن تحتوي على المفتاح، كما يلي:
TreeMap<Integer, Range> map = new TreeMap<>();
map.put(1, new Range(1, 10));
map.put(11, new Range(11, 30));
map.put(31, new Range(31, 100));
// int key = 0; // null
// int key = 1; // Range [start=1, end=10]
// int key = 11; // Range [start=11, end=30]
// int key = 21; // Range [start=11, end=30]
// int key = 31; // Range [start=31, end=100]
// int key = 41; // Range [start=31, end=100]
int key = 101; // Range [start=31, end=100]
// etc.
Range r = null;
Map.Entry<Integer, Range> m = map.floorEntry(key);
if (m != null) {
r = m.getValue();
}
System.out.println(r);
نظرًا لأن الشجرة يتم فرزها دائمًا حسب الترتيب الطبيعي لحدود النطاق السفلي، فإن جميع عمليات البحث الخاصة بك ستكون في أسوأ الأحوال O(log(n)).
ستحتاج إلى إضافة بعض التحقق من السلامة عندما يكون مفتاحك خارج الحدود تمامًا (على سبيل المثال، عندما يكون المفتاح خارج نهاية الخريطة، فإنه يُرجع آخر Range
في الخريطة)، ولكن هذا من شأنه أن يعطيك فكرة عن كيفية المتابعة.
نصائح أخرى
بافتراض أن عمليات البحث ذات أهمية قصوى، ويمكنك توفير ذاكرة O(N) ووقت المعالجة المسبقة تقريبًا O(N^2)، ستكون الخوارزمية كما يلي:
- تقديم فصل دراسي
ObjectsInRange
, ، والذي يحتوي على:بداية النطاق (int startOfRange
) ومجموعة من الكائنات (Set<Object> objects
) - أعرض
ArrayList<ObjectsInRange> oir
, ، والتي سوف تحتوي علىObjectsInRange
مرتبة حسبstartOfRange
- لكل
Range r
, ، تأكد من وجودهاObjectsInRange
(دعونا ندعو لهمa
وb
) مثل ذلكa.startOfRange = r.start
وb.startOfRange = b.end
.ثم للجميعObjectsInRange x
بينa
, ، وحتى (ولكن ليس بما في ذلك)b
, ، يضيفr.obj
لهمx.objects
تعيين
البحث إذن هو كما يلي:
- لعدد صحيح
x
, ، تجد مثل هذاi
الذي - التيoir[i].startOfRange <= x
وoir[i+1].startOfRange > x
- ملحوظة:
i
يمكن العثور عليها مع التنصيف في وقت O (log N)! - الأشياء الخاصة بك هي
oir[i].objects
إذا كانت المجموعة مرتبة، فيمكنك إجراء بحث ثنائي للعثور على النطاق الصحيح في وقت O(log(n))).إنها ليست فعالة مثل التجزئة للمجموعات الكبيرة جدًا، ولكن إذا كان لديك أقل من 1000 نطاق أو نحو ذلك، فقد تكون أسرع (لأنها أبسط).