设计MapReduce函数计算多列表中集合间的所有交集

First, let's recap the problem with the given examples to make sure we're aligned:

Example Input Collections #

L1 = [{2,7},{2,7,8},{2,3,6,7},{1,2,4,5,7}]
L2 = [{3,6},{1,3,4,6,7},{2,3,5,6,8}]
L3 = [{2,5,7,8},{1,2,3,5,7,8}, {2,4,5,6,7,8}]

Example Operation #

We need to pick one set from each list, compute their intersection, and collect all unique intersection results. For example:

{2,7}.intersection({3,6}).intersection({2,5,7,8})= empty
{2,7}.intersection({1,3,4,6,7}).intersection({2,5,7,8})= {7}
# ... and so on for all possible cross-list combinations

Example Final Output #

{{empty},{2},{3},{6},{7},{2,3},{2,5},{2,6},{2,8},{3,7},{4,7},{6,7},{1,7}}

MapReduce Implementation Approach #

Let's break this into the Map and Reduce phases, plus a note on handling edge cases like empty intersections.

1. Map Phase #

First, we need to tag every set with two pieces of metadata to track its origin:

• A unique identifier for its parent list (e.g., list_1 for L1, list_2 for L2, etc.)
• A unique ID for the set within its parent list (e.g., set_1 for the first set in L1)

Here's what the Map function does:

• Input: A single set, along with its parent list ID and internal set ID.
• Output: For every element in the set, emit a key-value pair where:
  • Key: The element itself (e.g., 2, 7)
  • Value: A tuple containing (parent_list_id, internal_set_id, the_full_set)

For example, processing the set {2,7} from L1 would emit two pairs:

• Key: 2, Value: ("list_1", "set_1", {2,7})
• Key: 7, Value: ("list_1", "set_1", {2,7})

2. Shuffle Phase (Handled Automatically by MapReduce) #

The framework will group all values by their key. So for element 7, we'll get all tuples of sets (from any list) that contain 7.

3. Reduce Phase #

The Reduce function's job is to generate valid cross-list set combinations, compute their intersections, and prepare results for deduplication:

1. Group values by parent list: Split the incoming values into groups where each group corresponds to one input list (e.g., all list_1 sets, all list_2 sets, etc.).
2. Generate cross-list combinations: Create every possible combination where we pick exactly one set from each list group (since we need one set per original input list).
3. Compute intersections: For each combination, calculate the intersection of the selected sets. Since all sets in the combination contain the current element, the intersection will at minimum include this element (unless other elements are excluded across all sets).
4. Emit hashable intersections: Convert the intersection to a hashable type (like a sorted tuple or frozenset) so we can deduplicate it later. Emit this hashable intersection as the key, with a value of 1.

4. Second Reduce Phase (Deduplication) #

To get the final unique set of intersections, we run a lightweight second MapReduce step:

• The Map step just passes through the hashable intersection keys with their 1 values.
• The Reduce step counts occurrences of each key. Any key with a count ≥1 is a valid intersection result, so we collect all these keys as our final output.

Handling Empty Intersections #

Empty intersections don't have any elements, so they won't be captured by the element-based approach above. To include them:

• During the initial Map phase, emit an additional key-value pair for every set: Key: "__EMPTY_CHECK__", Value: (parent_list_id, internal_set_id, the_full_set)
• In the Reduce phase for __EMPTY_CHECK__, generate all cross-list combinations, compute their intersections, and if any intersection is empty, emit the empty set (as a hashable type like () or frozenset()) to include in the final results.

内容的提问来源于stack exchange，提问作者cdt