CODEWITHSUNDEEP
pythonalgorithmperformanceoptimizationset
Gunnar
Gunnar

Reputation: 31

Fastest way of comparing intersections of sets and returning the dictionary key which contains the set belonging to the biggest intersection

I have an algorithm for creating a maximal clique cover but it is too slow. For each step I need to compare intersections between a main set, and the sets obtained from the dictionary keys of the main set.

Right now I have a dictionary of sets:

edges = { 1:{2,3},
        2:{1,3},
        3:{1,2}}

And a main set: {1,2} (The length increases with each step)

intersection_C = {1,2}

For the next iteration of this instance it will be: choose the dictionary key (from elements in main set) which gives you the largest intersection.

In other words: compare the intersections of the set edges[1] intersected with the set intersection_C, and the intersection of the set edges[2] intersected with intersection_C. Then choose the key which provided the largest (longest length) intersection. I need to keep both the final resulting intersection and the key which provided the largest intersection.

The key is added to a list C, and the final intersection will become the new main set

What is the fastest way I can do this?

My current algorithm for solving the subproblem is:

best = 0  #longest found length param
for node in intersection_C: #looping through elements of main set
    new = intersection_C.intersection(edges[node])   #new intersection'
    if len(new) >= best:          #comparing  
        candidate = node          #saving key
        best = len(new)          #updating best length
        best_intersection = new     #Saving best found intersection
    del new

Upvotes: 3

Views: 242

Answers (1)

Armali
Armali

Reputation: 19375

I can't imagine a faster algorithm, but we can shorten the notation of your current one:

candidate = max(intersection_C, key = lambda node: len(intersection_C & edges[node]))
best_intersection = intersection_C & edges[candidate]

Upvotes: 1

Related Questions