平面上点的最短距离

Question

我在想怎样才能让这段代码更像弦乐。更专业，更有可读性。代码运行得很好。

# Uses Python 3
"""
Finds the closest pair of point from a set of points on a plane
by brute-force (O(n^2)) and divide-and-conquer algorithms (O(nlog(n))).
Input: x,y coordinates (float)
Output: minimum distance (float)& closest pair (complex number)
@ Author: RA
"""

import sys


# Brute force algorithm.

def brute_force(xpoints):  # px will be passed to the function
    n = len(xpoints)
    if n < 2:
        return float('inf'), (None, None)
    else:
        sep = float('inf')  # set the initial minimum to infinity
        pair = ()
        for i in range(n - 1):
            for j in range(i + 1, n):
                if abs(xpoints[i] - xpoints[j]) < sep:
                    sep = abs(xpoints[i] - xpoints[j])
                    pair = (xpoints[i], xpoints[j])

    return sep, pair


# Divide and Conquer


def divide_n_conquer(xpoints, ypoints):
    n = len(xpoints)
    if n <= 3:
        return brute_force(xpoints)

    xmedian = int(n / 2)

    yl, yr = [], []
    for p in ypoints:
        if p.real < xpoints[xmedian].real:
            yl.append(p)
        else:
            yr.append(p)

    (l_sep, l_pair) = divide_n_conquer(xpoints[:xmedian], yl)  
    (r_sep, r_pair) = divide_n_conquer(xpoints[xmedian:], yr)

    (sep, pair) = (l_sep, l_pair) if l_sep < r_sep else (r_sep, r_pair)

    sep_strip, pair_strip = split(xpoints, ypoints, sep)  

    if sep_strip < sep:
        sep = sep_strip
        pair = pair_strip

    return sep, pair


def split(xpoints, ypoints, sep):
    xdivider = xpoints[int(len(xpoints)/2)].real
    ystrip = [item for item in ypoints if
              abs(item.real - xdivider).real < sep]  

    ns = len(ystrip)  # Number of points in the strip
    sep = float('inf')
    pair = ()
    if ns > 1:

        for i in range(ns - 1):
            for j in range(i + 1, min(i + 8, ns)):
                if abs(ystrip[i] - ystrip[j]) < sep:
                    sep, pair = abs(ystrip[i] - ystrip[j]), (ystrip[i], ystrip[j])

    return sep, pair


if __name__ == '__main__':
    _input = sys.stdin.read()
    data = list(map(int, _input.split()))
    n = data[0]
    x = data[1::2]
    y = data[2::2]
    p = [complex(x, y) for x, y in zip(x, y)]  
    px = sorted(p, key=lambda p: p.real)  # points sorted by x
    py = sorted(p, key=lambda p: p.imag)  # points sorted by y
    print("{0:.9f}".format(divide_n_conquer(px, py)[0]))

Answer 1

只是回顾一下brute_force。

1. 没有文档字符串。
2. 如果注释只是重复代码中的内容，就不需要编写注释了: sep = float('inf') #将初始最小值设置为无穷大，使用注释来解释从代码中很难推断出来的事情。
3. n < 2的特例是不必要的。如果n小于2，则i上的循环将为空，没有对进行测试。
4. 有一些多余的括号。在Python中，逗号运算符具有比赋值更高的优先级，因此，您可以编写: pair =xpoint我，xpointJ，而不是: pair =xpoint我，xpointJ。
5. 在某些情况下，表达式abs(xpoints[i] - xpoints[j])会被计算两次:这可以通过将结果存储在局部变量中来避免。
6. 当循环遍历一个序列的不同对时，请使用itertools.combinations，如下所示:从迭代工具导入组合def brute_force( points )：“找到序列点中具有最接近分离的对(p，q)。返回元组(分离，(p，q))”。sep = float('inf')对=0，对于p，q组合(点，2)：pq_sep = abs(p )如果pq_sep < sep: sep = pq_sep对= p，q返回sep，结对
7. 可以使用min和operator.itemgetter将其转换为一个表达式:从运算符导入itemgetter def brute_force(Point)的迭代工具导入组合：“在具有最接近分离的序列点中查找对(p，q)。返回元组(分离，(p，q))”。返回min((abs(P)，(p，q) )表示p，q的组合(点数，2)，key=itemgetter(0)，default=(浮点数(‘inf’)，(无，无))(这需要是Python3.4或更高版本，因为它使用了default关键字参数)。并不是每个人都认为这种编程风格是可读的，所以完全有理由停止使用上面第6节中的版本，而不是试图将所有内容压缩到一个表达式中。

Answer 2

关于代码一般样式的三个注释，跳过了另一个答案中已经说过的内容。

1.以类似的形式表达协调思想.

对于外部用户，brute_force和divide_n_conquer这两个函数是相同的。这些函数没有理由有不同的签名。建议: brute_force和divide_n_conquer的论据应该是相同的。

变量命名:为什么l_sep、l_pair和yl (而不是l_y)？

2.使用明确、具体、具体的语言.

变量名(如l_sep、l_pair、sep、ns )在没有上下文的情况下是不清楚的。如果您不能想出更好的名称，那么就显式地记录它们。一般越少越好。

3.不要把一个句子分成两半.

函数拆分(似乎)在divide_n_conquer之外毫无用处。理想情况下，split应该属于divide_n_conquer的主体。如果不重构代码，这是不可能的，因为递归调用，也就是说，拆分将在每个函数调用中重新定义。对此问题的一种pythonic解决方案是通过重命名函数_split，将拆分的函数标记为辅助函数。查看更多信息，这里。

或者，可以在divide_n_conquer内部定义拆分，例如，只要您定义了另一个助手函数divide_n_conquer_recurse。然后，该函数将看起来类似于：

def divide_n_conquer(xpoints): # Same signature as brute_force. See 1.

    def split(xpoints, ypoints, sep):
        pass

    def divide_n_conquer_recurse(...conditions):
        if base_condition: # n <=3 ?
            return brute_force(xpoints)
        else:
            if some_condition:  # l_sep < r_sep ?
                updated_conditions = split(...)
                return divide_n_conquer_recurse(updated_conditions)
            else:
                other_conditions = split(...)
                return divide_n_conquer_recurse(other_conditions)

    # parse xpoints into xpoints and ypoints.
    ...
    return divide_n_conquer_recurse(...initial_conditions)

小免责声明:受风格要素启发的段落名称。