nvbn Sep 16 2013 at 17:02

Ненормальное функциональное программирование на python

7 min

44K

Abnormal programming*Python*Functional Programming*

+47

Comments 18

Jimilian Sep 16 2013 at 17:56

Заключение прекрасно!

Andrey_Solomatin Sep 16 2013 at 19:32

Тоже проходил этот курс и люблю питон. С выводами абсолютно согласен.

dima_mendeleev Sep 16 2013 at 19:40

а я просто оставлю это здесь:

if (lambda sort = lambda v: (
lambda vec = list(v):
lambda len = len(vec):
lambda for_ = lambda r, f: map(f, r),
swap = lambda i, j: map(vec.__setitem__, (i, j), (vec[j], vec[i])):
lambda _ =
for_(range(len), lambda i:
for_(range(i, len), lambda j:
vec[i] < vec[j] or swap(i, j))):
list(vec))()()()():
__import__(«sys»).stdout.write("%s\n" % sort([3,5,2,6,8]))
)() or True:
print «You can do more in one expression»

dima_mendeleev Sep 16 2013 at 19:45

Это оно так плохо отображается из-за того, что я отхабреный? (Тег source присутствует)

nvbn Sep 16 2013 at 22:21

Ага, теги только у захабренных.

sebres Sep 16 2013 at 22:32

Как бы сказал один мой старый друг проффесор: за усердие — зачет, за понимание — неуд.
Кроме того, что сравниваем огурцы с бананами, еще и грубейшие ошибки при замерах:
1) Во первых, вы хотя бы сравнивайте на одинаковых входных данных, а то у вас xs всегда разный, и int вырастает до wide-wide-int пока последний тест отработает. Т.е. нужно брать из одного xs = range(limit) и чистить результат xs перед каждым start = time(). Потому как тогда одинаковые входные данные, да и всегда отрабатывем garbage переменной xs снаружи замера.

Правильный код для проверки под спойлером

xsin = range(limit)
xs = None

start = time()
xs = [checker(x) for x in xsin][::-1]
print('inline for:', time() - start, [xs[0], xs[-1], len(xs)])

xs = None

start = time()
xs = list(map(checker, xsin))[::-1]
print('map:', time() - start, [xs[0], xs[-1], len(xs)])

xs = None

calculate = curry_tail_r_map(checker)
start = time()
xs = calculate(xsin)[::-1]
print('r_map without pattern matching:', time() - start, [xs[0], xs[-1], len(xs)])
...

Для сравнения — ваше (с переопределением xs):

inline for: [9999900000, 0, 100000]
map: [0, 99998000019999900000, 100000]
r_map without pattern matching: [9999600007999900000899994000029999900000, 0, 100000]

А правильно:

inline for: [9999900000, 0, 100000]
map: [9999900000, 0, 100000]
r_map without pattern matching: [9999900000, 0, 100000]

Кстати в этом случае «map» будет всегда несколько быстрее «inline for».

2) Вы компилировали это, перед исполнением? Потому что у меня несколько другие результаты (для 10 тысяч):

inline for: 0.005000114440917969 [99990000, 0, 10000]
map: 0.004999876022338867 [99990000, 0, 10000]
r_map without pattern matching: 0.5000200271606445 [99990000, 0, 10000]
r_map with pattern matching: 0.9875400066375732 [99990000, 0, 10000]

А теперь внимание, с лимитом в 100 тысяч:

inline for: 0.0650029182434082 [9999900000, 0, 100000]
map: 0.05250191688537598 [9999900000, 0, 100000]
r_map without pattern matching: 50.784531116485596 [9999900000, 0, 100000]
r_map with pattern matching: 85.34341406822205 [9999900000, 0, 100000]

3) Про вашу реализацию на хвостовой рекурсии я умолчу лучше. Кроме того, в следующий раз вы возьмите пример, который нельзя сделать с «inline for», без накладных на вызововы функций, стек и т.д.
Т.е. реальный рекурсивный такой (пусть даже хвостовой) пример. Имхо, сравнение будет хотя бы чуть-чуть адекватнее.

Выводы улыбнули…

nvbn Sep 16 2013 at 22:49

1 — поправил, когда писал статью, не заметил. Но порядки результатов особо не поменялись.
2 — запускал, машины же у всех разные и скорость выполнения разная.
3:

Про вашу реализацию на хвостовой рекурсии я умолчу лучше

Предложите свою =)

Т.е. реальный рекурсивный такой (пусть даже хвостовой) пример. Имхо, сравнение будет хотя бы чуть-чуть адекватнее.

Не хвостовую, да и не всякую хвостовую в for(да и map, да и в reduce) можно переписать. Предложите свой пример.

nvbn Sep 16 2013 at 22:54

По 2 туплю, в статье 0 лишний был.

sebres Sep 16 2013 at 23:47

Да, нет, вы взгляните на мой пример еще раз: при увеличении количества итераций в 10 раз, время исполнения на «for» и «map» растет пропорционально (в 10 раз), два же последних теста замедлились в СТО раз — они не линейны, а значит что-то заведомо-изначально не верно!

nvbn Sep 17 2013 at 00:14

Добавил подсчёт количества вызовов checker'а в github.com/nvbn/pyfunc/blob/master/pyfunc/timing.py, получилось:

inline for: 0.015415668487548828  called: 20000
map: 0.015140533447265625  called: 20000
r_map without pattern matching: 3.7559814453125  called: 20000
r_map with pattern matching: 5.883073806762695  called: 20000

Всё вызывается одинаковое количество раз, теперь добавляю:

straightforward_tail_r_map — с более явным «складыванием» рекурсии;
straightforward_tail_r_map_2 — где убираю tuple unpacking;
straightforward_tail_r_map_3 — где не создаю каждый раз новый аккумулятор, а делаю append к существующему.

Результат:

inline for: 0.007587909698486328  called: 10000
map: 0.007678031921386719  called: 10000
r_map without pattern matching: 0.7014162540435791  called: 10000
r_map with pattern matching: 1.3289029598236084  called: 10000
straightforward map: 0.6855792999267578  called: 10000
straightforward map 2: 0.27460575103759766  called: 10000
straightforward map 3: 0.02640247344970703  called: 10000

Так что не моя реализация кривая, а tuple unpacking и создание нового списка — медленные операции, и как раз создание нового списка походу n^2 =)

sebres Sep 17 2013 at 11:54

Вы серьезно? Никто и не сомневался что checker вызывается одинаковое количество раз. Я как-раз про накладные в вашей реализации обертки. И про адекватность сравнения этого с примитивами, на не совсем удачном примере. Но даже не беря это во внимание, стоимость алгоритма для вашего примера должна рости линейно.

Теперь насчет рекурсии.

Не хвостовую, да и не всякую хвостовую в for(да и map, да и в reduce) можно переписать.

Любую рекурсию можно развернуть в цикл, уменьшая тем самым накладные на вызов, передачу параметров, обертки scope и т.д. Пример ниже показывает рекурсию на цикле, где параметер «a» постоянный (например лямбда сравнения), «b» и «c» меняются (например бегут по хиерархии сравнивая два дерева). Стоимость «обертки» в таком случае зависит не от количества всех ветвей или того хуже листьев дерева, а от средней глубины его.

def recursive_proc (a, b, c):
    stack = []
    while 1:
        ## делаем работу с текущими a, b,c :
        ...
        if next_level:
            ## push - след. уровень, текущие аргументы в стек :
            stack += [[b, c]]
            ## новые b и c
            b, c = ...
            continue;
        else:
            ## pop - возврат в пред. уровень :
            b, c = stack.pop()
            ## окончание рекурсии :
            if not len(stack):
                break

Создавать же рекурсию на сериях, безконечно создавая и копируя списки — это вообще что-то. При этом заявляя, что дескать, не моя реализация хромает, а питон медлено списки создает — это извините вообще по детски.

nvbn Sep 17 2013 at 14:03

Я как-раз про накладные в вашей реализации обертки

Тормозная не обёртка, а сама оборачиваемая функция.

Любую рекурсию можно развернуть в цикл

Ну да, но не в inline for, map или reduce.

Создавать же рекурсию на сериях, безконечно создавая и копируя списки — это вообще что-то.

Статья разве называется «самая оптимальная реализация»?) Ну и если отказаться от копирования списка, то aux становится грязной.

sebres Sep 17 2013 at 14:33

Не поймите привратно — вы на самом деле большой молодец (многие из известных мне питон-программистов не поймут и половину того, что вы написали) и понятно, что делали вы это все, чтобы «повторить все эти крутые штуки в python». Вам бы еще чуть глубже в него закопатся, да некоторое представление — как все это в байт-коде работает — цены бы вам не было.
Книгу «Functional JavaScript» к сожалению не читал, но теперь (спасибо вам) представляю о чем речь. Другое дело, что у JS и python абсолютно разная концептуальная база (не знаю как правильно выразиться) и иногда так «напрямую» переделывать, имхо, как минимум не целесообразно. Например, у питона модель итераторов развита на порядок выше чем у JS. Может быть, используя их (или что-то другое, в чем питон «сильнее» JS), вы пришли бы к другим результатам и соответственно другим выводам.

anjensan Sep 17 2013 at 18:08

Скажите, а насколько развита модель итераторов в Haskell, Erlang, OCaml или другом функциональном языке? Даже иначе поставлю вопрос — в этих языках они (итераторы) вообще есть?

Это, если что, я намекаю на то, что итераторы не совсем ФП.

sebres Sep 17 2013 at 19:26

Это не ко мне — не один из приведенных не знаю к сожалению настолько глубоко, чтобы коментировать уровень «развития» итераторов. Но судя по тому, что в Haskell'е например возможны следующие конструкции "iterate f x == [x, f x, f (f x), ...]" — бесконечный список повторяющихся приложений f от x — думается, что он (уровень) очень и очень на высоте. Хотя это тоже как посмотреть, конструкция ниже например для подсчета суммы через итератор далеко не идеальна (в исполняемом виде):

sumList :: [Integer] -> Integer
sumList (x:xs) = x + (sumList xs)
sumList [] = 0

Проблема здесь в том, что ей требуется O(n) от размера передаваемого списка, выделения которой в этом случае можно было бы избежать, например как здесь (как раз вида хвостовой рекурсии):

sumList :: [Integer] -> Integer
sumList lst = sumLoop lst 0 where
    sumLoop (x:xs) i = sumLoop xs (i+x)
    sumLoop [] i = i

Здесь sumLoop в отличии от первого примера использует тот же scope (stack frame), поэтому память «расходуется» sumList гораздо экономней.
Не зная такие тонкости можно огрести очень много проблем и со скоростью и с ресурсоемкостью. Это наверное одна из причин почему у меня душа не лежит ко всем вами перечисленным языкам. А может я просто не умею их готовить и потому больше «специализируюсь» по питону, тиклю и ко. Хотя тот же тикль например стандартно не имеет конструкций итератора (правда они неплохо строятся на лямбдах и синглтонах). Зато у него много других достоинств.
А вообще, имхо, лучше досконально знать один язык, чем поверхностно много.

anjensan Sep 17 2013 at 19:33

Ок. Если вы не поняли — в Haskell нету итераторов. Есть ленивые списки. А в Python нету истинно ленивых списков — есть только бесконечно-итерируемые коллекции. Так что в этом плане Python не намного лучше JS.

sebres Sep 17 2013 at 19:46

в Haskell нету итераторов

Да ну? А с этим вот как?

А в Python нету истинно ленивых списков

В питоне я вам любой ленивый список на генераторах или их помеси с итераторами построю. В JS например этого в чистом виде (без выкрутасов) нет вовсе.

anjensan Sep 17 2013 at 20:05

Итераторы в Python вещь замечательная. Только вот итераторы одноразовые в том смысле, что обладают побочным эффектом. А генераторы в этом плане еще хуже. Простите, о каком ФП может в таком случае идти речь.

Сравните это, скажем, с приведенным выше классом Traversable. Что же нам теперь, все языки где есть абстракция для обхода коллекции называть функциональными?

То, что в питоне есть итераторы, куча хороших функий для работы с ними — это не делает питон более/менее пригодным для ФП. Это элементы ФП, ни больше, ни меньше.

Show the best of all time