Курс по Python

[arseniiv]

(Оффтоп)

Честно говоря, я не помню, чтобы это было сильно трудно. У меня была уже под рукой реализация на другом языке, и ничего сверхоригинального использовать было не нужно, потому документации хватало вот так. Кстати тут как раз проблема в том, что я тогда не разбирался в юнит-тестах и потому их там нет, а были бы уместны — как раз к коду такого типа (из маленьких чистых классов и функций) они применимы наиболее.

[warlock66613]

Munin в сообщении #1318994 писал(а):

Что плохого в этом коде?

Можно (условно) предположить, что его писал человек, который думает, что Python оптимизит хвостовую рекурсию, то есть при определённых условиях рекурсия разворачивается в цикл. Но на самом деле ничего подобного не происходит: никакой оптимизации хвостовой рекурсии в Python нет.

[Munin]

То есть, рекурсия - это оверхедно? А как же тогда заниматься ФП?

[mustitz]

Munin в сообщении #1319264 писал(а):

ozheredov
Насчёт затрат памяти для кэширования вопрос повис в воздухе. (Понятно, что это $O(N),$ но хотелось бы узнать соотношение затрат по сравнению с питоновским же массивом.)

Python это не язык для достижения максимальной призводительности. Поэтому большинство такими вопросами не заморачивается — главное чтобы было удобно писать. Если ставить вопрос о жесткой многопоточности и выжимании тиков процессора, то, наверное, тут более подойдёт язык Rust.

Попробовал сравнить

Используется синтаксис Python

#!/usr/bin/env python3

import itertools
import tracemalloc
from sympy import isprime

def fibb():
    a, b = 1, 1
    while True:
        yield a
        a, b = b, a+b

tracemalloc.start()

f1, f2 = itertools.tee(fibb())
f1 = itertools.islice(f1, 1000)
f2 = filter(lambda x: isprime(x), f2)
f2 = itertools.islice(f2, 20)

t1 = list(f1)
t2 = list(f2)

snapshot = tracemalloc.take_snapshot()

total = sum([x.size for x in snapshot.statistics('filename', True)])
print(total)
 

печатает 105688

Используется синтаксис Python

#!/usr/bin/env python3

import itertools
import tracemalloc
from sympy import isprime

def fibb(length):
    a, b = 1, 1
    result = []
    for _ in range(length):
        result.append(a)
        a, b = b, a+b
    return result

tracemalloc.start()

f1 = fibb(1000)
f2 = [2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169,
 19134702400093278081449423917, 475420437734698220747368027166749382927701417016557193662268716376935476241,
 529892711006095621792039556787784670197112759029534506620905162834769955134424689676262369,
 1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353,
 3061719992484545030554313848083717208111285432353738497131674799321571238149015933442805665949,
 10597999265301490732599643671505003412515860435409421932560009680142974347195483140293254396195769876129909,
 36684474316080978061473613646275630451100586901195229815270242868417768061193560857904335017879540515228143777781065869]

snapshot = tracemalloc.take_snapshot()

total = sum([x.size for x in snapshot.statistics('filename', True)])
print(total)
 

печатает 84672

[Munin]

Спасибо! В общем, не кошмар.

[_Ivana]

Munin в сообщении #1319365 писал(а):

А как же тогда заниматься ФП?

Очевидно, на более других языках, более подходящих для этого. Питон не про ФП. Царь Гвидон говорил, что ТСО не будет, потому что "неочевидны стектрейсы при отладке", и вообще фильтр/мап/редьюс притянуты для баловства и не аутентичны.

[Aritaborian]

Munin в сообщении #1319365 писал(а):

А как же тогда заниматься ФП?

А вам где-то обещали ФП? Вам соврали. Идите учить WL, там от ФП вас аж тошнить будет. Питон он же не про ФП в основном. То есть, поддерживает парадигму в чём-то, но не в своей основе.

[arseniiv]

Вообще ФП это довольно неопределённый термин, как и ООП, особенно среди современных языков.

[Aritaborian]

Сейчас модно говорить, что современный язык должен поддерживать все парадигмы. Это с одной стороны. А эта точка зрения приводит ко второй стороне: фиг его знает, что значат эти парадигмы по отдельности. Определения расплываются и нельзя определённо говорить, что это так уж плохо.

[arseniiv]

Да, когда они были предложены каждая по отдельности в первый раз, те языки уже давно канули в Лету. Например, где Модула? Где Self? На смолтоке, правда, пишут, и на некоторых близких к архаичному состоянию диалектах лиспа, ннно…

А некоторые парадигмы вообще неконкретны: например, декларативное программирование имеет в обычных классификациях подтипом функциональное. Притом это значит, что и последнее (или ООП) может быть полезным расщепить.

С третьей стороны я лично вообще не очень понимаю, в чём смысл говорить о парадигмах конкретно, в моих обсуждениях языков они не приносили пользы даже когда появлялись. Говорить об инкапсуляции куда более полезно — у некоторых языков с ней откровенно плохо, другие имеют необходимый минимум, третьи радуют гибкостью. Некоторые особенности языков хорошо играют вместе с другими, но таких наборов множество, они обычно более-менее мелкие и сочетаемость бывает разной степени, тут нет трёх-четырёх классов с жёсткими границами.

P. S. Сегодня какой-то день оффтопа.

[_Ivana]

Никогда не пробовал писать на Питоне, но сейчас решил сравнить его скорость (только честно, скорость именно Питона, без вызова подкапотных сишных и фортрановских либ) с некоторой реализацией другого интерпретируемого скриптового языка (безо всяких джитов, оптимизаций, векторизаций и прочего). Например, если взять неоптимальную экпоненциальнорекурсивную функцию чисел Фибоначчи, Питон рассчитывает ее значение от 32 примерно за 0.85 сек, другой за 4.2 сек, то есть в 5 раз медленнее. До сишки всем далеко, конечно, но в своем классе не сказать что разница на порядки.

(Оффтоп)

mustitz в сообщении #1319254 писал(а):

Например, мы хотим получить список из 10 первых простых чисел Фиббоначчи.

Пользуясь случаем, накидал у себя, с парой вариантов создания потока

(defn is-prime (n)
     (defn go (i) cond
         (> (* i i) n) true
         (= 0 (mod n i)) false
         (go (+ 1 i)))
     (go 2))

(def n 12)

(defn fibgen (a b) (s-cons a (fibgen b (+ a b))))
(def fibs (fibgen 0 1))
(print "Первые " n " простых чисел Фибоначчи" \n)
(print "вариант 1: " (s-take n (s-filter is-prime fibs)) \n)

(def fibsexp (cons 0 (s-cons 1 (s-sum (s-tail fibsexp) fibsexp))))
(print "вариант 2: " (s-take n (s-filter is-prime fibsexp)) \n)

 => Первые 12 простых чисел Фибоначчи
вариант 1: (0 1 1 2 3 5 13 89 233 1597 28657 514229)
вариант 2: (0 1 1 2 3 5 13 89 233 1597 28657 514229)

[Aritaborian]

_Ivana в сообщении #1319479 писал(а):

с некоторой реализацией другого интерпретируемого скриптового языка (безо всяких джитов, оптимизаций, векторизаций и прочего)

Вы либо трусы наденьте, либо крестик снимите. Какого языка?

[Pphantom]

Aritaborian в сообщении #1319481 писал(а):

Какого языка?

Если не ошибаюсь, это Clojure.

[_Ivana]

Clojure считает это за 0.47 секунд. И она не чисто интерпретируемая, она компилируется в Джава байт-код.
А выше я взял одну из своих реализаций лиспа, в данном случае тоже на JVM.

ЗЫ но конечно все эти замеры некорректны - ибо сделаны на разных машинах, и не знаю какую часть времени выполнения занимает поднятие среды исполнения. Но общую примерно-потолочную картину они все-же дают.

[warlock66613]

Munin в сообщении #1319365 писал(а):

А как же тогда заниматься ФП?

Смотря что значит "заниматься". Если речь о практическом использовании (не об учёбе), то очень просто: использовать более высокоуровневые функции — такие, которые в настоящем функциональном языке были бы реализованы через рекурсию, а в python'е - через цикл. Вот «тру-функциональный фибоначчи» на питоне без рекурсии:

Используется синтаксис Python

from itertools import islice, repeat, imap

def ireduce(func, iterable, init=None):
    if init is None:
        iterable = iter(iterable)
        curr = next(iterable)
    else:
        curr = init
    for x in iterable:
        curr = func(curr, x)
        yield curr

def fibb():
  return imap(lambda x: x[0], ireduce(lambda (a, b), _: (b, a + b), repeat(None), (0, 1)))

print list(islice(fibb(), 10))

(Реализация ireduce взята отсюда: Charming Python #b13: The itertools Module.)
(Кстати, посоветованная на первой странице песочница этот код не переваривает.)Это потому что код выше - для устаревшего Python2. Для Python 3 надо так:

Используется синтаксис Python

from itertools import islice, repeat

def ireduce(func, iterable, init=None):
    if init is None:
        iterable = iter(iterable)
        curr = next(iterable)
    else:
        curr = init
    for x in iterable:
        curr = func(curr, x)
        yield curr

def fibb():
  return map(lambda x: x[0], ireduce(lambda x, _: (lambda a, b: (b, a + b))(*x), repeat(None), (0, 1)))

print(list(islice(fibb(), 10)))