Блог

Я изо всех сил пытаюсь понять вызов ‘reduce’, написанный ниже на python.

Я нашел несколько источников, как здесь, так и в других местах, в которых указано, что делает функция, и что в C # есть эквивалентный ‘aggregate’ для списков, но я не могу понять, что на самом деле делают приведенные ниже вызовы -ожидать — … возможно, потому, что я не могу понять, что возвращает ‘_keep_left’?

Итак:

1- кто-нибудь может помочь мне рассказать, что возвращает ‘_keep_left’?

2- что , []) означает в вызове reduce?

Большое спасибо.

 TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)

def turn(p, q, r):
    """Returns -1, 0, 1 if p,q,r forms a right, straight, or left turn."""
    return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)

def _keep_left(hull, r):
    while len(hull) > 1 and turn(hull[-2], hull[-1], r) != TURN_LEFT:
            hull.pop()
    return (not len(hull) or hull[-1] != r) and hull.append(r) or hull

def _graham_scan(points):
    """Returns points on convex hull of an array of points in CCW order."""
    points.sort()
    lh = reduce(_keep_left, points, [])
    uh = reduce(_keep_left, reversed(points), [])
    return lh.extend(uh[i] for i in xrange(1, len(uh) - 1)) or lh
  

1. _keep_left возвращает список hull , который изначально пуст. Из него удаляются повороты, не идущие влево. В него добавляется текущая точка, если она уже не является последним элементом в списке.

2. , []) это третий параметр, который нужно уменьшить. Это начальное значение накопителя, которое будет передано _keep_left , таким образом делая hull (и, в конце концов, lh и uh ) изначально пустым.

Он выполняет сканирование Грэма, сначала сортируя точки, затем дважды просматривая все точки ( lh и uh обозначают нижнюю половину и верхнюю половину), и с каждой разверткой точки накапливаются в списке. Баллы накапливаются с помощью reduce , то есть результат изначально пуст, и баллы передаются _keep_left по одному (в отсортированном порядке), и для каждой точки точки, вызывающие поворот направо, удаляются из накопленного списка. Затем текущая точка добавляется в накопленный список.

Возвращаемое значение из _keep_left немного сложнее: not len(hull) возвращает True, если список пуст. hull[-1] != r проверяет, является ли r (текущая точка) последним элементом в списке. hull.append(r) находится в логическом выражении только для побочного эффекта добавления r к списку (выглядит немного грязно для меня), так что, если последний элемент hull является r , hull будет возвращен без добавления r к нему.

Другими словами, из-за короткого замыкания hull всегда будет возвращено, но r будет добавлено к нему перед возвратом, если это не последний элемент. Ту же логику должно быть легко реализовать более приятным, но более подробным способом.