كيفية البحث عن النطاق من مجموعة النطاقات المتجاورة لرقم معين

Question

بكل بساطة، هذا ما أحاول القيام به:

لدي مجموعة من Range كائنات متجاورة (غير متداخلة، مع عدم وجود فجوات بينها)، يحتوي كل منها على أ start و end int، وإشارة إلى كائن آخر obj.هذه النطاقات ليست ذات حجم ثابت (الأول يمكن أن يكون 1-49، والثاني 50-221، وما إلى ذلك).يمكن أن تنمو هذه المجموعة لتصبح كبيرة جدًا.

آمل أن أجد طريقة للبحث عن النطاق (أو بشكل أكثر تحديدًا، الكائن الذي يشير إليه) الذي يتضمن رقمًا محددًا دون الحاجة إلى التكرار على المجموعة بأكملها للتحقق من كل نطاق لمعرفة ما إذا كان يتضمن الرقم.سيتم إجراء عمليات البحث هذه بشكل متكرر، لذا فإن السرعة/الأداء هو المفتاح.

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

شكرًا.

Answer 1

إذا كان يبدو أنك تريد استخدام أ 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 في الخريطة)، ولكن هذا من شأنه أن يعطيك فكرة عن كيفية المتابعة.

Answer 2

بافتراض أن عمليات البحث ذات أهمية قصوى، ويمكنك توفير ذاكرة 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

Answer 3

إذا كانت المجموعة مرتبة، فيمكنك إجراء بحث ثنائي للعثور على النطاق الصحيح في وقت O(log(n))).إنها ليست فعالة مثل التجزئة للمجموعات الكبيرة جدًا، ولكن إذا كان لديك أقل من 1000 نطاق أو نحو ذلك، فقد تكون أسرع (لأنها أبسط).