对两组中的每个元素进行成对比较，并 return 排名前三

Question

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

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

有没有更快的方法来解决这个任务。我正在寻找一种更 pythonic 的方式来完成任务。

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

你的答案还不错，比每次迭代都对数组排序要好，但它仍然是 O(N^2)。

由于您知道所需的数组索引，因此可以使用 quickselect 算法根据 magicComp 函数在 O(log n) 时间内找到索引 0,1,2。这会将您的运行时间减少到 O(n*log n)

根据 link 中的代码，您的代码类似于：

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

Answer 2

如果我们想成为真正的 pythonic，比如

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 3

嗯嗯，更快的方式。对于每个内部迭代，您的原始版本的时间复杂度为 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())

对两组中的每个元素进行成对比较，并 return 排名前三

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

python

python-2.x