اتحاد الفترات

Question

لقد حصلت على فئة تمثل الفاصل الزمني.تحتوي هذه الفئة على خاصيتين "البداية" و"النهاية" من نوع مشابه.أنا الآن أبحث عن خوارزمية فعالة لجمع مجموعة من هذه الفواصل الزمنية.

شكرا لك مقدما.

Answer 1

وفرز لهم من قبل واحدة من حيث (بداية، على سبيل المثال)، ثم التحقق من وجود تداخل مع ه (الأيمن) الجار وأنت تتحرك من خلال القائمة.

class tp():
    def __repr__(self):
        return '(%d,%d)' % (self.start, self.end)
    def __init__(self,start,end): 
        self.start=start
        self.end=end
s=[tp(5,10),tp(7,8),tp(0,5)]
s.sort(key=lambda self: self.start)
y=[ s[0] ]
for x in s[1:]:
  if y[-1].end < x.start:
      y.append(x)
  elif y[-1].end == x.start:
      y[-1].end = x.end

Answer 2

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

O (ن سجل ن) + O (ن) = O (ن سجل ن)

Answer 3

اتضح أن هذه المشكلة قد تم حلها، عدة مرات - على مستويات مختلفة من الخيال، تحت التسميات (التسميات): http://en.wikipedia.org/wiki/Interval_tree , http://en.wikipedia.org/wiki/Segment_tree وأيضا "RangeTree"

(نظرًا لأن سؤال OP يتضمن عددًا كبيرًا من الفواصل الزمنية، فإن هياكل البيانات هذه مهمة)

---

فيما يتعلق باختياري لاختيار مكتبة بايثون:

• من خلال الاختبار، وجدت أن أكثر ما يميزها هو كونها كاملة المواصفات وتيار بيثون (غير متعفن قليلاً):فئتي "Interval" و"Union" من SymPy، راجع: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• خيار آخر جيد المظهر، وأداء أعلى ولكن خيار أقل ثراءً بالميزات (على سبيل المثال.لم تنجح في إزالة نطاق النقطة العائمة): https://pypi.python.org/pypi/Banyan

أخيراً:ابحث في SO نفسها، ضمن أي من IntervalTree، وSegmentTree، وRangeTree، وستجد إجابات/خطافات وافرة

Answer 4

والخوارزمية التي geocar فشلت في الحالات التالية:

s=[tp(0,1),tp(0,3)]

ولست متأكدا جدا ولكن أعتقد أن هذا هو الطريق الصحيح:

class tp():
    def __repr__(self):
        return '(%.2f,%.2f)' % (self.start, self.end)
    def __init__(self,start,end): 
        self.start=start
        self.end=end
s=[tp(0,1),tp(0,3),tp(4,5)]
s.sort(key=lambda self: self.start)
print s
y=[ s[0] ]
for x in s[1:]:
    if y[-1].end < x.start:
        y.append(x)
    elif y[-1].end == x.start:
        y[-1].end = x.end
    if x.end > y[-1].end:
        y[-1].end = x.end
print y

وأنا أيضا تنفيذه لالطرح:

#subtraction
z=tp(1.5,5) #interval to be subtracted
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)]

s.sort(key=lambda self: self.start)
print s
for x in s[:]:
    if z.end < x.start:
        break
    elif z.start < x.start and z.end > x.start and z.end < x.end:
        x.start=z.end
    elif z.start < x.start and z.end > x.end:
        s.remove(x)
    elif z.start > x.start and z.end < x.end:
        s.append(tp(x.start,z.start))
        s.append(tp(z.end,x.end))
        s.remove(x)
    elif z.start > x.start and z.start < x.end and z.end > x.end:
        x.end=z.start
    elif z.start > x.end:
        continue

print s

Answer 5

وترتيب جميع النقاط. ثم انتقل من خلال قائمة تزايد عداد للحصول على نقاط "بداية"، وdecrementing ذلك للحصول على نقاط "إنهاء". إذا وصلت العداد 0، ثم هو حقا نقطة نهاية واحدة من فترات في الاتحاد.

والعداد سوف يذهب أبدا سلبي، وسوف تصل إلى 0 في نهاية القائمة.

Answer 6

والعثور على مجموعه من اتحاد فترات في C ++

#include <iostream>
#include <algorithm>

struct interval
{
    int m_start;
    int m_end;
};

int main()
{
    interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } };

    std::sort(
        arr,
        arr + sizeof(arr) / sizeof(interval),
        [](const auto& i, const auto& j) { return i.m_start < j.m_start; });

    int total = 0;
    auto current = arr[0];
    for (const auto& i : arr)
    {
        if (i.m_start >= current.m_end)
        {
            total += current.m_end - current.m_start;
            current = i;
        }
        else if (i.m_end > current.m_end)
        {
            current.m_end = i.m_end;
        }
    }

    total += current.m_end - current.m_start;
    std::cout << total << std::endl;
}