暴力破解最近点对算法 - for循环

Question

我刚开始学Python，想分析一下“最近点对”这个算法。找到一个例子

里面有这些代码：

return min( ((abs(point[i] - point[j]), (point[i], point[j]))
                 for i in range(numPoints-1)
                 for j in range(i+1,numPoints)),
                key=itemgetter(0))

我不太明白这些for循环是怎么运行的。

这些for循环和点、key还有itemgetter有什么关系呢？

我把这段代码放到Ideone上试了一下，

结果在times()函数里出现了运行时错误：

def times():
    ''' Time the different functions
    '''
    import timeit

    functions = [bruteForceClosestPair, closestPair]
    for f in functions:
        print 'Time for', f.__name__, timeit.Timer(
            '%s(pointList)' % f.__name__,
            'from closestpair import %s, pointList' % f.__name__).timeit(number=1)

谢谢。

Answer 1

你的 min 代码其实可以用一个 生成器 来实现，像这样：

def getPoints(point, numPoints):
  for i in range(numPoints - 1):
    for j in range(i + 1, numPoints):
      yield (abs(point[i] - point[j]), (point[i], point[j]))

return min(getPoints(point, numPoints), key=itemgetter(0))

正如 @DSM 提到的，你代码中 min 的第一个参数是一个 生成器表达式。