Комментарии / Профиль lightln2 / Хабр

Oleg T@lightln2

программист

Рейтинг

Подписчики

ПрофильСтатьи6ПостыНовостиКомментарии166

HashLife на питоне

lightln2 10 часов назад

Берем длинную палку длинной L шириной 1

да, вы правы.

Кстати, если вот как вы там обобщаете на окрестность p x p, то там скорость света вообще может быть p/2 и, похоже, периметр надо будет делать еще больше.

вроде, не надо: для $p^{k+1} \times p^{k+1} \to p^k \times p^k$ за k шагов скорость света . Чтобы перейти $p^k \to p^{k+1}$ , у нас есть периметр шириной $(p^{k+1} - p^k) / 2$ клеток, то есть, мы можем сделать $\frac{ (p^{k+1} - p^k) / 2 } {(p-1)/2} = p^k$ шага, именно это и делается, если взять массив $(2p-1) \times (2p-1)$ , положить в центр узел $p^k \times p^k$ и сделать один этап эволюции.

HashLife на питоне

lightln2 11 часов назад

Как это делается для дерева 2x2 вообще? В вашей реализации выше я такой обработки не нашел. Кажется, можно поместить состояние в центр массива 3x3 и сделать 4 эволюции блоков 2x2 и получить 4 квадранта ответа

Тут я, похоже, ошибся: я хотел упростить, и корень $s^k \times s^k$ увеличиваю дважды до $s^{k+2}$ , и делаю ему evolve, и проблема в вашем агрументе про скорость света. Тут оно работает, потому что живые клетки в стандартных правилах “жизни” не могут двигаться быстрее, чем на T/2 клеток за T шагов, поэтому в корне всегда достаточно пустого периметра. Но для произвольного автомата, вы правы, поле может разрастить быстрее.

Поэтому, видимо, в общем случае надо делать последний этап в эволюции:

Для 3x3: 9x9 -> 7x7 -> 5x5 -> 3x3, нужен один этап 5x5 -> 3x3
для 2x2: 4x4 -> 3x3 -> 2x2, нужен один этап 3x3 -> 2x2
для $p \times p$ : один этап $2p - 1 \times 2p - 1 \to p \times p$

то это упрощает код

Интересно, я в этом направлении не думал. А у вас есть код посмотреть? Я пытался делать мапу 0 -> 0, 1 -> 1, там немного упрощается база рекурсии, но не сильно.

HashLife на питоне

lightln2 13 часов назад

Я поразмышлял на досуге, тут вообще получается интересно.

Рассмотрим обобщенный клеточный автомат, у которого состояние клетки зависит от целой окрестности $p \times p$ , p = 3,5,7,… нечётно (в частном случае, может быть обычный автомат, в котором мы ходим сразу на шагов). Тогда тот же подход позволяет использовать $p \times p$ -дерево, с листом $1 \times 1$ , и эволюцией поля в этапов

$p^2 \times p^2 \to (p^2 - (p-1)) \times (p^2 - (p-1)) \to (p^2 - 2(p-1)) \times (p^2 - 2(p-1)) \dots \to p \times p$

Тогда эволюция узла будет $p^k \times p^k \to p^{k-1} \times p^{k-1}$ за $p^{k-1}$ шагов.

Но также мы можем поменять размер листа $1 \times 1 \to d \times d$ , тогда база эволюции будет $(p-1+d) \times (p-1+d) \to d \times d$ . Если мы подберем d так, чтобы было маленькое и целое, то мы можем сделать эволюцию в $s \times s$ дереве, узла $s^kd \times s^kd \to s^{k-1}d \times s^{k-1}d$ за $s^{k-1}$ шагов. То есть, мы разменяли часло шагов на размер узла и сложность его эволюции.

Альтернативно, мы можем сделать s степенью маленького целого, тогда можно уменьшить размер узла. Например, вместо $4 \times 4$ -дерева можно взять квадродерево, но в эволюции раскрывать не два уровня вложенности, а четыре. То есть, мы разменяли число шагов и сложность эволюции на размер узла.

Например, возьмем - стандартную окрестность. Тогда стандартная эволюция в $3 \times 3$ -дереве с листом $1 \times 1$ - мой вариант, или, если возьмем , будет эволюция в квадродереве с листом $2 \times 2$ - классический hashlife!

Если взять , то есть варианты:

$5 \times 5$ -дерево, лист $1 \times 1$ ,
$3 \times 3$ -дерево, лист $2 \times 2$ ,
квадродерево, лист $3 \times 3$ .

Для варианты:

$7 \times 7$ -дерево, лист $1 \times 1$ ,
$4 \times 4$ -дерево, лист $2 \times 2$ (можно использовать квадродерево, и раскрывать 4 уровня),
$3 \times 3$ -дерево, лист $3 \times 3$ ,
квадродерево, лист $6 \times 6$ .

В общем, в этом подходе, вариант $3 \times 3$ (и $p \times p$ в общем случае) является “естессвенным”, а hashlife получается как размен скорости эволюции на размер дерева и сложности шага эволюции. Было бы интересно провести анализ, но мне кажется, если все учесть, то асимптотически все варианты будут одинаковы.

Говорят, спортивное программирование портит код. Почему я с этим не согласен

lightln2 17 июл в 09:00

Бизнес разный бывает. В гугле/яндексе есть департаменты, разрабатывающие новые технологии, в high-frequency trading часто берут исключительно по успехам на олимпиадах. Кроме бизнеса бывает еще опен-сорс и research-проекты, для которых олимпиадный опыт более релевантен, чем бизнес-опыт. Конечно, таких мест в процентном соотношении мало, но туда трудно пробиться без олимпиадного опыта.

HashLife на питоне

lightln2 17 июл в 06:40

Как у вас, надо будет всех внуков корня квадро-дерева выписать в квадрат 4x4

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

hashlife3x3

hashlife2x2

Но все равно мне вариант с 3x3 кажется интуитивно более понятным.

HashLife на питоне

lightln2 16 июл в 21:41

Это сильно эффективнее вашего варианта со сторонами из степени 3.

Эффективность зависит только от количества разных узлов. Насколько я понимаю, ваши вычисления касаются случайной популяции, при которой количество узлов экспоненциально, и hashlife работает медленно. В реальности он хорошо работает на регулярных структурах, и там все зависит от того, как именно они регулярны. Если есть много структур с симметрией сдвига кратной степерям двойки, то стандартный hashlife будет лучше. Если кратной степеням тройки - то мой вариант.

Откуда вы вообще 3 взяли?

Я делал оба варианта hashlife для версии клеточного автомата (не “жизнь”, но не принципиально), в которой много структур, симметричных относительно сдвига на 3^k клеток, но не на 2^k. Моя версия действительно была быстрее (в пять раз), но что я не ожидал, что реализация будет проще, чем квадродерево. К тому же, мне идея эволюции квадрата 3x3 кажется более естесственной, чем 4x4 - собственно, я и хотел этим поделиться.

Была еще и другая конфигурация, в которой симметрия была фрактальной со сдвигом 2^k. Ожидаемо, там стандартный hashlife работал за логарифм, а мой вариант вырождался в линию.

У меня недостаточно данных, чтобы утверждать, какой из вариантов лучше на практике в среднем. Навскидку, вариант с квадродеревом требует меньше памяти, но вариант с 3x3-деревом легче написать и отладить.

Самовлюблённые числа: когда нарциссизм и бесполезность вдохновляют

lightln2 19 мая в 15:08

С этим сложно поспорить, но можно переформулировать задачу как найти такие $a_1, \dots, a_n < B$ , что

$\sum{B^i a_i} = \sum{a_i^n}$

что является частным случаем диофантовых уравнений! А вообще, статья интересная, спасибо! Не хватает только списка самих чисел.

Структуры данных на практике. Глава 15: Графы и их обход с эффективным использованием кэша

lightln2 11 мая в 21:08

А по теме, есть хорошая лекция от MIT про оптимизацию BFS, с акцентом на многопоточность, но и однопоточные оптимизации тоже раскрываются. Там, кстати, рассказывают, как именно считаются эти cache misses, и как оптимизации их улучшают.

Это все если граф влезает в память. BFS для графов, которые не влезают в память - это отдельный мир, с десятилетиями научных исследований и сотней эзотерических алгоритмов.

Структуры данных на практике. Глава 15: Графы и их обход с эффективным использованием кэша

lightln2 11 мая в 21:00

Что мне больше всего тут непонятно, это как там на графе из 500 вершин и 6000 ребер даже в самой оптимизированной версии насчиталось почти миллион cache misses.

Ну и вообще, я посмотрел в оригинал, он оставляет странное впечатление - товарищ работает с низкоуровневым программированием, пишет книгу аж из 20 глав, в ней все баззворды на своих местах. Но он зациклен на cache misses, и его аргументация местами очень странная. То ли очень неаккуратно написано (при чем тут Radix Tree?), то ли вообще цифры с потолка взяты.

Беззнаковые размеры: пять лет назад мы совершили ошибку

lightln2 10 мая в 08:38

Кажется, автор еще забыл упомянуть, что переполнение знаковых - это undefined behavior в C++, если делать offset/length знаковыми, то это придется как-то чинить.

Но совсем избавляться от беззнаковых тоже кажется не самой лучшей идеей, тогда, как в Яве, придется вводить оператор “>>>” (беззнаковый сдвиг вправо), и будут проблемы с поддержкой форматов хранения, где значения беззнаковые, например, массив uint8.

Но когда корректность важнее скорости, то имхо, знаковые оффсеты и длины массивов кажутся хорошим компромисом: можно вставить дополнительные проверки на неотрицательность при создании массива и обращении к его элементам (в 99% случаев оно не скажется на производительности, так как проверка будет на свободном ALU-порту, и branch prediction тоже отработает параллельно)

В общем, мне нравится подход как в C#, придуманный много лет назад:

длины и оффсеты массивов знаковые, исключения при обращениях out-of-bounds
есть беззнаковые, если нужны, более-менее разумные правила автоматического преобразования
если важно не поймать overflow, есть опциональный checked{} контекст, в котором оно вызовет исключение
Eсли надо выжать последние полпроцента производительности, есть unsafe{} контекст, в котором можно создать массив байт через malloc, и дальше уже с ним извращаться, как душе угодно.

Не бойтесь динамического программирования

lightln2 1 апр в 09:18

Многие, кто работают в гугле/яндексе пишут дп регулярно. Но конкретно

использовать в реальном рабочем процессе

Вы это делаете каждый день, когда выполняете git diff - он основан на алгоритме Майерса, варианте Longest Common Subsequence Problem, являющегося классикой DP!

Игра в угадайку

lightln2 1 апр в 07:15

Спасибо, отличный обзор! Тем не менее, хотел бы указать на потенциально не раскрытые вами подходы:

Теория игр и теорема минимакса - представить задачу как игру, где один игрок выбирает число, не противоречащее предыдущим проверкам, а второй пытается его угадать за минимальное число проверок.
Иммунные алгоритмы - если честно, я мало что при них знаю, но ученые, с ними работающие, утверждают, что это гораздо круче генетических алгоритмов!
Целочисленное Линейное Программирование - вроде должно работать, потому что каждое угадывание задает линейное ограничение (то есть, гиперплоскость в одномерном пространстве)!

Не бойтесь динамического программирования

lightln2 31 мар в 10:02

Я не боюсь, но опасаюсь задач на DP, потому что сложность в деталях:

Как конкретно определять подзадачу (например, на строках - dp[i] - это задача на символе i или на префиксе длины i? Будем задавать базовые условия для всех подстрок в один символ или для только пустой строки?)
Какой брать переход из возможных опций (dp[i] - количество нужных подстрок, заканчивающихся на символе i или принадлежащих префиксу длины i)?
А если еще и надо восстановить оптимальное рещение, то это еще сильнее усложняет реализацию (будем хранить граф переходов? или потом восстановим из таблицы стоимостей?)

Чаще всего все варианты будут работать, но нужна интуиция, чтобы понять какой приведет к самому короткому и понятному коду без ошибок. Если кто-то знает какие-то эвристики, расскажите!

А мое любимое объяснение DP - лекция из цикла MIT “введение в алгоритмы” авторства Эрика Демайна - очень известный в мире computer scienсе чувак, автор структуры Tango Trees и доказавший, что тетрис NP-полон. Он подробно рассказывает именно о том, какие характеристики задачи делают ее dp, и как от них перейти к формуле.

Давайте заглянем в этот самый вайб-код

lightln2 20 мар в 15:19

А потом замкнуть круг - агент генерирует код, линтер выдает ошибки, чтоб агент починил, отдает линтеру... и так до бесконечности
Но скорее всего, уже на первом цикле агент все разломает, что раньше хоть как-то работало

Python Standard Library для спортивного программирования

lightln2 15 мар в 21:55

Еще можно упомянуть крайне полезную библиотеку sortedcontainers с классами SortedList, SortedDict, SortedSet - аналоги multiset, map, set в с++, но, в отличие от них, поддерживающие поиск индекса и по индексу за логарифм.

Ну и, чтоб два раза не вставать, хочется упомянуть "тяжелую артиллерию".

библиотека networkx для работы с графами, умеет ну практически все стандартные алгоритмы на графах.
библиотека Z3-solver, решает задачи в символьном виде, умеет LP, целочисленное LP, 2-SAT, 3-SAT и кучу всего прочего.

Решение задачи с собеседования используя технику Sliding Window на Go

lightln2 10 мар в 17:30

А есть какой-то стандартный шаблон для sliding window, который позволяет для разных задач подставлять реализацию (как, например, с бинпоиском), или там слишком много разных вариаций? Ну, типа

left = 0
for right in range(n):
   add(right)
   while left <= right and not good(): remove(left++)

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

Сравнение двух налоговых служб: ФНС России и IRS США

lightln2 26 фев в 10:36

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

В поисках O(n): как научиться видеть эффективные решения задач

lightln2 19 фев в 20:08

да я уже понял, что зря залез со своим комментарием. Я просто хотел поделиться подходом к решению таких задач, который минимизирует скорость написания и количество ошибок.
Такие задачи - это не ентерпрайз, это либо собеседования, либо соревнования по программированию.
И на хабре, и на реддите многие жалуются, что на собесе не решили задачу, стресс, не хватило времени, запутались в граничных условиях, не нашли ошибку (На контестах тоже частая проблема - не хватает времени на сложные задачи, так как слишком много времени ушло на написание и отлаживание простых). Это нормально - в условиях стресса люди всегда делают больше ошибок, поэтому всегда имеет смысл писаль код максимально близкий к объяснению решения задачи на словах.
Ну и если вы думаете, что это - говнокод, значит вы не видели, как пишут код люди уровня чемпионов ICPC - не потому, что иначе не умеют, а потому, что это более эффективно.

В поисках O(n): как научиться видеть эффективные решения задач

lightln2 15 фев в 10:51

Это, наверно, был риторический вопрос, но я попробую ответить.
Конкретно эта задача, может, и не имеет практического значения, но она является упражнением на поиск второго маскимума(минимума).
Это частный случай поиска k-го максимума (или первых k максимумов). Практическое значение - Вас с помощью этой задачи подводят к алгоритму quick-select (используется много где, например, в статистике для вычисления медианы/перцентилей)
Второе применение - поиск второго максимума/минимума в более сложных объектах. Классическая задача - поиск второго оптимального пути в ациклических направленных графах. Практическое применение - быстрое вычисление оптимальной траектории в вашей сети, если одно из ее ребер удалить (то есть, нарушилась связность между двумя узлами в сети).

В поисках O(n): как научиться видеть эффективные решения задач

lightln2 13 фев в 21:25

что вы понимаете под оптимальными алгоритмами?
обычно это означает "асимптотически оптимальные", но вы имеете в виду, видимо, абсолютное время? тогда перепишите код на c++ и скомпилируйте с -Ofast -march=native и это будет оптимально, так как упрется в пропускную способность памяти (и то не на всех архитектурах, так как иногда в один поток невозможно нагрузить память, надо будет параллелить).
Даже если вы имеете в виду абсолютное время на питоне, то наверняка какой-нибудь numpy.partition будет быстрее, так как выполняется нативно на numpy-массивах. Ну и даже для вашего алгоритма наверняка распараллеливание на несколько потоков его ускорит.

повышение читаемости сомнительно

это стандартный шаблон argmax (одна из полезных функций, отсутствующих в питоне, но присутствующих, например, в numpy) - он обычно легко распознается при чтении, если вам знаком

2 3 ...

8 9