خوارزمية تقاطع النطاق أفضل من O(n)؟

Question

يعد تقاطع النطاق مشكلة بسيطة ولكنها ليست تافهة.

وقد تم الرد عليه مرتين بالفعل:

• البحث عن تقاطع نطاق الأرقام
• مقارنة النطاقات الزمنية

الحل الأول هو O(n) والحل الثاني لقاعدة البيانات (وهو أقل من O(n) بالطبع).

لدي نفس المشكلة، ولكن بالنسبة لـ n كبير وأنا لست ضمن قاعدة بيانات.

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

إذًا ما هي بنية البيانات التي ستقوم بتخزين مجموعة النطاقات فيها، بحيث تكون تكلفة البحث في نطاق أقل من O(n)؟(رصيد إضافي لاستخدام المكتبات المتاحة لجافا)

يحرر:

أريد الحصول على مجموعة فرعية من جميع النطاقات المتقاطعة، مما يعني أن نطاق البحث يمكن أن يتقاطع مع نطاقات متعددة.

الطريقة التي يجب أن تكون أقل من O(n) في Java هي:

public class RangeSet {
    ....
    public Set<Range> intersects(Range range);
    ....
}

حيث أن Range هو مجرد فئة تحتوي على زوج من البداية والنهاية.

هذا ليس سؤالاً مستحيلاً، لدي الحل بالفعل، أردت فقط معرفة ما إذا كانت هناك طريقة أكثر قياسية/أبسط للقيام بذلك

Answer 1

النهج القياسي هو استخدام شجرة الفاصل.

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

الحل البسيط هو زيارة كل فاصل زمني واختبار ما إذا كان يتقاطع مع النقطة أو الفاصل الزمني المحدد، الأمر الذي يتطلب وقت O(n)، حيث n هو عدد الفواصل الزمنية في المجموعة.نظرًا لأن الاستعلام قد يُرجع كافة الفواصل الزمنية، على سبيل المثال، إذا كان الاستعلام عبارة عن فاصل زمني كبير يتقاطع مع جميع الفواصل الزمنية في المجموعة، فهذا هو الأمثل من الناحية التقاربية؛ومع ذلك، يمكننا أن نفعل ما هو أفضل من خلال النظر في الخوارزميات الحساسة للمخرجات، حيث يتم التعبير عن وقت التشغيل من حيث م، وعدد الفواصل الزمنية التي ينتجها الاستعلام.تحتوي الأشجار الفاصلة على وقت استعلام قدره O(log n + m) ووقت إنشاء أولي قدره O(n log n)، مع قصر استهلاك الذاكرة على O(n).بعد الإنشاء، قد تكون أشجار الفواصل ديناميكية، مما يسمح بالإدراج والحذف الفعالين للفاصل الزمني في O(log n).إذا كانت نقاط نهاية الفواصل الزمنية ضمن نطاق عدد صحيح صغير (على سبيل المثال، في النطاق [1،...,O(n)])، توجد هياكل بيانات أسرع[1] مع وقت المعالجة المسبقة O(n) ووقت الاستعلام O( 1+m) للإبلاغ عن فترات زمنية تحتوي على نقطة استعلام معينة.

Answer 2

يحرر:يبدو أن هذا الحل أكثر أو أقل شجرة الفاصل.يمكن العثور على تطبيق أكثر اكتمالاً لشجرة الفاصل الزمني هنا.

class TreeNode
{
public:
    long pivot;
    List<Range> leaves;  //Any ranges that intersect the pivot
    TreeNode left;        //Tree nodes that fall to the left of the pivot
    TreeNode right;       //Tree nodes that fall to the right of the pivot
};

الإعدادية O(ن سجل ن):

1. إنشاء قائمة النطاقات
2. اختر النقاط المحورية (ربما باستخدام قائمة مرتبة بتواريخ الانتهاء.) ؟؟
3. قم ببناء شجرتك.

يبحث:

1. استخدم البحث الثنائي للعثور على المحور الأول الذي يكون >= TestRange.End

2. اجتياز الشجرة حتى المحور > TestRange.Start

   2 أ.أضف الأوراق إلى نتيجتك.

---

مثال:

نطاقات:

• 0 - 2
• 1 - 2
• 2 - 3
• 1 - 4
• 2 - 4
• 0 - 5
• 4 - 5
• 2 - 6
• 3 - 7

شجرة:

                             4
               --------------+------------------
               3             |                 7
               |            1-4                |
               |            2-4                |
               |            0-5                |
               |            4-5                |
      ---------+------                 --------+--------
      2        |    null              6        |       null
 -----+----   2-3                 ----+----   3-7
null  |  null                   null  |  null    
     0-2                             2-6
     1-2

Answer 3

نطاقات غير متداخلة:

الإعدادية O(ن سجل ن):

1. قم بعمل مصفوفة/متجه للنطاقات.
2. فرز المتجه حسب نهاية النطاق (قطع الروابط عن طريق الفرز حسب بداية النطاق)

يبحث:

1. استخدم البحث الثنائي للعثور على النطاق الأول بقيمة نهاية >= TestRange.Start

2. يبدأ المكرر في البحث الثنائي حتى تجد Start > TestRange.End:

   2 أ.إذا كان النطاق الحالي يقع ضمن نطاق الاختبار، فأضفه إلى النتيجة.

Answer 4

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

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

Answer 5

النطاقات المتداخلة:

الإعدادية O(ن سجل ن):

1. قم بعمل مصفوفة/متجه للنطاقات.
2. فرز المتجه حسب نهاية النطاق (قطع الروابط عن طريق الفرز حسب بداية النطاق)

3. اصنع ناقلًا ثانيًا من ints.يمثل هذا النقطة التي يمكنك عندها التوقف عن البحث.

   int stop[size];
   stop[size-1] = Ranges[size - 1].start;
   for (int i = size - 2; i >= 0; i--)
   {
       stop[i] = min(Ranges[i].start, stop[i+1]);
   }
   

يبحث:

1. استخدم البحث الثنائي للعثور على النطاق الأول بقيمة نهاية >= TestRange.Start

2. يبدأ المكرر عند البحث الثنائي حتى stop[i] > TestRange.End:

   2 أ.إذا كان النطاق الحالي يقع ضمن نطاق الاختبار، فأضفه إلى النتيجة.

Answer 6

إذا تداخلت النطاقات، ويريد المرء استردادها الجميع النطاقات التي تتداخل (أو تحتوي على) نطاق مستهدف معين، يبدو أن معظم الحلول المذكورة أعلاه لا تعمل.

كما أشار البعض، إذا (الأسوأ) الجميع يحدث أن تتقاطع النطاقات مع النطاق المستهدف (على سبيل المثال، إذا كان النطاق المستهدف هو {0..MAXINT} أو ما شابه ذلك) فبالطبع يتطلب الأمر O(n) لإرجاع النطاقات n.

ولكن أليست الحالة المثيرة للاهتمام والنموذجية/المتوسطة، حيث لا تتقاطع سوى نسبة صغيرة جدًا من إجمالي النطاقات n مع النطاق المستهدف؟اتصل بالرقم الذي يفعل تقاطع "m" - في هذه الحالة، قد تكون قادرًا على القيام بعمل جيد مثل O(m).وإذا كان n=10^9 وm=10، فهذا فرق حاسم.

خذ بعين الاعتبار الحالة البسيطة للمستند النصي الذي يحتوي على مناطق مختلفة تم تمييزها من أجل "النوع" الخاص بها - ربما تريد العثور على جميع الوحدات المميزة التي تحتوي على نطاق معين من النص أو تتقاطع معه (على سبيل المثال، فقرة).في HTML أو XML أو ما شابه ذلك، يمكن أن يكون هؤلاء فقط أسلافًا للعقدة (العقد) النصية التي تحتوي على بعض أحرف النطاق المستهدف على الأقل.في التمثيلات النموذجية مع المؤشرات الرئيسية في كل عقدة، يكون هذا O(m) أفضل بكثير من O(n)، خاصة لأن m هو (بالنسبة للنطاقات المستهدفة القصيرة أو المتزامنة) مجرد عمق تداخل الشجرة، والذي يميل إلى أن يكون أقل حتى من ln(n) لأن مستندات XML الكبيرة في الممارسة العملية تصبح أكثر كثافة وليست أعمق.

الحالة المثيرة للاهتمام أصعب:ماذا لو كانت "عناصرك" لا تشكل شجرة كما هو الحال في XML، ولكن يمكن أن تتداخل كما هو الحال في MECS، وCLIX، وLMNL، وبعض الأنظمة الأخرى؟لا تزال ترغب في العثور على جميع المناطق/"العناصر" التي تتداخل مع هدفك، ولكن ليس من السهل تنظيمها.

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

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

Answer 7

يبدو أنك بحاجة إلى فئة تنفذ واجهة SortedSet.TreeSet هو التطبيق الذي يأتي مع واجهة برمجة التطبيقات الأساسية.

اجعل مجموعة واحدة تحتوي على النطاقات مرتبة حسب القيمة الأدنى، ومجموعة أخرى مرتبة حسب القيمة الأعلى.

يمكنك بعد ذلك تنفيذ ما يعادل خوارزمية قاعدة البيانات باستخدام مجموعات الذاكرة.

أما فيما يتعلق بما إذا كان هذا أسرع بالفعل من O(n)، فلا أستطيع أن أقول.

Answer 8

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

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

  - if the node range intersects the input range:
     - if it's a leaf node, then add the range to your result list
     - if it's not a leaf node, then traverse down to the child nodes and repeat this process.

يجب أن يكون O(logN)

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

Answer 9

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

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

-- يحرر --

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

--انتهى التعديل --

تحتوي فئة النطاق على:

final int                               lower;                                  // lower end of range
final int                               upper;                                  // upper end of range

public int compareTo(Object obj) {
    if(obj==null) { return -1; }

    Range                           oth=(Range)obj;

    if(lower<oth.lower) { return -1; }
    if(lower>oth.lower) { return  1; }
    if(upper<oth.upper) { return -1; }
    if(upper>oth.upper) { return  1; }
    return 0;
    }

إدراج النطاق:

public Builder addRange(int fir, int las) {
    if(fir!=-1) { fir&=0x001FFFFF; }
    if(las!=-1) { las&=0x001FFFFF; }

    if(codepoints==null || codepoints.length==0) {
        codepoints=new Range[]{new Range(fir,las)};
        }
    else {
        int                         idx=Range.findChar(codepoints,fir);
        int                         ins=(idx<0 ? -(idx+1) : idx);

        if(idx<0) {
            if     (ins>0                 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); }  // new range adjoins the following range (can't overlap or idx would be >=0)
            else if(ins<codepoints.length && las>=(codepoints[ins  ].lower-1)) { idx=ins;     }  // new range overlaps or adjoins the following range
            }

        if(idx<0) {
            codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
            }
        else {
            boolean                 rmv=false;

            for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
                if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
                codepoints[xa]=null;
                rmv=true;
                }
            if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
                codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
                }
            if(rmv) { codepoints=Range.removeNulls(codepoints); }
            }
        }
    return this;
    }

بحث ثنائي:

static int findChar(Range[] arr, int val) {
    if(arr.length==1) {
        if     (val< arr[0].lower) { return -1; }                             // value too low
        else if(val<=arr[0].upper) { return  0; }                             // value found
        else                       { return -2; }                             // value too high
        }
    else {
        int                             lowidx=0;                               // low index
        int                             hghidx=(arr.length-1);                  // high index
        int                             mididx;                                 // middle index
        Range                           midval;                                 // middle value

        while(lowidx<=hghidx) {
            mididx=((lowidx+hghidx)>>>1);
            midval=arr[mididx];
            if     (val< midval.lower) { hghidx=(mididx-1); }                   // value too low
            else if(val<=midval.upper) { return mididx;     }                   // value found
            else                       { lowidx=(mididx+1); }                   // value too high
            }
        return -(lowidx+1);                                                     // value not found.
        }
    }