Make a pairwise comparison of each element in two sets and return the top rating of the 3rd list

Question

Given two sets, how do I perform pairwise comparisons of each element in one set with each element of another set.

I would like to get the 3 best results for each item in the original set. \

Is there a faster way to solve the problem. I am looking for a more pythonic way of completing a task.

set1 = set([str(item) for item in range(100)]) # Pls. note originally set contains strings set2 = set([str(item) for item in range(50,150)]) # set([str(item) for item in range(50,100)]) for item in set1: max = [-1,-1,-1] for stuff in set2: val = magicComp(item,stuff) if val > max[0]: max[2] = max[1] max[1] = max[0] max[0] = val elif val > max[1]: max[2] = max[1] max[1] = val elif val > max[2]: max[2] = val 

Answer 1

Your answer is not bad, it is better than sorting the array at each iteration, but it is still O (N ^ 2).

Since you know the indexes of the arrays you want, you can use the quickselect algorithm to search for indexes 0,1,2 based on the magicComp function in O (log n). This will reduce the runtime to O (n * log n)

Based on the code in this link, your code will look something like this:

 results = {} ls2 = list(set2) for el in set1: results[el] = [select(ls2, ii) for ii in [0,1,2]] 

Answer 2

If we want to be really pythonic, something like

 from functools import partial most_valueable = { item1: sorted(set2, key=partial(magicComp, item1), reverse=True)[0:3] for item1 in set1 } 

gotta do the trick. This is still O (n² ln n), since we need to re-sort the second set for each element.

Answer 3

Ehmmm, faster way. Your original version has a time complexity of O(3n) for each inner iteration.

The following is faster with O(nlg3) time complexity.

 from queue import PriorityQueue q = PriorityQueue(maxsize=3) for item in set1: map(q.put, (-1 * magicComp(item,stuff) for stuff in set2)) max = [] while not q.empty(): max.append(-1 * q.get())