А по теме, есть хорошая лекция от MIT про оптимизацию BFS, с акцентом на многопоточность, но и однопоточные оптимизации тоже раскрываются. Там, кстати, рассказывают, как именно считаются эти cache misses, и как оптимизации их улучшают.
Это все если граф влезает в память. BFS для графов, которые не влезают в память - это отдельный мир, с десятилетиями научных исследований и сотней эзотерических алгоритмов.
Что мне больше всего тут непонятно, это как там на графе из 500 вершин и 6000 ребер даже в самой оптимизированной версии насчиталось почти миллион cache misses.
Ну и вообще, я посмотрел в оригинал, он оставляет странное впечатление - товарищ работает с низкоуровневым программированием, пишет книгу аж из 20 глав, в ней все баззворды на своих местах. Но он зациклен на cache misses, и его аргументация местами очень странная. То ли очень неаккуратно написано (при чем тут Radix Tree?), то ли вообще цифры с потолка взяты.
Кажется, автор еще забыл упомянуть, что переполнение знаковых - это undefined behavior в C++, если делать offset/length знаковыми, то это придется как-то чинить.
Но совсем избавляться от беззнаковых тоже кажется не самой лучшей идеей, тогда, как в Яве, придется вводить оператор “>>>” (беззнаковый сдвиг вправо), и будут проблемы с поддержкой форматов хранения, где значения беззнаковые, например, массив uint8.
Но когда корректность важнее скорости, то имхо, знаковые оффсеты и длины массивов кажутся хорошим компромисом: можно вставить дополнительные проверки на неотрицательность при создании массива и обращении к его элементам (в 99% случаев оно не скажется на производительности, так как проверка будет на свободном ALU-порту, и branch prediction тоже отработает параллельно)
В общем, мне нравится подход как в C#, придуманный много лет назад:
длины и оффсеты массивов знаковые, исключения при обращениях out-of-bounds
есть беззнаковые, если нужны, более-менее разумные правила автоматического преобразования
если важно не поймать overflow, есть опциональный checked{} контекст, в котором оно вызовет исключение
Eсли надо выжать последние полпроцента производительности, есть unsafe{} контекст, в котором можно создать массив байт через malloc, и дальше уже с ним извращаться, как душе угодно.
Спасибо, отличный обзор! Тем не менее, хотел бы указать на потенциально не раскрытые вами подходы:
Теория игр и теорема минимакса - представить задачу как игру, где один игрок выбирает число, не противоречащее предыдущим проверкам, а второй пытается его угадать за минимальное число проверок.
Иммунные алгоритмы - если честно, я мало что при них знаю, но ученые, с ними работающие, утверждают, что это гораздо круче генетических алгоритмов!
Целочисленное Линейное Программирование - вроде должно работать, потому что каждое угадывание задает линейное ограничение (то есть, гиперплоскость в одномерном пространстве)!
Я не боюсь, но опасаюсь задач на DP, потому что сложность в деталях:
Как конкретно определять подзадачу (например, на строках - dp[i] - это задача на символе i или на префиксе длины i? Будем задавать базовые условия для всех подстрок в один символ или для только пустой строки?)
Какой брать переход из возможных опций (dp[i] - количество нужных подстрок, заканчивающихся на символе i или принадлежащих префиксу длины i)?
А если еще и надо восстановить оптимальное рещение, то это еще сильнее усложняет реализацию (будем хранить граф переходов? или потом восстановим из таблицы стоимостей?)
Чаще всего все варианты будут работать, но нужна интуиция, чтобы понять какой приведет к самому короткому и понятному коду без ошибок. Если кто-то знает какие-то эвристики, расскажите!
А мое любимое объяснение DP - лекция из цикла MIT “введение в алгоритмы” авторства Эрика Демайна - очень известный в мире computer scienсе чувак, автор структуры Tango Trees и доказавший, что тетрис NP-полон. Он подробно рассказывает именно о том, какие характеристики задачи делают ее dp, и как от них перейти к формуле.
А потом замкнуть круг - агент генерирует код, линтер выдает ошибки, чтоб агент починил, отдает линтеру... и так до бесконечности Но скорее всего, уже на первом цикле агент все разломает, что раньше хоть как-то работало
Еще можно упомянуть крайне полезную библиотеку sortedcontainers с классами SortedList, SortedDict, SortedSet - аналоги multiset, map, set в с++, но, в отличие от них, поддерживающие поиск индекса и по индексу за логарифм.
Ну и, чтоб два раза не вставать, хочется упомянуть "тяжелую артиллерию".
библиотека networkx для работы с графами, умеет ну практически все стандартные алгоритмы на графах.
библиотека Z3-solver, решает задачи в символьном виде, умеет LP, целочисленное LP, 2-SAT, 3-SAT и кучу всего прочего.
А есть какой-то стандартный шаблон для sliding window, который позволяет для разных задач подставлять реализацию (как, например, с бинпоиском), или там слишком много разных вариаций? Ну, типа
left = 0
for right in range(n):
add(right)
while left <= right and not good(): remove(left++)
И, кстати, почему-то везде все итерируют по правому концу, и подбирают левый, хотя, кажется, итерировать по левому концу немного более естесственно?
Я когда-то давно смотрел интервью с налоговым инспектором, и он сказал, что им сверху спускается позиция - никогда не принимать сторону налогоплательщика. Любая попытка "войти в положение" или "простить незначительные ошибки" будет трактоваться как сговор с налогоплательщиком с целью уйти от налогов, и последует обвинение во взятке.
да я уже понял, что зря залез со своим комментарием. Я просто хотел поделиться подходом к решению таких задач, который минимизирует скорость написания и количество ошибок. Такие задачи - это не ентерпрайз, это либо собеседования, либо соревнования по программированию. И на хабре, и на реддите многие жалуются, что на собесе не решили задачу, стресс, не хватило времени, запутались в граничных условиях, не нашли ошибку (На контестах тоже частая проблема - не хватает времени на сложные задачи, так как слишком много времени ушло на написание и отлаживание простых). Это нормально - в условиях стресса люди всегда делают больше ошибок, поэтому всегда имеет смысл писаль код максимально близкий к объяснению решения задачи на словах. Ну и если вы думаете, что это - говнокод, значит вы не видели, как пишут код люди уровня чемпионов ICPC - не потому, что иначе не умеют, а потому, что это более эффективно.
Это, наверно, был риторический вопрос, но я попробую ответить. Конкретно эта задача, может, и не имеет практического значения, но она является упражнением на поиск второго маскимума(минимума). Это частный случай поиска k-го максимума (или первых k максимумов). Практическое значение - Вас с помощью этой задачи подводят к алгоритму quick-select (используется много где, например, в статистике для вычисления медианы/перцентилей) Второе применение - поиск второго максимума/минимума в более сложных объектах. Классическая задача - поиск второго оптимального пути в ациклических направленных графах. Практическое применение - быстрое вычисление оптимальной траектории в вашей сети, если одно из ее ребер удалить (то есть, нарушилась связность между двумя узлами в сети).
что вы понимаете под оптимальными алгоритмами? обычно это означает "асимптотически оптимальные", но вы имеете в виду, видимо, абсолютное время? тогда перепишите код на c++ и скомпилируйте с -Ofast -march=native и это будет оптимально, так как упрется в пропускную способность памяти (и то не на всех архитектурах, так как иногда в один поток невозможно нагрузить память, надо будет параллелить). Даже если вы имеете в виду абсолютное время на питоне, то наверняка какой-нибудь numpy.partition будет быстрее, так как выполняется нативно на numpy-массивах. Ну и даже для вашего алгоритма наверняка распараллеливание на несколько потоков его ускорит.
повышение читаемости сомнительно
это стандартный шаблон argmax (одна из полезных функций, отсутствующих в питоне, но присутствующих, например, в numpy) - он обычно легко распознается при чтении, если вам знаком
Если писать на питоне, то я бы использовал всю его мощь для таких задач. Ваше решение можно сократить более, чем в два раза и, мне кажется, в таком коде сложнее ошибиться (что особенно важно, если эта задача с собеседования):
def max_product_linear(arr):
n = len(arr)
if n < 2: return None
max1 = max(range(n), key=lambda i: arr[i])
max2 = max(range(n), key=lambda i: arr[i] if i != max1 else -math.inf)
min1 = min(range(n), key=lambda i: arr[i])
min2 = min(range(n), key=lambda i: arr[i] if i != min1 else math.inf)
return max(arr[max1]*arr[max2], arr[min1]*arr[min2])
да, у меня примерно такое же нерекурсивное решение. Рекурсивное есть совсем простое, но за квадрат в худшем случае. Его несложно превратить в линейное, там побольше кода будет. Но мне кажется, оно все еще сильно проще нерекурсивного.
На простых задачах это неинтересно. Попробуйте сравнить на более сложных, особенно где есть нетривиальное состояние. Например:
quick sort: его, конечно, можно написать без рекурсии, но код будет, мягко говоря, нечитабельным
задача с литкода про восстановление дерева по его inorder и preorder. Решается элементарно за 5 минут с помощью рекурсии, в 5 строк кода на питоне. У нее есть нерекурсивное решение, в чем-то изящное, но оно сильно нетривиальное, и там надо додуматься до хитрого инварианта того, что пихать в стек.
Хочу поправить себя, я тут неправду написал, конечно, вставка O*log(n)) амортизированная. Тут еще кажется, что сортировка массива добавляет еще один лог-фактор, но в Питоне, как и в Яве, сортировка является вариантом TimSort, который работает за линейное время, если сортируемый массив состоит из небольщого количества уже отсортированных кусков (так как внутри он использует merge sort). Поэтому полезный трюк на питоне или Яве (но не на C++ или C#) - если надо сделать merge sort, можно просто слить массивы в один массив, и использовать стандартный сорт!
вот, если кому интересно, реализация на питоне (поиск и вставки, без удаления), получилось 9 строчек. Вставка O(1) амортизированная, поиск O(log^2(n)). На практике, перед вставкой надо тоже делать поиск, чтобы избежать дубликатов, но для этого можно добавить простой хешсет, чтобы вставка осталась O(1).
С этим сложно поспорить, но можно переформулировать задачу как найти такие
, что
что является частным случаем диофантовых уравнений! А вообще, статья интересная, спасибо! Не хватает только списка самих чисел.
А по теме, есть хорошая лекция от MIT про оптимизацию BFS, с акцентом на многопоточность, но и однопоточные оптимизации тоже раскрываются. Там, кстати, рассказывают, как именно считаются эти cache misses, и как оптимизации их улучшают.
Это все если граф влезает в память. BFS для графов, которые не влезают в память - это отдельный мир, с десятилетиями научных исследований и сотней эзотерических алгоритмов.
Что мне больше всего тут непонятно, это как там на графе из 500 вершин и 6000 ребер даже в самой оптимизированной версии насчиталось почти миллион cache misses.
Ну и вообще, я посмотрел в оригинал, он оставляет странное впечатление - товарищ работает с низкоуровневым программированием, пишет книгу аж из 20 глав, в ней все баззворды на своих местах. Но он зациклен на cache misses, и его аргументация местами очень странная. То ли очень неаккуратно написано (при чем тут Radix Tree?), то ли вообще цифры с потолка взяты.
Кажется, автор еще забыл упомянуть, что переполнение знаковых - это undefined behavior в C++, если делать offset/length знаковыми, то это придется как-то чинить.
Но совсем избавляться от беззнаковых тоже кажется не самой лучшей идеей, тогда, как в Яве, придется вводить оператор “>>>” (беззнаковый сдвиг вправо), и будут проблемы с поддержкой форматов хранения, где значения беззнаковые, например, массив uint8.
Но когда корректность важнее скорости, то имхо, знаковые оффсеты и длины массивов кажутся хорошим компромисом: можно вставить дополнительные проверки на неотрицательность при создании массива и обращении к его элементам (в 99% случаев оно не скажется на производительности, так как проверка будет на свободном ALU-порту, и branch prediction тоже отработает параллельно)
В общем, мне нравится подход как в C#, придуманный много лет назад:
длины и оффсеты массивов знаковые, исключения при обращениях out-of-bounds
есть беззнаковые, если нужны, более-менее разумные правила автоматического преобразования
если важно не поймать overflow, есть опциональный checked{} контекст, в котором оно вызовет исключение
Eсли надо выжать последние полпроцента производительности, есть unsafe{} контекст, в котором можно создать массив байт через malloc, и дальше уже с ним извращаться, как душе угодно.
Многие, кто работают в гугле/яндексе пишут дп регулярно. Но конкретно
Вы это делаете каждый день, когда выполняете git diff - он основан на алгоритме Майерса, варианте Longest Common Subsequence Problem, являющегося классикой DP!
Спасибо, отличный обзор! Тем не менее, хотел бы указать на потенциально не раскрытые вами подходы:
Теория игр и теорема минимакса - представить задачу как игру, где один игрок выбирает число, не противоречащее предыдущим проверкам, а второй пытается его угадать за минимальное число проверок.
Иммунные алгоритмы - если честно, я мало что при них знаю, но ученые, с ними работающие, утверждают, что это гораздо круче генетических алгоритмов!
Целочисленное Линейное Программирование - вроде должно работать, потому что каждое угадывание задает линейное ограничение (то есть, гиперплоскость в одномерном пространстве)!
Я не боюсь, но опасаюсь задач на DP, потому что сложность в деталях:
Как конкретно определять подзадачу (например, на строках - dp[i] - это задача на символе i или на префиксе длины i? Будем задавать базовые условия для всех подстрок в один символ или для только пустой строки?)
Какой брать переход из возможных опций (dp[i] - количество нужных подстрок, заканчивающихся на символе i или принадлежащих префиксу длины i)?
А если еще и надо восстановить оптимальное рещение, то это еще сильнее усложняет реализацию (будем хранить граф переходов? или потом восстановим из таблицы стоимостей?)
Чаще всего все варианты будут работать, но нужна интуиция, чтобы понять какой приведет к самому короткому и понятному коду без ошибок. Если кто-то знает какие-то эвристики, расскажите!
А мое любимое объяснение DP - лекция из цикла MIT “введение в алгоритмы” авторства Эрика Демайна - очень известный в мире computer scienсе чувак, автор структуры Tango Trees и доказавший, что тетрис NP-полон. Он подробно рассказывает именно о том, какие характеристики задачи делают ее dp, и как от них перейти к формуле.
А потом замкнуть круг - агент генерирует код, линтер выдает ошибки, чтоб агент починил, отдает линтеру... и так до бесконечности
Но скорее всего, уже на первом цикле агент все разломает, что раньше хоть как-то работало
Еще можно упомянуть крайне полезную библиотеку sortedcontainers с классами SortedList, SortedDict, SortedSet - аналоги multiset, map, set в с++, но, в отличие от них, поддерживающие поиск индекса и по индексу за логарифм.
Ну и, чтоб два раза не вставать, хочется упомянуть "тяжелую артиллерию".
библиотека networkx для работы с графами, умеет ну практически все стандартные алгоритмы на графах.
библиотека Z3-solver, решает задачи в символьном виде, умеет LP, целочисленное LP, 2-SAT, 3-SAT и кучу всего прочего.
А есть какой-то стандартный шаблон для sliding window, который позволяет для разных задач подставлять реализацию (как, например, с бинпоиском), или там слишком много разных вариаций? Ну, типа
И, кстати, почему-то везде все итерируют по правому концу, и подбирают левый, хотя, кажется, итерировать по левому концу немного более естесственно?
Я когда-то давно смотрел интервью с налоговым инспектором, и он сказал, что им сверху спускается позиция - никогда не принимать сторону налогоплательщика. Любая попытка "войти в положение" или "простить незначительные ошибки" будет трактоваться как сговор с налогоплательщиком с целью уйти от налогов, и последует обвинение во взятке.
да я уже понял, что зря залез со своим комментарием. Я просто хотел поделиться подходом к решению таких задач, который минимизирует скорость написания и количество ошибок.
Такие задачи - это не ентерпрайз, это либо собеседования, либо соревнования по программированию.
И на хабре, и на реддите многие жалуются, что на собесе не решили задачу, стресс, не хватило времени, запутались в граничных условиях, не нашли ошибку (На контестах тоже частая проблема - не хватает времени на сложные задачи, так как слишком много времени ушло на написание и отлаживание простых). Это нормально - в условиях стресса люди всегда делают больше ошибок, поэтому всегда имеет смысл писаль код максимально близкий к объяснению решения задачи на словах.
Ну и если вы думаете, что это - говнокод, значит вы не видели, как пишут код люди уровня чемпионов ICPC - не потому, что иначе не умеют, а потому, что это более эффективно.
Это, наверно, был риторический вопрос, но я попробую ответить.
Конкретно эта задача, может, и не имеет практического значения, но она является упражнением на поиск второго маскимума(минимума).
Это частный случай поиска k-го максимума (или первых k максимумов). Практическое значение - Вас с помощью этой задачи подводят к алгоритму quick-select (используется много где, например, в статистике для вычисления медианы/перцентилей)
Второе применение - поиск второго максимума/минимума в более сложных объектах. Классическая задача - поиск второго оптимального пути в ациклических направленных графах. Практическое применение - быстрое вычисление оптимальной траектории в вашей сети, если одно из ее ребер удалить (то есть, нарушилась связность между двумя узлами в сети).
что вы понимаете под оптимальными алгоритмами?
обычно это означает "асимптотически оптимальные", но вы имеете в виду, видимо, абсолютное время? тогда перепишите код на c++ и скомпилируйте с -Ofast -march=native и это будет оптимально, так как упрется в пропускную способность памяти (и то не на всех архитектурах, так как иногда в один поток невозможно нагрузить память, надо будет параллелить).
Даже если вы имеете в виду абсолютное время на питоне, то наверняка какой-нибудь numpy.partition будет быстрее, так как выполняется нативно на numpy-массивах. Ну и даже для вашего алгоритма наверняка распараллеливание на несколько потоков его ускорит.
это стандартный шаблон argmax (одна из полезных функций, отсутствующих в питоне, но присутствующих, например, в numpy) - он обычно легко распознается при чтении, если вам знаком
O(4n) - это тот же O(n). Нафига бороться за константу в коде на питоне? Тогда уж надо на c++ писать.
Если писать на питоне, то я бы использовал всю его мощь для таких задач. Ваше решение можно сократить более, чем в два раза и, мне кажется, в таком коде сложнее ошибиться (что особенно важно, если эта задача с собеседования):
да, у меня примерно такое же нерекурсивное решение.
Рекурсивное есть совсем простое, но за квадрат в худшем случае. Его несложно превратить в линейное, там побольше кода будет. Но мне кажется, оно все еще сильно проще нерекурсивного.
На простых задачах это неинтересно. Попробуйте сравнить на более сложных, особенно где есть нетривиальное состояние. Например:
quick sort: его, конечно, можно написать без рекурсии, но код будет, мягко говоря, нечитабельным
задача с литкода про восстановление дерева по его inorder и preorder. Решается элементарно за 5 минут с помощью рекурсии, в 5 строк кода на питоне. У нее есть нерекурсивное решение, в чем-то изящное, но оно сильно нетривиальное, и там надо додуматься до хитрого инварианта того, что пихать в стек.
Хочу поправить себя, я тут неправду написал, конечно, вставка O*log(n)) амортизированная.
Тут еще кажется, что сортировка массива добавляет еще один лог-фактор, но в Питоне, как и в Яве, сортировка является вариантом TimSort, который работает за линейное время, если сортируемый массив состоит из небольщого количества уже отсортированных кусков (так как внутри он использует merge sort).
Поэтому полезный трюк на питоне или Яве (но не на C++ или C#) - если надо сделать merge sort, можно просто слить массивы в один массив, и использовать стандартный сорт!
вот, если кому интересно, реализация на питоне (поиск и вставки, без удаления), получилось 9 строчек.
Вставка O(1) амортизированная, поиск O(log^2(n)). На практике, перед вставкой надо тоже делать поиск, чтобы избежать дубликатов, но для этого можно добавить простой хешсет, чтобы вставка осталась O(1).