Курс по Python

[iakovk]

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

Наоборот комплимент, речь же не про ПХП

Ну что ж, значит, оскорбление. Спасибо за подтверждение.

[mihaild]

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

но я не думаю, что только на этой концепции, без хранения где-то всех выданных ранее значений удастся реализовать например генератор простых чисел, который на потоках реализуется например так:

Я не знаю этого языка (лисп?), но кажется что вот такой код делает что-то аналогичное:

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

import itertools

def primes():
    yield 2
    yield from filter(is_prime, itertools.count(3, 1))

def is_prime(n):
    return all(map(n.__mod__, itertools.takewhile(lambda p: p * p <= n, primes())))

print(list(itertools.islice(primes(), 30)))
 

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

То есть я не против итераторов-генераторов, но с одной стороны их можно реализовать везде где есть лямбды, и для этого не надо ничего добавлять в язык

В C тоже for тривиально реализуется через while. Но неудобно же.

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

я не вижу их больших преимуществ, но вижу ограничения

Ленивый map можно запускать над бесконечно длинной последовательностью, неленивый нет.

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

непривычно мыслить мапы/фильтры как обертки над такими "значениями без истории"

Это странно - в функциональных языках они именно такие.

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

А теперь вопрос - при чем здесь собственно сам язык, если все это тривиально реализуется на базовых возможностях большинства языков внешней библиотекой?

Потому что чуть удобнее написать (int(x) + 13 for x in sys.stdin if x == x[::-1]), чем явно писать цикл с if, или композицию кучи фильтров и map'ов с использованием лямбд.

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

И в каком смысле в Питоне есть итераторы/генераторы мне пока непонятно.

В питоне есть:
-операторы yield, yield from
-цикл for
-синтаксис генераторных выражений
Сделать конструкции, подобные этим, дополнительной библиотекой нельзя.
Кроме того, в питоне есть модуль builtins, все имена из которого импортированы в глобальное пространство имен по умолчанию. В нем есть функции next и iter и класс StopIteration, на которые завязаны конструкции выше. Эти функции и класс можно реализовать самостоятельно, не ссылаясь на готовые (но встроенные операторы всё равно будут использовать встроенные версии, и заставить их использовать другие нельзя).

[_Ivana]

mihaild как всегда спасибо за изложение. Вопросов еще много, но пока ограничусь одним - ваш код выше (генератор простых чисел) где и как хранит все ранее полученные значения? Ведь генератор primes их не помнит, а takewhile обращается к ним?

[mihaild]

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

где и как хранит все ранее полученные значения?

На лету перегенерирует. Вызов primes() создает новый генератор, независимый от предыдущих.

[_Ivana]

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

[mihaild]

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

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

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

[arseniiv]

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

А теперь вопрос - при чем здесь собственно сам язык, если все это тривиально реализуется на базовых возможностях большинства языков внешней библиотекой?

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

С iterable сам язык тоже при чём — при том, что упомянутые мной (вот уже даже не только) циклы for … in используют этот API в определении собственной семантики. Вы предложили ложную дилемму включать в язык стандартную библиотеку или нет целиком, а никто не заставляет целиком. Можно упоминать только некоторые вещи из неё, и то лишь со стороны интерфейса и ограничений на их поведение, без включения в описание конкретного кода.

-- Сб июн 16, 2018 01:26:08 --

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

Точно так же монады не являются частью Хаскелл, хотя для них там даже синтаксис свой есть в ядре.

Это смотря в каком режиме компилируем. Если просто так, то синтаксис использует методы класса именно Monad. Если с расширением RebindableSyntax, любые >>= и >>, которые сейчас видны.

[_Ivana]

Помните анекдот про Ежика? "Мужики, я вам изоленту принес!" (С) Впервые посидел с сабжем - настрогал кустарные бесконечные потоки с ленивыми вычислениями на них с кучей примеров - из второй главы того самого СИКПа про потоки, если надо - приведу остальные (интегрирование степенных рядов, вычисление Пи и т.п.). На лямбдах, один класс добавил - но он необязательный, одних лямбд было бы достаточно, только более громоздко писался бы код. Но даже на этих примерах очевидно, что все работает. С генераторами такая же ситуация - их еще проще реализовать на подобных абстракциях. Продолжаю не понимать зачем они в ядре языка

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

# волшебная троица
def cons(x, y): return (x,y)
def car(l): return l[0]
def cdr(l): return l[1]

# объект-обертка для мемоизированных ленивых вычислений
class Lazy:
  def __init__(self, expr):
    self.expression = expr
    self.calculated = False
    self.rezult = False
  
  def getvalue(self):
    if not self.calculated:
      self.rezult = self.expression()
      self.calculated = True
    return self.rezult

# хвост потока
def stail(s):
  t = cdr(s)
  if callable(t):
    return t()
  elif isinstance(t, Lazy):
    return t.getvalue()
  else:
    return t

# потоковые аналоги списковых функций

def stake(n, l):
  r = []
  while n>0:
    r.append(car(l))
    l = stail(l)
    n = n-1
  return r

def smap(f, s): return cons(f(car(s)), Lazy(lambda: smap(f, stail(s))))

def sfilter(f, s):
  if f(car(s)):
    return cons(car(s), Lazy(lambda: sfilter(f, stail(s))))
  else:
    return sfilter(f, stail(s))

def szipwith(f, a, b):
  return cons(f(car(a), car(b)), Lazy(lambda: szipwith(f, stail(a), stail (b))))

def ssum(a,b): return szipwith(lambda x,y: x+y, a, b)

# тестовые примеры

n = 50

print("первые {} натуральных чисел:".format(n))
def intfrom(n): return cons(n, Lazy(lambda: intfrom(n+1)))
nats = intfrom(1)
print(stake(n, nats))

print("первые {} членов потока ряда Фибоначчи (НЕ экспоненциальный расчет):".format(n))
def fibgen(a,b): return cons(a, Lazy(lambda: fibgen(b, a+b)))
fibs = fibgen(0,1)
print(stake(n,fibs))

print("первые {} членов потока ряда Фибоначчи (мемоизированный экспоненциальный расчет):".format(n))
fibsexp = cons(0, cons(1, Lazy(lambda: ssum(stail(fibsexp), fibsexp))))
print(stake(n,fibsexp))

print("первые {} четных чисел:".format(n))
evens = sfilter(lambda x: x%2 == 0, intfrom(0))
print(stake(n, evens))

print("первые {} простых чисел через решето Эратосфена:".format(n))
def sieve(s):
    r = sfilter(lambda x: x % car(s) != 0, stail(s))
    return cons(car(s), Lazy(lambda: sieve(r)))
primesErat = sieve(intfrom(2))
print(stake(n, primesErat))

print("первые {} простых чисел через гипотезу Бертрана:".format(n))
def primesBert(): return cons(2, Lazy(lambda: sfilter(isprime, intfrom(3))))
def isprime(n):
    def iter(ps):
      if car(ps)*car(ps) > n: return True
      elif n % car(ps) == 0: return False
      else: return iter(stail(ps))
    return iter(primesBert())
print(stake(n, primesBert()))

print ("частичные суммы натурального ряда:")
def partialsums (s):
  def go(a, s): return cons(a+car(s), Lazy(lambda: go(a+car(s), stail(s))))
  return go(0, s)
print(stake(50, partialsums(intfrom(1))))

print("первые {} чисел Хэмминга:".format(n))
def merge(a, b):
  if   car(a) < car(b): return cons(car(a), Lazy(lambda: merge(stail(a), b)))
  elif car(a) > car(b): return cons(car(b), Lazy(lambda: merge(a, stail(b))))
  else:                 return cons(car(a), Lazy(lambda: merge(stail(a), stail(b))))
def sscale (k, s): return smap(lambda x: k*x, s)
hamm = cons(1, Lazy(lambda: merge(sscale(2,hamm), merge(sscale(3,hamm), sscale(5, hamm)))))
print(stake(n, hamm))
 

результаты:

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

первые 50 натуральных чисел:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
первые 50 членов потока ряда Фибоначчи (НЕ экспоненциальный расчет):
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049]
первые 50 членов потока ряда Фибоначчи (мемоизированный экспоненциальный расчет):
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049]
первые 50 четных чисел:
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98]
первые 50 простых чисел через решето Эратосфена:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229]
первые 50 простых чисел через гипотезу Бертрана:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229]
частичные суммы натурального ряда:
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275]
первые 50 чисел Хэмминга:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240, 243]

запустить и проверить можно на реплите: https://repl.it/

[mihaild]

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

Продолжаю не понимать зачем они в ядре языка

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

Ваш код, подозреваю, работает заметно медленнее аналога, использующего встроенные средства.

Кстати, почему вы не спрашиваете, зачем в языке встроенный тип int, например, и даже сразу поддержка арифметики с ним? Ведь его тоже несложно воспроизвести такими средствами.

[arseniiv]

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

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

Вы рассматривали ситуацию, когда yield не последний оператор в блоке? Я не зря сопрограммы упоминал, после возврата элемента при запросе следующего выполнение продолжится с места после yield. Так же ведущий себя код без yield будет менее прозрачным, особенно если эти операторы были погребены во много разных управляющих конструкций — реразрезать это всё правильно станет вообще той ещё задачей.

[_Ivana]

mihaild Хорошо, аргумент про заметно медленнее принимается, хотя Питон и так не блещет скоростью и не для этого создавался, но сравнительные замеры можно провести. Ваш предыдущий не мемоизированный код на встроенных средствах, подозреваю, проиграет. Если интересно, можете написать примеры мемоизированного кода для представленных задачек, как раз сравним.

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

3-ю тему насчет того, что считать частью языка а что нет, я не планировал развивать (лучше в другом месте и точно не со мной (С)), но отметившиеся выше участники почему-то сочли ее достойной обсуждения.

arseniiv нет, не рассматривал, даже не подозревал такой возможности у встроенных питонных генераторов. В таком случае соглашусь, что оснований для их впиливания в ядро достаточно.

[mihaild]

А что такое "ядро языка"?
В питоне есть модуль builtins и набор ключевых слов, часть из которых связана с объектами из этого модуля. Плюс есть еще всякие синтаксические конструкции - например, списковые и генераторные выражения.
Полное описание грамматики - https://docs.python.org/3/reference/grammar.html.
Что из этого считается "ядром языка", и зачем вообще это понятие нужно?

Имеющиеся конструкции не независимы - многие из них можно воспроизвести друг через друга. Например, вместо всех видов циклов можно ограничиться while True и break, а вместо assert писать if и руками кидать AssertionError. Но зачем?

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

Если интересно, можете написать примеры мемоизированного кода для представленных задачек, как раз сравним.

Не собираюсь. Если писать генератор чисел Фибоначчи, то питонично это делать в императивном стиле:

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

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

И это будет работать существенно быстрее, чем любые рекурсивные варианты.

Несмотря на то, что у питона с производительностью всё плохо, есть много задач, в которых его сейчас использовать можно, а если замедлить еще в 10-100 раз - то станет нельзя.

[_Ivana]

ЗЫ кстати, насчет заметно медленнее - слегка доработанный код поиска простых:

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

def thru2from(n): return cons(n, Lazy(lambda: thru2from(n+2)))
 
n = 5000
 
print("первые {} простых чисел через гипотезу Бертрана:".format(n))
primesBert = cons(2, Lazy(lambda: sfilter(isprime, thru2from(3))))
def isprime(n):
    l = primesBert
    while car(l)*car(l) <= n:
      if n % car(l) == 0: return False
      l = stail(l)
    return True
print(stake(n, primesBert))

выдает первые 5000 значений за 0.4s - и это вместе с преобразованием результата в список и выводом его на экран. Имхо, вполне неплохо для наколенных велосипедных потоков. Пруф - https://ideone.com/9OahaQ

-- 16.06.2018, 03:25 --

mihaild в сообщении #1320300 писал(а):

Не собираюсь.

Ваше право Спасибо и за то что выдали.

[kotenok gav]

kotenok gav в сообщении #1319321 писал(а):

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

вы выстраиваете программу курса (возможно, основываясь на авторитетных учебниках, не только лишь на своей голове) и посдедовательно излагаете её по главам/параграфам/темам. При этом вы излагаете основной материал и, возм., предлагаете задачи для самостоятельного решения, другие искушённые в данном предмете участники скромно вам помогают, а те, кому интересно именно обучение, задают тупые вопросы, предлагают свои решения задач и просят подсказок. Программа должна быть выстроена также и по времени. E. g., есть глава «Обзор основных типов данных». На её обсуждение отводится, скажем, неделя. После этого объявляется следующая глава, а обсуждение предыдущей главы в этом топике прекращается. Как-то так. Это если мы всё ещё хотим оставить топик с его текущим названием;

Попробую...

Первая глава. Строки, числа, их преобразования и ввод с выводом.
Содержимое будет к моему вечеру...

[FomaNeverov]

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

выдает первые 5000 значений за 0.4s - и это вместе с преобразованием результата в список и выводом его на экран.

Ну и скорости у вас...