ما هي بنية البيانات لإيجاد التقاطعات غير الفارغة بسرعة في قائمة المجموعات؟

Question

لدي مجموعة من N العناصر ، التي هي مجموعات من الأعداد الصحيحة ، دعنا نفترض أنه تم طلبها ونسميها I[1..N]. نظرا ل candidate تعيين ، أحتاج إلى العثور على مجموعة فرعية من I التي لها تقاطعات غير فارغة مع candidate.

لذلك ، على سبيل المثال ، إذا:

I = [{1,2}, {2,3}, {4,5}]

أنا أتطلع إلى تحديد valid_items(items, candidate), ، مثل ذلك:

valid_items(I, {1}) == {1}
valid_items(I, {2}) == {1, 2}
valid_items(I, {3,4}) == {2, 3}

أحاول تحسين مجموعة واحدة I ومتغير candidate مجموعات. حاليا أقوم بذلك عن طريق التخزين المؤقت items_containing[n] = {the sets which contain n}. في المثال أعلاه ، سيكون ذلك:

items_containing = [{}, {1}, {1,2}, {2}, {3}, {3}]

وهذا هو ، 0 موجود في أي عناصر ، و 1 موجود في البند 1 ، 2 الواردة في itmes 1 و 2 ، 2 و 2 ، ورد في البند 2 ، و 4 و 5 موجودة في البند 3.

بهذه الطريقة ، يمكنني تحديد valid_items(I, candidate) = union(items_containing[n] for n in candidate).

هل هناك أي بنية بيانات أكثر كفاءة (بحجم معقول) لتخزين المؤقت نتيجة لهذا الاتحاد؟ المثال الواضح للفضاء 2^N غير مقبول ، ولكن N أو N*log(N) سيكون.

Answer 1

أعتقد أن الحل الحالي الخاص بك هو الأمثل الحكيمة ، على الرغم من أن هناك تقنيات تحسين صغيرة يمكن أن تحسن من أدائها الفعلي. مثل استخدام عمليات bitwise عند دمج المجموعة المختارة في مجموعة item_containing مع مجموعة العناصر الصالحة.

أي أنك تخزن العناصر_

items_containing = [0x0000, 0x0001, 0x0011, 0x0010, 0x0100, 0x0100]

ويمكن أن تستخدم appal_items الخاص بك من الحكمة أو لدمج مثل هذا:

int valid_items(Set I, Set candidate) {
    // if you need more than 32-items, use int[] for valid 
    // and int[][] for items_containing
    int valid = 0x0000;
    for (int item : candidate) {
        // bit-wise OR
        valid |= items_containing[item];
    }
    return valid;
}

لكنهم لا يغيرون الأداء الكبير.

Answer 2

يتمثل أحد التمثيل الذي قد يساعد في تخزين المجموعات i كمتجهات V من حجم N الذي تكون إدخالات V (i) 0 عندما لا أكون في V وإيجابية خلاف ذلك. ثم لأخذ تقاطع اثنين من المتجهات التي تضرب الشروط ، ولأخطو الاتحاد الذي تضيفه الشروط.