Комментарии 18
Заключение прекрасно!
Тоже проходил этот курс и люблю питон. С выводами абсолютно согласен.
а я просто оставлю это здесь:
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»
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»
Это оно так плохо отображается из-за того, что я отхабреный? (Тег source присутствует)
Как бы сказал один мой старый друг проффесор: за усердие — зачет, за понимание — неуд.
Кроме того, что сравниваем огурцы с бананами, еще и грубейшие ошибки при замерах:
1) Во первых, вы хотя бы сравнивайте на одинаковых входных данных, а то у вас xs всегда разный, и int вырастает до wide-wide-int пока последний тест отработает. Т.е. нужно брать из одного
Кстати в этом случае «map» будет всегда несколько быстрее «inline for».
2) Вы компилировали это, перед исполнением? Потому что у меня несколько другие результаты (для 10 тысяч):
А теперь внимание, с лимитом в 100 тысяч:
3) Про вашу реализацию на хвостовой рекурсии я умолчу лучше. Кроме того, в следующий раз вы возьмите пример, который нельзя сделать с «inline for», без накладных на вызововы функций, стек и т.д.
Т.е. реальный рекурсивный такой (пусть даже хвостовой) пример. Имхо, сравнение будет хотя бы чуть-чуть адекватнее.
Выводы улыбнули…
Кроме того, что сравниваем огурцы с бананами, еще и грубейшие ошибки при замерах:
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», без накладных на вызововы функций, стек и т.д.
Т.е. реальный рекурсивный такой (пусть даже хвостовой) пример. Имхо, сравнение будет хотя бы чуть-чуть адекватнее.
Выводы улыбнули…
1 — поправил, когда писал статью, не заметил. Но порядки результатов особо не поменялись.
2 — запускал, машины же у всех разные и скорость выполнения разная.
3:
Предложите свою =)
Не хвостовую, да и не всякую хвостовую в for(да и map, да и в reduce) можно переписать. Предложите свой пример.
2 — запускал, машины же у всех разные и скорость выполнения разная.
3:
Про вашу реализацию на хвостовой рекурсии я умолчу лучше
Предложите свою =)
Т.е. реальный рекурсивный такой (пусть даже хвостовой) пример. Имхо, сравнение будет хотя бы чуть-чуть адекватнее.
Не хвостовую, да и не всякую хвостовую в for(да и map, да и в reduce) можно переписать. Предложите свой пример.
По 2 туплю, в статье 0 лишний был.
Да, нет, вы взгляните на мой пример еще раз: при увеличении количества итераций в 10 раз, время исполнения на «for» и «map» растет пропорционально (в 10 раз), два же последних теста замедлились в СТО раз — они не линейны, а значит что-то заведомо-изначально не верно!
Добавил подсчёт количества вызовов checker'а в github.com/nvbn/pyfunc/blob/master/pyfunc/timing.py, получилось:
Всё вызывается одинаковое количество раз, теперь добавляю:
Результат:
Так что не моя реализация кривая, а tuple unpacking и создание нового списка — медленные операции, и как раз создание нового списка походу n^2 =)
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 =)
Вы серьезно? Никто и не сомневался что 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
Создавать же рекурсию на сериях, безконечно создавая и копируя списки — это вообще что-то. При этом заявляя, что дескать, не моя реализация хромает, а питон медлено списки создает — это извините вообще по детски.
Я как-раз про накладные в вашей реализации обертки
Тормозная не обёртка, а сама оборачиваемая функция.
Любую рекурсию можно развернуть в цикл
Ну да, но не в inline for, map или reduce.
Создавать же рекурсию на сериях, безконечно создавая и копируя списки — это вообще что-то.
Статья разве называется «самая оптимальная реализация»?) Ну и если отказаться от копирования списка, то aux становится грязной.
Не поймите привратно — вы на самом деле большой молодец (многие из известных мне питон-программистов не поймут и половину того, что вы написали) и понятно, что делали вы это все, чтобы «повторить все эти крутые штуки в python». Вам бы еще чуть глубже в него закопатся, да некоторое представление — как все это в байт-коде работает — цены бы вам не было.
Книгу «Functional JavaScript» к сожалению не читал, но теперь (спасибо вам) представляю о чем речь. Другое дело, что у JS и python абсолютно разная концептуальная база (не знаю как правильно выразиться) и иногда так «напрямую» переделывать, имхо, как минимум не целесообразно. Например, у питона модель итераторов развита на порядок выше чем у JS. Может быть, используя их (или что-то другое, в чем питон «сильнее» JS), вы пришли бы к другим результатам и соответственно другим выводам.
Книгу «Functional JavaScript» к сожалению не читал, но теперь (спасибо вам) представляю о чем речь. Другое дело, что у JS и python абсолютно разная концептуальная база (не знаю как правильно выразиться) и иногда так «напрямую» переделывать, имхо, как минимум не целесообразно. Например, у питона модель итераторов развита на порядок выше чем у JS. Может быть, используя их (или что-то другое, в чем питон «сильнее» JS), вы пришли бы к другим результатам и соответственно другим выводам.
Скажите, а насколько развита модель итераторов в Haskell, Erlang, OCaml или другом функциональном языке? Даже иначе поставлю вопрос — в этих языках они (итераторы) вообще есть?
Это, если что, я намекаю на то, что итераторы не совсем ФП.
Это, если что, я намекаю на то, что итераторы не совсем ФП.
Это не ко мне — не один из приведенных не знаю к сожалению настолько глубоко, чтобы коментировать уровень «развития» итераторов. Но судя по тому, что в 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 гораздо экономней.Не зная такие тонкости можно огрести очень много проблем и со скоростью и с ресурсоемкостью. Это наверное одна из причин почему у меня душа не лежит ко всем вами перечисленным языкам. А может я просто не умею их готовить и потому больше «специализируюсь» по питону, тиклю и ко. Хотя тот же тикль например стандартно не имеет конструкций итератора (правда они неплохо строятся на лямбдах и синглтонах). Зато у него много других достоинств.
А вообще, имхо, лучше досконально знать один язык, чем поверхностно много.
Ок. Если вы не поняли — в Haskell нету итераторов. Есть ленивые списки. А в Python нету истинно ленивых списков — есть только бесконечно-итерируемые коллекции. Так что в этом плане Python не намного лучше JS.
Итераторы в Python вещь замечательная. Только вот итераторы одноразовые в том смысле, что обладают побочным эффектом. А генераторы в этом плане еще хуже. Простите, о каком ФП может в таком случае идти речь.
Сравните это, скажем, с приведенным выше классом
То, что в питоне есть итераторы, куча хороших функий для работы с ними — это не делает питон более/менее пригодным для ФП. Это элементы ФП, ни больше, ни меньше.
Сравните это, скажем, с приведенным выше классом
Traversable
. Что же нам теперь, все языки где есть абстракция для обхода коллекции называть функциональными?То, что в питоне есть итераторы, куча хороших функий для работы с ними — это не делает питон более/менее пригодным для ФП. Это элементы ФП, ни больше, ни меньше.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ненормальное функциональное программирование на python