Когда я лезу в хаб "ненормальное программирование (извращения с кодом)", я жду извращений с кодом! А не извращений с человеческим языком и ноль кодирования, просто вылили ведро воды.
ну в хаскелле тоже можно отрефакторить так, что оно не будет работать %)
начиная с самого простого foo _ = undefined
благо, полнота по Тьюрингу разрешает писать на хаскелле программы, не достигающие останова (путём выжирания памяти, времени, или просто крешащиеся явным способом).
Если уж хочется "компилируется - следовательно, работает", то нужны языки с тотальными функциями, тот же идрис.
Но вот скажите, кто-нибудь использует идрис в продакшене? Или прототипирует на идрисе, а потом перетаскивает кусочки в хаскелл? Мне просто интересно...
В хаскелле просто нашли способ запихать глобальный синглетон "реальный мир" в простую синтаксическую и семантическую обёрточку - в аргумент с типом, который невозможно случайно создать с нуля или копировать. (И больше ничего с ним делать невозможно, только передавать дальше по цепочке выполнения). А поскольку такой аргумент никому не нужен и только мешает, как синтаксический шум, тут-то нотации работы с монадами (конвеер и особенно do) пригодились.
Можно философски думать об IO как о State, где состояние хранится во внешнем мире, - но это не совсем справедливо. Во-первых, State можно безболезненно копировать, а мир - нельзя. Во-вторых, State неизменно, если его не менять, а мир меняется сам по себе.
Ну и ко всему прочему, монады бывают синглетонного вида "одно значение плюс всякая аугментация", а бывают множественного "набор данных, к которым надо приделать map/reduce" - собственно, список и множество суть монады. Это, конечно, вносит хаос в головы... Где список и где реальный мир. А всего-навсего - у них общее то, что с ними можно орудовать, как с разными моноидами в эндофункторах.
Довольно куцее исследование! Я давным-давно видел статью (вот только не помню, где, - может быть, и на хабре) о том, какие РАЗНЫЕ способы для построения сколь угодно широких конструкций из кирпичей.
Гармонический ряд - это, внезапно, неэффективный способ. Хотя и выглядящий достаточно парадоксально, ну и просто как proof of concept.
Строить ведь можно, не только смещая кирпичи друг от друга, но и прижимая их сверху противовесами.
(Извините, сейчас нарисовать не могу, чтоб проиллюстрировать идею).
Ну вот самый банальный пример. Ромб. Его ширина линейно растёт от высоты, или как квадратный корень - от количества кирпичей. Это всяко лучше, чем гармонический мостик.
Если противовес делать больше высоким, чем широким в противоположную от обрыва сторону, то можно строить фигуры, похожие на волшебную лампу Аладдина - с очень длинным носиком.
То есть, При N = 2**16 мы ещё не получим тут переполнения, а при 2**16 + 1 уже получим.
Отсюда мораль: нужно делать две ветви алгоритма: быстрый, который только компенсирует underflow, и более медленный, который компенсирует overflow в компенсаторе.
Причём медленный работает на больших наборах данных, и значит, надо там как-то поиграться, чтобы делать эту компенсацию не на каждый такт.
Например, можем избавиться от проверки в пользу цикла. (Как, собственно, это сделали с underflow). Решим уравнение (N-1)*P < 2**32. И нарежем весь набор остатков на блоки по P штук. Причём для удобства (и для распараллеливания) можем выбирать P как степень 2. Последний блок будет неполным, конечно.
N <= 2**16 -- P = 2**16
N <= 2**17 -- P = 2**15
...
N <= 2**31 -- P = 2
N <= 2**32 -- P = 1
Что, кстати, как бы намекает нам, что в последних случаях алгоритм выродится - у нас будет сплошное underflow и сплошные компенсации.
Не могу сказать, что это решение оптимально: тут мы 13 раз делаем забег по одному числу!
Лучше уж поступить следующим образом.
Каждое число является линейной функцией для любых предыдущих: была цепочка L, пририсовали цепочку M, получили N = L * 10^w + M, где w - длина M.
А теперь то же самое по модулю: n = l * f + r
int dp[13] = {1 /* , 0... */};
for (const string& x : numbers) {
// один раз вычисляем наш линейный оператор
int f = 1, r = 0;
for (char c : x) {
f = f * 10 % 13;
r = (r * 10 + c - '0') % 13
}
// затем применяем его к предыдущему слою данных
int next[13] = {/* 0... */};
for (int l = 0; l < 13; ++l) {
int n = (l * f + r) % 13;
next[n] += dp[l];
}
// и порождаем новый слой
for (int n = 0; n < 13; ++n) {
dp[n] = (dp[n] + next[n]) % 1000000007;
}
}
return dp[0];
Когда речь зашла про христианство, я было подумал, что эксель наловчился вести сквозную нумерацию абзацей библии или там псалтиря. Кто бы мог подумать, что 10:75 - это десять часов семьдесят пять минут!!! 43 мартобря.
В случае Free монады начальными элементами будут, грубо говоря, простые типы, а операциями - рекурсивные типы данных, являющиеся функторами (не будем вдаваться в подробности, поскольку для дальнейшего это не имеет значения). Поскольку функторы обладают приятным свойством ассоциативности (не важны скобки в композиции), то их можно спокойно комбинировать, а значит получать монадические свойства на халяву (free в другом смысле).
Это очень плохая идея - использовать перегруженные термины, да ещё и походя.
В хаскелле функтором называют одно, в камле - другое. Как понять, о чём речь идёт именно здесь? В статье, ясен пень, теоркатовско-хаскелловские...
Ещё один not-invented-here псевдоязык. Зачем? Чтобы кровь из глаз пошла?
Взяли бы синтаксис хаскелла и не мучали бы людей. Или, если на то пошло, взяли бы синтаксис окамла. Вот наверняка же одиночные апострофы - это оттуда прилетело?
Чайники вида номер 5 выпускались в постсоветское время. Точнее, я видел такие гибриды 1 и 5: полусфера, но ручка не сверху над крышкой, а сбоку под 45 градусов. Удобство среднее, потому что там начинаются ещё развлечения с крышкой, открывать которую ручка мешает.
Никто не говорит, что ручка должна утоньшаться к концу, - это просто набросок же.
Хотя заварочные чайники из глины-керамики-фарфора, конечно, будут с утоньшающейся ручкой.
Для полноты примера надо было бы вот такое сделать
def outer():
def inner():
fs = []
for I in range(3):
fs.append((lambda i: (lambda x : [x,i,I,O,G]))(I))
I = 'innervar'
return fs
fs = inner()
O = 'outervar'
return fs
fs = outer()
G = 'globalvar'
O = 'hacked' # введём глобальные переменные
I = 'hacked' # в ТЩЕТНОЙ надежде на конфликт
i = 'hacked' # с именами внутри лямбды
print([f('xxx') for f in fs])
del G
print([f('xxx') for f in fs]) # NameError: name 'G' is not defined
I обнаружена транслятором питона как локальная переменная, будет связана с контекстом функции inner.
O - нелокальная переменная (можно не писать nonlocal, поскольку мы не присваиваем, а значит, неоднозначности синтаксиса нет), будет связана с контекстом функции outer
G по умолчанию - глобальное имя, будем искать его каждый раз ровно в момент обращения
i - локальная переменная-аргумент внешней лямбды, будет связана с контекстом её вызова (куда подставлено конкретное значение I)
хорошие гороскопы этим и отличаются - что, если нет каких-то предустановок, то подойдут все типы
Так-то Нюша - это уменьшительное от Анна. Так что именно Нюша и пришла %)))
кто кого тут наймёт, ещё вопрос... и даже не вопрос.
Когда я лезу в хаб "ненормальное программирование (извращения с кодом)", я жду извращений с кодом! А не извращений с человеческим языком и ноль кодирования, просто вылили ведро воды.
Не надо так, пожалуйста?
ну в хаскелле тоже можно отрефакторить так, что оно не будет работать %)
начиная с самого простого foo _ = undefined
благо, полнота по Тьюрингу разрешает писать на хаскелле программы, не достигающие останова (путём выжирания памяти, времени, или просто крешащиеся явным способом).
Если уж хочется "компилируется - следовательно, работает", то нужны языки с тотальными функциями, тот же идрис.
Но вот скажите, кто-нибудь использует идрис в продакшене? Или прототипирует на идрисе, а потом перетаскивает кусочки в хаскелл? Мне просто интересно...
В хаскелле просто нашли способ запихать глобальный синглетон "реальный мир" в простую синтаксическую и семантическую обёрточку - в аргумент с типом, который невозможно случайно создать с нуля или копировать. (И больше ничего с ним делать невозможно, только передавать дальше по цепочке выполнения). А поскольку такой аргумент никому не нужен и только мешает, как синтаксический шум, тут-то нотации работы с монадами (конвеер и особенно do) пригодились.
Можно философски думать об IO как о State, где состояние хранится во внешнем мире, - но это не совсем справедливо. Во-первых, State можно безболезненно копировать, а мир - нельзя. Во-вторых, State неизменно, если его не менять, а мир меняется сам по себе.
Ну и ко всему прочему, монады бывают синглетонного вида "одно значение плюс всякая аугментация", а бывают множественного "набор данных, к которым надо приделать map/reduce" - собственно, список и множество суть монады. Это, конечно, вносит хаос в головы... Где список и где реальный мир. А всего-навсего - у них общее то, что с ними можно орудовать, как с разными моноидами в эндофункторах.
Довольно куцее исследование! Я давным-давно видел статью (вот только не помню, где, - может быть, и на хабре) о том, какие РАЗНЫЕ способы для построения сколь угодно широких конструкций из кирпичей.
Гармонический ряд - это, внезапно, неэффективный способ. Хотя и выглядящий достаточно парадоксально, ну и просто как proof of concept.
Строить ведь можно, не только смещая кирпичи друг от друга, но и прижимая их сверху противовесами.
(Извините, сейчас нарисовать не могу, чтоб проиллюстрировать идею).
Ну вот самый банальный пример. Ромб. Его ширина линейно растёт от высоты, или как квадратный корень - от количества кирпичей. Это всяко лучше, чем гармонический мостик.
Если противовес делать больше высоким, чем широким в противоположную от обрыва сторону, то можно строить фигуры, похожие на волшебную лампу Аладдина - с очень длинным носиком.
Обозначу количество за N.
Если N = 0 или 1, тут всё тривиально.
Если N < H, сейчас найдём этот порог, то sum(xi / N) + sum(xi % N) / N работает.
Если больше - то происходит переполнение.
Найдём худший случай: sum(xi % N) < sum(N-1) = (N-1)*N.
То есть, При N = 2**16 мы ещё не получим тут переполнения, а при 2**16 + 1 уже получим.
Отсюда мораль: нужно делать две ветви алгоритма: быстрый, который только компенсирует underflow, и более медленный, который компенсирует overflow в компенсаторе.
Причём медленный работает на больших наборах данных, и значит, надо там как-то поиграться, чтобы делать эту компенсацию не на каждый такт.
Например, можем избавиться от проверки в пользу цикла. (Как, собственно, это сделали с underflow). Решим уравнение (N-1)*P < 2**32. И нарежем весь набор остатков на блоки по P штук. Причём для удобства (и для распараллеливания) можем выбирать P как степень 2. Последний блок будет неполным, конечно.
N <= 2**16 -- P = 2**16
N <= 2**17 -- P = 2**15
...
N <= 2**31 -- P = 2
N <= 2**32 -- P = 1
Что, кстати, как бы намекает нам, что в последних случаях алгоритм выродится - у нас будет сплошное underflow и сплошные компенсации.
Видео недоступно
Это видео с ограниченным доступом.
Я дуже балован сайтом leetcode на уровне hard, поэтому эта задачка показалась лёгкой.
Разве что сама формулировка изящная и забавная, то есть, это больше про искусство задавать задачки, чем про решать их.
Не могу сказать, что это решение оптимально: тут мы 13 раз делаем забег по одному числу!
Лучше уж поступить следующим образом.
Каждое число является линейной функцией для любых предыдущих: была цепочка L, пририсовали цепочку M, получили N = L * 10^w + M, где w - длина M.
А теперь то же самое по модулю: n = l * f + r
А зачем прогрессия?
По условию: каждый (n) пожал руку каждому, кроме себя (n-1), при этом "он" и "ему" учитываются как одно рукопожатие.
n*(n-1)/2 = 78
И таки да, (n-1)^2 < n(n-1) < n^2, находим ближайшие квадраты - 144 и 169 и проверяем, что ответ подошёл.
Если все волокна (или единственное) крутят спинлок "пока время не достигло таймаута", - это просто разогрев процессора.
По-хорошему, нужен планировщик с вот таким апи:
yield() - просто отдать управление, у текущего волокна состояние из "active" переходит в "ready"
sleep_until(timestamp) - пусть планировщик сам вернёт в список ready, когда надо будет
sleep_for(duration) = sleep_until(now + duration)
А потом туда же прикрутить разные условия - poll/select, condition variable, и т.п.
Когда речь зашла про христианство, я было подумал, что эксель наловчился вести сквозную нумерацию абзацей библии или там псалтиря. Кто бы мог подумать, что 10:75 - это десять часов семьдесят пять минут!!! 43 мартобря.
Моисей вообще клялся на Торе.
Так что предлагаю развить эту ДИСКуссию.
Это очень плохая идея - использовать перегруженные термины, да ещё и походя.
В хаскелле функтором называют одно, в камле - другое. Как понять, о чём речь идёт именно здесь? В статье, ясен пень, теоркатовско-хаскелловские...
Ещё один not-invented-here псевдоязык. Зачем? Чтобы кровь из глаз пошла?
Взяли бы синтаксис хаскелла и не мучали бы людей. Или, если на то пошло, взяли бы синтаксис окамла. Вот наверняка же одиночные апострофы - это оттуда прилетело?
Чайники вида номер 5 выпускались в постсоветское время. Точнее, я видел такие гибриды 1 и 5: полусфера, но ручка не сверху над крышкой, а сбоку под 45 градусов.
Удобство среднее, потому что там начинаются ещё развлечения с крышкой, открывать которую ручка мешает.
Никто не говорит, что ручка должна утоньшаться к концу, - это просто набросок же.
Хотя заварочные чайники из глины-керамики-фарфора, конечно, будут с утоньшающейся ручкой.
Для полноты примера надо было бы вот такое сделать
выведет
Пояснение:
I обнаружена транслятором питона как локальная переменная, будет связана с контекстом функции inner.
O - нелокальная переменная (можно не писать nonlocal, поскольку мы не присваиваем, а значит, неоднозначности синтаксиса нет), будет связана с контекстом функции outer
G по умолчанию - глобальное имя, будем искать его каждый раз ровно в момент обращения
i - локальная переменная-аргумент внешней лямбды, будет связана с контекстом её вызова (куда подставлено конкретное значение I)