Do a pairwise comparison of each element in two sets and return a top 3 ranklist

Question

Given two sets, how do I perform a pairwise comparison of each element in one set with each element of the other set.

I would like to get top 3 results for each element in the initial set.\

Is there a faster way to solve the task. I am looking for a more pythonic way of doing the 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's not bad, it's better than sorting the array on each iteration, but it's still O(N^2).

Since you know the array indices that you want, you can use the quickselect algorithm to find indices 0,1,2 based on the magicComp function in O(log n) time. This'll reduce your run-time to O(n*log n)

Based on the code in that link, your code would look something like:

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