对两个集合中的每个元素进行成对比较，并返回前3个ranklis

Question

给定两个集合，如何对一个集合中的每个元素与另一个集合中的每个元素进行成对比较。在

我想得到初始集合中每个元素的前3个结果。\

有没有更快的方法来解决这个任务。我正在寻找一种更像Python的任务。在

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

如果我们想成为真正的Python

from functools import partial

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

应该会成功的。但是，这仍然是O（n²ln n），因为我们需要为每个项目重新排序第二组。在

Answer 2

嗯，快点。对于每个内部迭代，原始版本的时间复杂性为O(3n)。在

下面是时间复杂度更快的O(nlg3)。在

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())

Answer 3

你的答案不错，这比在每次迭代时对数组进行排序要好，但仍然是O（N^2）。在

由于您知道所需的数组索引，因此可以使用quickselect算法在O（logn）时间内基于magicComp函数查找索引0,1,2。这将把运行时间减少到O（n*logn）

基于该链接中的代码，您的代码将类似于：

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