حساب الحد الأدنى من العناصر بكفاءة عبر مجموعات مرتبة جزئيًا

Question

لدي قائمة بالمجموعات التي أرغب في تصنيفها بترتيب جزئي بناءً على علاقة المجموعة الفرعية.

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

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

ما هي الطريقة الأكثر ملاءمة من حيث المساحة والوقت لحل هذه المشكلة؟ربما هناك طريقة لا تتطلب بناء الرسم البياني بأكمله؟ربما هناك خوارزمية معروفة بمصطلحات أفضل مما وصفته بسذاجة أعلاه؟

أدرك أن متطلبات الوقت والمكان غير محددة أعلاه، ولكن سأكون سعيدًا بأي اقتراحات، سواء ثبت أنها مثالية أم لا...

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

Answer 1

نهج واحد هو فرز المجموعات عن طريق زيادة الحجم، ثم قم بتنفيذ ما يلي مرارا وتكرارا: قم بإخراجها الأولى في القائمة، وإخراجها، وإزالتها من القائمة كل ما تبالغ فيه. سيؤدي ذلك إلى إخراج كل مجموعات الحد الأدنى. وقت التشغيل هو $ O (nk) $ تعيين المقارنات بالإضافة إلى $ O (n \ log n) $ خطوات للفرز، حيث $ n $ هو عدد المجموعات التي لديكها و $ K $ هو الرقم من العناصر الحد الأدنى. أو، لوضعها بطريقة أخرى، إذا كانت كل مجموعة تحتوي على عناصر $ m $ ، ستكون وقت التشغيل تقريبا $ O ( n (k + \ log n) m) m) $ الخطوات الأساسية.

لماذا الترتيب حسب الحجم؟ هذا هو التحسين. أصغر مجموعة مضمونة لتكون ضئيلة (لا يوجد من أصل أصغر في القائمة، لذلك لا يمكن أن تكون أي من مجموعاتها الفرعية في القائمة)، لذلك الحجم هو خدعة مفيدة لتحديد مجموعة يجب أن تكون بالتأكيد ضئيلة.

بدون فرز حسب الحجم، من المحتمل أن ينتهي وقت التشغيل الأسوأ في حالة $ O (n ^ 2) $ تعيين المقارنات (أو $ O (n ^ 2 m) $ الخطوات الأساسية)، والتي هي أسوأ عند $ k \ ll n $ .

---

إليك نسخة محسنة من هذه الخوارزمية. دع $ M $ يكون بنية بيانات تقوم بتخزين مجموعة من المجموعات، ك Trie: على سبيل المثال، مجموعة $ \ {1،3،36،7 \} $ يتوافق مع كلمة $ 1367 $ ويتم تخزينها في Trie وفقا لذلك. في البداية، $ M $ فارغة. كرر ما يلي: خذ المجموعة التالية $ S $ من القائمة؛ تحقق مما إذا كانت أي مجموعة في $ M $ هي مجموعة فرعية من $ s $ ؛ إذا لم يكن كذلك، أدخل $ S $ في $ m $ ؛ أخيرا حذف $ S $ من القائمة (أو تقدم مؤشرك للعنصر التالي في القائمة). يمكن إجراء عملية "التحقق ..." بكفاءة إلى حد ما باستخدام اجتياز متكرر لل Trie. في النهاية، بمجرد مررت القائمة بأكملها، إخراج $ m $ .

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

Answer 2

لقد وجدت الحل في هذه الورقة، ص 12.

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

T = set([]);
for x in X:
    rem = set([]);
    spe = False;
    for a in T:
        rel = oracle(x,a);
        if rel == "x>a":
            spe = True;
            break;
        elif rel == "x<a":
            rem.add(a);
    if not spe:
        T -= rem;
        T.add(x);

أتوقع break لتكون حاسمة لوقت التشغيل الفعلي، لذلك قد يكون من الجيد الفرز X مقدمًا للحصول على استراحات مبكرة - لكنني لست متأكدًا من ذلك.

النقطة الأخرى التي أراها هنا هي ذلك > من المفترض أن يكون غير انعكاسي، لذلك x>x لا يحمل.ولكن بالنسبة لهذا الكود سيكون من الأفضل لو حدث ذلك.لو a==x, ، فإنه ينكسر بدلاً من النظر إلى أبعد من ذلك دون داع.

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

هنا هو التنفيذ كما مأخوذ من الورقة:

def oracle(rep1,rep2):
    if generalizes(rep2,rep1):
        return ">";
    elif generalizes(rep1,rep2):
        return "<";
    return None;

def find_min_els_(repIDs,ID2rep):
    min_els = set([]);
    for x in repIDs:
        spec_of_x = set([]);
        x_is_spec = False;
        for min_el in min_els:
            relation = oracle(ID2rep[x],ID2rep[min_el]);
            if relation == ">":
                x_is_spec = True;
                break;
            elif relation == "<":
                spec_of_x.add(min_el);
        if not x_is_spec:
            min_els -= spec_of_x;
            min_els.add(x);
    return min_els;

الآن تبين أن هذا بطيء للغاية ويمكننا بالفعل أن نقول من التعقيد أنه أمر سيء للغاية إذا كان عرض الترتيب الجزئي هو الرقم m من المتوقع أن تكون العناصر الدنيا كبيرة.

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

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

هنا هو الكود المعني:

def generalizations(spe_rep,gens):
    for el in spe_rep:
        gen_rep = spe_rep - set([el]);
        gen_str = string(gen_rep);
        if not gen_str in gens:
            gens.add(gen_str);
            yield gen_str;
            for x in generalizations(gen_rep,gens):
                yield x;

def find_min_els(repIDs,ID2rep):
    min_els = set(repIDs);
    for x in repIDs:
        for genID in generalizations(ID2rep[x],set([])):
            if genID in min_els:
                min_els.remove(x);
                break;
    return min_els;

يستخدم هذا وظيفة المولد generalizations() لتجنب حساب المزيد من التعميمات x بمجرد العثور على واحد بالفعل في الحد الأدنى من العناصر الحالية.هذا بالفعل سريع جدًا مع بياناتي، ولكن ربما يمكن تحسينه عن طريق إنشاء تعميمات أكثر عمومية أولاً (يجب اختبارها إذا كان هذا يجعلها أسرع) وعلى وجه الخصوص عن طريق توليد التعميمات التي تتكون من عناصر تمت ملاحظتها بالفعل في العناصر الدنيا الحالية.على سبيل المثال إذا كان لدينا x يكون {a,b,c}, ، ولكن لا يوجد عنصر الحد الأدنى الحالي c في ذلك، ليس علينا إنشاء أي مجموعة فرعية من x يحتوي على c, ، أي.فقط {a,b},{a},{b},{}.