Как сделать эту наивную реализацию Python Quicksort более питонической?

Question

У меня 2 часа на чтение diveintopython , и я реализовал наивную версию быстрой сортировки.

import operator

def even(num):
    return operator.mod(num,2) == 0

def last(list):
    return len(list)-1

def median(list):
    if even(len(list)):
        return len(list)/2 - 1
    else:
        return len(list)/2

def sort(list, pivot_selector):
    if len(list) <= 1:
        return list
    else:
        i = pivot_selector(list)
        pivot = list[i]
        less, greater, equal = [], [], []
        for x in list:
            if x < pivot:
                less.append( x )
            elif x == pivot:
                equal.append( x )
            else:
                greater.append( x )

    return sort(less, pivot_selector) + equal + sort(greater, pivot_selector)

if __name__ == "__main__":
    print sort([5,4,3,2],median)
    print sort([],median)
    print sort([2],median)
    print sort([3,2],median)
    print sort([3,2,3],median)
    print sort([1,3,2],median)
    print sort([1,'a',0],median)
    print sort([None,1,0],median)

5 вопросов:

1. Этот код находится в файле с именем quicksort.py. Как скрыть метод даже от экспорта в открытый доступ.
2. Является ли pythonic указывать * pivot_selector * в качестве параметра?
3. Что-то не так или неоптимально с моей реализацией быстрой сортировки?
4. Как бы вы позволили пользователю указать компаратор, который будет принудительно настраивать порядок элементов списка?
5. Есть ли питонный способ применить ограничение, согласно которому параметр списка должен содержать однородные типы?

Answer 1

1 - этот код находится в файле quicksort.py.Как скрыть метод даже от экспорта в открытый доступ?

Соглашение состоит в том, чтобы называть функции приватными для вашего модуля с подчеркиванием в начале .

2 - Является ли Pythonic передачей * pivot_selector * в качестве параметра?

Поскольку в Python есть функции первого класса, можно передавать функции в качестве параметров.

3 - Что-то не так или неоптимально с моей реализацией быстрой сортировки?

Использование списка equal кажется мне нетрадиционным. Обычно элементы, равные центральной точке, оказываются в списке greater.

4 - Как вы позволите пользователю указать компаратор, который будет принудительно настраивать заказ наэлементы списка?

Стандартные функции Python sort() и sorted() имеют необязательный параметр для функции сравнения.Кажется, это лучший способ сделать это.

5 - есть ли питонный способ применить ограничение, согласно которому параметр списка должен содержать однородные типы?

В Python выобычно не беспокойся об этом.У Python есть концепция "утки" , поэтому, если объект делает то, что должен, нам не нужно заранее проверять его тип.Это часто выражается как «Проще просить прощения, чем разрешения».

Поэтому позвольте пользователю вашего модуля беспокоиться об Исключении, которое будет выдано, если они передадут список объектов для сортировки, которые могут 'нельзя сравнивать друг с другом.

Answer 2

Некоторые полуслучайные заметки в вашем коде:

• Почему явно operator.mod в even, а не просто %?
• Действительно ли len(list)/2 - 1 действительно важен в median? Если у вас есть список длины 4, почему индекс 2 меньше медианы, чем индекс 1? Также, middle было бы более подходящим именем, потому что функция на самом деле не вычисляет медиану . Поиск реальной медианы в списке для быстрой сортировки является довольно сложной проблемой и обычно приближается.
• Передача селектора как функции довольно Pythonic. Вы можете использовать тот же метод, чтобы передать функцию сравнения и использовать ее в sort.
• Ваш вопрос (5) пахнет непифоническим - не делайте этого. Python - это все о типизировании утки - если ваш пользователь думает, что он хочет сравнить целые числа с class UserID и предоставляет соответствующие методы / операторы, позвольте ему.

Answer 3

Я думаю, это довольно хорошо.Мне нравится аргумент функции для селектора поворота.

Некоторые комментарии:

• Не создавайте теневые встроенные элементы, такие как list или sort
• Используйте li [-1], чтобы получить последний элемент из списка
• Функция even выглядит немного излишней.

Answer 4

Pythonic способ реализовать алгоритм сортировки не в. ;) Встроенная sort существует по причине, которая заключается в том, что должен быть только один способ сделать это.

Это говорит:

• Нет необходимости import operator для простой операции модуля. Pythonistas понимают символ %.

• Но нам даже не нужно отдельно проверять четность длины списка, потому что Python выполняет целочисленное деление.

• Нет смысла превращать median в функцию на самом деле, в этот момент, потому что работа, которую она выполняет, очень проста. Нам также не нужен last, потому что Python позволяет индексировать список с отрицательными числами и считать его с конца. mylist[-1] - идиоматический, Pythonic способ получить последний элемент.

• Общая практика программирования: не нужно все делать детально - то есть установите отдельную переменную для каждого промежуточного результата в каждом расчете. Переменные предназначены для вещей, которые достаточно важны, чтобы иметь имена. Если вы не можете придумать более описательное имя, чем «я», это может быть признаком того, что вам на самом деле не нужно разбивать вещи.

• Как уже упоминалось, не создавайте теневых построек. Одно общее соглашение для переменных, которые должны быть списками, это называть их a_list. (Это из мира Smalltalk, IIRC.)

• Используйте списки (и / или встроенные функции map и filter, по вкусу) для обработки списков в другие списки, когда это возможно.

• Я бы сказал, что pivot_selector должен фактически вычислять пороговое значение, а не позицию. В конце концов, нет никакой причины, по которой корректность алгоритма требует, чтобы 'pivot' действительно находился в массиве:)

  def middle(a_list): return a_list[(len(a_list) - 1) / 2]
  
  
  def last(a_list): return a_list[-1]
  
  
  def quick_sort(a_list, pivot_selector):
    if len(a_list) <= 1: return a_list
    pivot = pivot_selector(a_list)
    return (
      quick_sort([x for x in list if x < pivot], pivot_selector) +
      [x for x in list if x == pivot] +
      quick_sort([x for x in list if x > pivot], pivot_selector)
    )
  

Answer 5

2: Да.Но использование значения по умолчанию может быть лучше.

5: экземпляр.Но не хороший выбор.Чтобы убедиться, что у них всех есть необходимый интерфейс - это нормально, вам не нужно следить за их типами.

Answer 6

Единственное, что я хотел бы добавить, это то, что создание трех списков и увеличение их по одному элементу за раз выглядит довольно неоптимальным.Типичная реализация быстрой сортировки (в Python или нет) перемещает элементы в существующем списке.

Answer 7

1. Вы не скрываете вещи в Python, мы все здесь взрослые.Если вы действительно не хотите экспортировать его, вы можете сделать его внутренней функцией (объявить ее внутри функции, которую вы используете).
2. Я не понимаю, почему это не будет пифоническим.Передача параметров функции обычно используется всеми API Python (например, аргумент sort s key)
3. Да, медиана должна называться «средняя».И, конечно, как вы, наверное, уже знаете, вы можете отсортировать его на месте и заменить рекурсию на итерацию, основанную на стеке, что будет немного быстрее (поскольку кадры стека вызовов тяжелее выдвигать и извлекать, чем просто аргументы, чем изменения).
4. Как и в случае с аргументом селектора сводок, передайте функцию, которая принимает два аргумента и возвращает true, если аргументы в порядке.
5. Нет, но вы можете вызвать исключение, если выпожелает.Если вы действительно, действительно хотите, вы можете использовать numpy массивы, которые гарантированно будут однородными.