Python для C # уменьшить понимание функции - PullRequest
Новая
       4

Python для C # уменьшить понимание функции

3 голосов
/ 05 ноября 2011

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

Я нашел несколько источников, как здесь, так и в других местах, которые указывают, что делает функция, и что есть эквивалентный "агрегат"для списков в C #, но я не могу понять, что на самом деле делают вызовы ниже -expect -... возможно, потому что я не могу понять, что возвращает _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 Ответ

3 голосов
/ 05 ноября 2011

  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 перед возвратом, если это не последний элемент. Та же самая логика должна быть легко реализована более приятным, но более многословным способом.

...