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

Oleg T@lightln2

программист

0,1

Рейтинг

Подписчики

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

Сортировка слиянием, часть 2

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

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

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

Сколько всего строк на 100GB - миллиард по 100B или миллион по 100KB?
Какой у алгоритма Read/Write amplification - сколько байт всего нужно прочитать и записать за время его работы
Не очень понял, зачем нужен zstd, если строки случайные, и данные не сжимаются. Также, зачем дедупликация, если дубликатов совсем мало?
Сколько времени занимает генерация ключа для сравнения, и сколько раз он генерится - это может быть как самая медленная операция, так и самая быстрая, если в .NET есть happy path для ascii-строк
Сколько времени занимает само сравнение, и сколько таких сравнений? Есть ли смысл их ускорять (используя SIMD или radix sort)?

Тогда будет понятно, где узкое место, в зависимости от оборудования.

Как я решал leetcode задачу

lightln2 вчера в 19:04

По-моему, тут рекурсия сама собой получается:

Рассмотрим первую скобку: очевидно, она открывающая. Где будет ее закрывающая скобка? В какой-то позиции через четное число скобок от нее. Также очевидно, что между ними, а также после закрывающей скобки - тоже правильные скобочные последовательности длины 2i и 2(n-i-1).

Сгенерим все такие последовательности рекурсивно.

Кстати, рекуррентная формула для чисел каталана из этого принципа и выводится.

@cache
def generate(n):
    if n == 0: return [""]
    result = []
    for i in range(n):
        for x in generate(i):
            for y in generate(n - i - 1):
                result.append(f"({x}){y}")
    return result

Математики бойкотируют новые ИИ‑открытия от компании OpenAI

lightln2 10 окт в 08:25

А мне вот интересно, не будет ли в математике как в программировании - когда математикам уровня Терренса Тао беспокоиться не о чем, а вот junior-аспирантам будет сложно, так как обычно начинают карьеру, помогая допиливать теории своих научных руководителей - мало того, что тем теперь будет быстрее взять LLM для этого, так и аспиранту будет неопубликоваться, потому что то, что он решит, уже будет опубликовано типа в github/openai/problem-100500.

Математики бойкотируют новые ИИ‑открытия от компании OpenAI

lightln2 10 окт в 08:10

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

Этот подход позволил решать задачи на шесть порядков большие, чем человечество умело до этого.

Тайна чисел‑близнецов

lightln2 1 окт в 09:20

я тоже против

Тайна чисел‑близнецов

lightln2 30 сен в 12:52

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

Закономерность расположения составных чисел в рядах B(b) = 6b-1 и С© = 6с+1 позволяет создать решето для чисел‑близнецов

А вот Терренс Тао утверждает, что это принципиально невозможно!

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

lightln2 14 сен в 13:16

вроде бы, можно. Вот тут доказано, что всегда можно найти N permutation-fair кубиков, правда, разного размера. Но, насколько я понимаю, их всегда можно свести к кубикам одного размера (взяв наибольшее общее частное их количества граней, потом повторив каждую грань столько раз, что все кубики будут одинаковыми, но с повторяющимися числами, потом заменив каждое повторяющееся число на последовательность чисел, и увеличив все числа больше его соответственно).

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

lightln2 14 сен в 03:48

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

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

Сформулировать условие - n игроков бросают n кубиков с d гранями каждый, с различными числами на гранях 1 … nd. Выигрывает тот, кто выкинул максимальное число. Можно ли обеспечить равновероятность выигрыша каждым игроком?

Рассказать, что есть разные варианты задачи

каждый игрок выигрывает с равной вероятностью
любые k <= n игроков могут взять произвольные k кубиков и выиграть с равной вероятностью
результат обеспечивает любую перестановку игроков с равной вероятностью

Упомянуть, что для более простых условий есть тривиальные решения:

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

В комментариях уже написали, что для двух игроков есть тривиальное решение (1,4) и (2,3) Для трех игроков уже надо искать брутфорсом, перебирая все варианты, простой скрипт на питоне выдает несколько решений, например, (0, 4, 8, 11, 13, 15) (1, 5, 6, 10, 12, 17) (2, 3, 7, 9, 14, 16).

Проверка, что кубики удовлетворяют условию задачи, делается за O(d^n), но можно применить оптимизацию, похожую на merge sort, ускоряющую ее до O(dn) (очень похоже на те самые всеми нелюбимые leetcode-задачи!).

При этом количество вариантов размещения чисел на кубиках растет экспоненциально, поэтому для трех достаточно скрипта на питоне, для четырех надо писать умные оптимизации, а для пяти чуваки решали задачу 15 лет, и до сих пор не знают, оптимально ли найденное решение.

Что математики говорят про влияние ИИ на математику?

lightln2 11 сен в 13:16

В общем, TLDR: LLM-ы в математике (как и в программировании), очень хорошо генерят write-only доказательство (код), решающий одну конкретную задачу. Сделать доказательства (код) переиспользуемыми, тем более, законтрибьютить в теорию (стандартную библиотеку), это они (пока?) не умеют.

Математики до сих пор не уверены, как быстрее всего перемножать числа

lightln2 28 авг в 10:46

а все-таки, где про это почитать? Там вроде должны быть физические ограничения на логические элементы - чтобы сделать сложение/умножение за O(1), надо, чтобы NAND элементы имели O(n) входов и выходов, что линейно увеличивает паразитную ёмкость, что замедляет распространение сигнала.

Необратимая операция: как печатать чек, если непонятно, напечатался ли он

lightln2 6 авг в 10:12

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

фискальный документ и чек - это одно и то же?
что значит “печать”? реально физическая печать на реально физической бумажке? зачем? и что потом делают с бумажками, появляющимися [размер фермы / 0.7] в секунду?

OpenAI заявила о 10 математических прорывах: достижения новой модели Astra

lightln2 2 авг в 13:13

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

Начиная с Рамануджана, который (пока что) на несколько порядков уделывает LLM-ы по нахождению безумных тождеств (и решению проблем, похожих на эту), и кончая классикой жанра - нахождением безумной вспомогательной функции для решения задачи о упаковке восьмимерных сфер (https://arxiv.org/abs/1603.04246). По таким прорывам можно писать отдельный обзор (я, навскидку, могу без гугла около десятка вспомнить).

Так что я скорее сошлашусь с комментаторами, утверждающими, что LLM тут решает задачи, которые и человекам под силу, просто до них пока никто не добрался. Тут интересный вопрос, можно ли будет такое поставить на поток в стиле Рамануждана.

HashLife на питоне

lightln2 18 июл в 14:43

Берем длинную палку длинной 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 18 июл в 13:27

Как это делается для дерева 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 18 июл в 11:01

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

Рассмотрим обобщенный клеточный автомат, у которого состояние клетки зависит от целой окрестности $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 для графов, которые не влезают в память - это отдельный мир, с десятилетиями научных исследований и сотней эзотерических алгоритмов.

2 3 ...

8 9