从列表中获取对的最快方法

问题描述：

给定range(n)从对象范围中获取对的最快方法是按列表中每个对象的距离排序，即对于两个元素列表A和B的距离是abs(A-B)。这是我想出了实现：从列表中获取对的最快方法

sorted(combinations(range(n), 2), key=lambda a: -abs(a[0]-a[1]))

，但我想这是一个发电机，更高效。

你可以排序'combinations'的情况下直接转化成榜第一。你为什么要发电机？ – 2014-12-02 13:13:18

更改为不先转换为列表。我相信它作为一个发电机会更有效率。 – vfxGer 2014-12-02 14:17:16

基本上，两个答案都会生成具有给定距离（n，n-1，n-2，...）的所有数字对，而不是生成所有对，测量距离并排序：通过使用更好的算法，它们避免所有的减法_和_结果上的排序。任何其他节省都是微不足道的。 – alexis 2014-12-02 14:43:57

答

如果你想要一台发电机：

def distant_pairs(n): 
    for d in range(n, 0, -1): 
     for i in range(n-d): 
      yield (i, i+d)

或者散文：对于每一个可能的距离，从最大到最小，找到每个将它们分开一段距离并将其收割。

这里有一个小的测试工具来证明它的工作原理：

for n in range(12): 
    answer = list(distant_pairs(n)) 
    prev_answer = sorted(combinations(range(n), 2), key=lambda a: -abs(a[0]-a[1])) 

    print "SIZE", n 
    print answer 
    print prev_answer 
    assert answer == prev_answer 
    print "---" 
print "done"

答

在距离外环将工作：

((a, a + d) for d in range(1, n) for a in range(n - d))

从列表中获取对的最快方法

相关推荐