Кратчайшее расстояние для точек в плоскости


Мне было интересно, как я могу сделать этот код более подходящие для Python. Более профессиональная и более читабельным. Код работает прекрасно.

# 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]))


Комментарии
2 ответа

Просто обзор brute_force.


  1. Нет строкой документации.

  2. Не надо писать комментарии, если они просто повторяют то, что написано в коде:

    sep = float('inf')  # set the initial minimum to infinity

    Используйте комментарии, чтобы объяснить вещи, которые трудно вывести из считывания кода.


  3. Специальный чехол для n < 2 является ненужным. Если n меньше 2, то цикл по i будет пустой и без пар будут проверены.

  4. Есть некоторые лишние скобки. В Python оператор "запятая" имеет более высокий приоритет, чем назначение, и поэтому, вместо:

    pair = (xpoints[i], xpoints[j])

    вы можете написать:

    pair = xpoints[i], xpoints[j]

  5. Выражение abs(xpoints[i] - xpoints[j]) получает просчитываться дважды в некоторых случаях этого можно избежать, храня результат в локальную переменную.

  6. После перехода на пар последовательности, использовать itertools.combinationsвот так:

    from itertools import combinations

    def brute_force(points):
    """Find the pair (p, q) in the sequence points with the closest
    separation. Return the tuple (separation, (p, q)).

    """
    sep = float('inf')
    pair = None, None
    for p, q in combinations(points, 2):
    pq_sep = abs(p - q)
    if pq_sep < sep:
    sep = pq_sep
    pair = p, q
    return sep, pair


  7. Это может быть превращен в одно выражение, используя min и operator.itemgetter:

    from itertools import combinations
    from operator import itemgetter

    def brute_force(points):
    """Find the pair (p, q) in the sequence points with the closest
    separation. Return the tuple (separation, (p, q)).

    """
    return min(((abs(p - q), (p, q)) for p, q in combinations(points, 2)),
    key=itemgetter(0), default=(float('inf'), (None, None)))

    (Это нужно для Python 3.4 или более поздней версии, поскольку это использует default ключевое слово аргумент.)

    Не каждый находит этот стиль программирования, читаемой, поэтому было бы весьма разумно, чтобы остановить с версией в §6 выше, и не пытаться раздавить все в одно выражение.


6
ответ дан 7 апреля 2018 в 11:04 Источник Поделиться

Три замечания по общему стилю вашего кода, пропуская то, что уже сказал в другой ответ.

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. Не разбить предложение на два.

Функция Split (кажется) бесполезно за пределами divide_n_conquer. В идеале разделить бы принадлежать внутри тела divide_n_conquer. Это не может произойти без рефакторинга кода из-за рекурсивных вызовов, то есть, раскол будет переименован в каждый вызов функции. Типичный для Python решение этой проблемы, чтобы отметить функцию разделения в качестве вспомогательной функции, переименовав его _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)

Небольшая оговорка:
Пункт имена вдохновленный элементами стиля.

1
ответ дан 9 апреля 2018 в 11:04 Источник Поделиться