CODEWITHSUNDEEP
pythonpython-3.xperformancesetset-intersection
Raquel Roses
Raquel Roses

Reputation: 3

Intersection of multiple sets, which ones intersect and where?

I have a very large number of sets (thousands), each corresponding to an agent (entity) with an id - this can be represented as a dictionary, where each agent_id (key) has a set (value).

    agent_path= {a1: (25, 60, 86, 95), a2: (72, 34, 96, 60, 12, 74, 95, 43, 78), a3: ....}

I need to find the intersections of the different sets, and more importantly, find which agents intersect with each other.

    a1 ∩ a2: 60, 95

This could for example be stored in a new dictionary. In the next step, I will have to loop over each agent with intersecting elements again to perform the next action.

My solution would be to loop x2 over the agent_path dictionary and compare each set individually, and then save the results into a dictionary:

agent_path=dict()
agent_path['a1']=a
agent_path['a2']=b

agent_inters=dict()
for agent1 in agent_path.keys():
for agent2 in agent_path.keys():
    agent_key=str(agent1)+str(agent2)
    if agent1 == agent2:
        pass
    else:
        set1=set(agent_path[agent1])
        set2=set(agent_path[agent2])
        set1xset2=set1.intersection(set2)
        agent_inters[agent_key]=set1xset2

Is there a more efficient way to do this? Especially, as I will have to do this for a large number of sets and multiple times (the sets are update at each time step in the model).

Upvotes: 0

Views: 582

Answers (1)

Sunny Patel
Sunny Patel

Reputation: 8078

You can make use of itertools.combinations which will speed up a lot of the comparisons, especially to not have repeats so that (agent1 ∩ agent2) and (agent2 ∩ agent1) don't both get compared since their results are equal. Also, placing them in a set before comparison will speed things up as well.

from itertools import combinations

agent_path = {
    "a1": set([25, 60, 86, 95]),
    "a2": set([72, 34, 96, 60, 12, 74, 95, 43, 78]),
    "a3": set([15, 23, 60, 9, 99, 95])
}

agent_inters = {}

for agent1, agent2 in combinations(agent_path, 2):
    agent_key = str(agent1)+str(agent2)
    agent_common = agent_path[agent1] & agent_path[agent2]
    if agent_common:
        agent_inters[agent_key] = agent_common
print(agent_inters)          #Prints {'a1a2': {60, 95}, 'a1a3': {60, 95}, 'a2a3': {60, 95}}

If you want to compare one set that gets updated to the rest, you can make a separate for loop but keep the innards that the same (function def!) ensuring the key order of str(agent1)+str(agent2) is maintained.

Upvotes: 1

Related Questions