Эквивалент Python для схем / функций Lisp CAR и CDR - PullRequest
Новая
       10

Эквивалент Python для схем / функций Lisp CAR и CDR

0 голосов
/ 29 апреля 2018

В настоящее время я пытаюсь реализовать fold / reduce в Python, поскольку мне не нравится версия из functools. Естественно, это подразумевало реализацию чего-то вроде функции Lisp CDR, поскольку у Python, похоже, нет ничего подобного. Вот что я думаю попробовать: 

def tail(lat):
  # all elements of list except first
  acc = []
  for i in range(1,len(lat)):
    acc = acc + [lat[i]]

Будет ли это эффективным способом реализации этой функции? Я пропускаю какую-то встроенную функцию? Заранее спасибо!

1 Ответ

0 голосов
/ 29 апреля 2018

«Что-то вроде функции CDR в Lisp» тривиально: 

acc[1:]

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

Впрочем, делать это не имеет особого смысла. Весь смысл CDR состоит в том, что когда ваши списки являются связанными списками, хранящимися в ячейках CONS, переход от одной ячейки к ее хвосту является одной операцией на машинном языке. Но с массивами (что и есть списки Python), acc[1:] - или более сложная вещь, которую вы пытались написать, или фактически любая возможная реализация - выделяет целый новый массив размера N-1 и копирует значения N-1 .

Эффективность затрат на выполнение этого снова и снова (в алгоритме, который ожидал, что он будет почти бесплатным) будет настолько велика, что ускорение с постоянным коэффициентом использования acc[1:] вряд ли будет достаточно улучшение, чтобы сделать его приемлемым.

Большинство алгоритмов, которые работают быстро с CDR, будут медленными с этим типом нарезки, а большинство алгоритмов, которые работают быстро с этим типом срезов, будут медленными с CDR. Вот почему у нас есть несколько структур данных, во-первых, потому что они хороши для разных вещей.

Если вы хотите узнать наиболее эффективный способ сворачивания / уменьшения массива - это способ, которым functools.reduce (и варианты его, предлагаемые такими библиотеками, как toolz), это просто: итерация.

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

...