да я уже понял, что зря залез со своим комментарием. Я просто хотел поделиться подходом к решению таких задач, который минимизирует скорость написания и количество ошибок. Такие задачи - это не ентерпрайз, это либо собеседования, либо соревнования по программированию. И на хабре, и на реддите многие жалуются, что на собесе не решили задачу, стресс, не хватило времени, запутались в граничных условиях, не нашли ошибку (На контестах тоже частая проблема - не хватает времени на сложные задачи, так как слишком много времени ушло на написание и отлаживание простых). Это нормально - в условиях стресса люди всегда делают больше ошибок, поэтому всегда имеет смысл писаль код максимально близкий к объяснению решения задачи на словах. Ну и если вы думаете, что это - говнокод, значит вы не видели, как пишут код люди уровня чемпионов 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).
Интересно, оказывается, эта структура имеет название. Я думал, это "народный" трюк, чтобы делать "дешевый аналог" деревьев, если в вашем языке программирования нет их из коробки, и нет возможности использовать дополнительные библиотеки. Я похожий трюк даже один раз использовал для какой-то задачи с литкода, потому что не знал, есть ли в питоне sorted set) Основное ее преимущество перед деревьями - простота реализации. Если не гнаться за излишней оптимизацией, реализация [на питоне] занимает буквально десяток строчек! Она, кажется, позволяет делать большую часть того, что могут и обычные деревья, за счет дополнительного log-фактора. Этот лог фактор можно убить с помощью эзотерической техники fractional cascading (но непонятно, нафига, так как это уже сложнее, чем "вращать деревья"). Этот подход, если я правильно понимаю, является частным случаем log-structure merge tree, на котором основаны поисковые движки типа lucene, и многие nosql базы данных (cassandra, rocksdb)
Хорошая задача, она демонстрирует основной результат теории, которую называют красивым словом "heavy hitters theory" (не знаю, как правильно перевести на русский - может, "важные чуваки"?) Лет 10 назад она активно развивалась, и было много научных работ на эту тему (последнее время я за ней не слежу, может, до сих пор там что-то новое придумывают) Там два основных результата - это теорема Бойера-Мура о поиске значений, встречающихся в потоке больше половины раз , о которой @Alexandroppolus упоминает, и ее обобщение на n/k раз теорема Мисра-Грис. Также там активно исследовались вероятностные методы, так что идея автора (если я правильно понимаю) - очень хорошая на практике, потому что вероятность ложного результата обычно падает экспоненциально по количеству попыток. То есть, если взять ваш алгоритм и повторить раз 50, то вероятность его ошибки будет сильно меньше вероятности того, что прилетит заряженная частица с солнца и поменяет бит в памяти компьютера. Конечно, есть еще вероятность злонамеренной атаки на генератор случайных чисел, но эта проблема тоже имеет теоретическое решение :) Ну и важная часть исследований доказывает разные ограничения. Я знаю реальный случай, когда начальник попросил программиста найти моду (самое повторяющееся значение в потоке) с использованием констатной памяти. Программист ему гордо показал теорему, которая говорит, что это невозможно!
если номера изначально не отсортированы, и их много, то наверно самый быстрый теоретический подход - это для каждого номера выполнять predecessor query за O(1) по началам диапазонов. Например, сохранять a_i в Van Emde Boas tree. Я когда-то слышал, что якобы в роутерах похожий подход используют для матчинга ip по диапазонам, но в википедии про это нет, так что это, наверно, anecdotal evidence. Но, судя по тому, что эта структура в реальности почти не используется, там наверняка слишком большие константы, и бинпоиск выгоднее на задачах ожидаемого размера.
Ну, может, и изврат)) мне просто интересны эти задачи с точки зрения ментальной нагрузки. Иногда это называют cyclomatic complexity, но я определяю как матожидание количества исправлений от первой версии до полностью рабочей. Я иногда могу потратить пару часов на задачу LeetCode easy, пытаясь ее написать так, чтобы минимизировать количество потенциальных ошибок. С этой точки зрения heap для меня проще бинпоиска, у которого много пограничных случаев, которые надо в голове держать. Это, кстати, и в работе помогает - развивает интуицию, как надо писать код, чтобы потом его мучительно не отлаживать ))
да, если его оформлять как отдельный переиспользуемый класс, то получается много кода. Но на интервью, вроде бы, обычно нормально относятся к сокращению кода. Я сейчас попробовал написать по памяти хип сорт, примерно так получилось:
def sieve_down(arr, i, n):
while True:
lt,rt,best = i*2+1, i*2+2, i
if lt < n and arr[lt] > arr[best]: best = lt
if rt < n and arr[rt] > arr[best]: best = rt
if best == i: break
arr[i], arr[best], i = arr[best], arr[i], best
def heapsort(arr):
for i in reversed(range(len(arr))):
sieve_down(arr, i, len(arr))
for i in reversed(range(len(arr))):
arr[0], arr[i] = arr[i], arr[0]
sieve_down(arr, 0, i)
Спасибо за подробный рассказ! Я, конечно, поражаюсь (ну и немного завидую) вашему упорству! Вы пишете про динамическое программирование: "Прорыв произошёл не сразу и не за одну тему" - А это было сколько по времени? В смысле, месяц, год, неделя?
Ну и конечно, главный вопрос: почему не питон? :)
И чтоб два раза не вставать, хочу "защитить" мой любимый Heap - я не согласен, что его долго писать, он довольно простой, если в голове держать, какие элементы куда просеиваются. А если делать heapsort - там даже просеивания вверх не нужно, только просеивание вниз, и весь код умещается строчек в 15 на питоне! Для меня бинпоиск сложнее, чем heap, потому что там надо в голове держать, что вернуть, если элемент не найден, или есть несколько одинаковых элементов.
Не соглашусь, скорее это как хотеть играть на пианино, но вместо того, чтобы сразу учить концерт Рахманинова и писать свою симфонию, два года играть гаммы и "к Элизе". Для профессиональных писанистов это скорее норма. И если уж продолжать аналогию, то цель была - попасть в оркестр пианистом, а теперь поменялась на "научиться играть на пианино" - я бы не назвал это провалом))
Я, кажется, решил задачу для n=10 (получается, задача 3025 года!) Мой результат - 290,794,520 решений, или 36,349,315 решений без учета симметрии. Программа работала 3 недели на 8-ядерном AMD EPYC, и проверила чуть больше 500 триллионов позиций (шагов DFS). Конечно, надо будет перепроверять результат, тем более что там много хитрых оптимизаций, и вероятность ошибки не исключена. Для сравнения, программа считает результат для n=8 за 2 секунды (16 секунд однопоточно), а для n=9 - за 15 минут (2 часа однопоточно). Надо, наверно, будет потом опубликовать код и подробно описать оптимизации, они сами по себе довольно интересные.
Я часто вижу такую точку зрения, что эти задачки на литкоде и собеседованиях - это такая лотерея, что человек их заучивает, и потом либо ему повезло, и он похожую задачу решал, либо не повезло. Мне кажется, эти задачи скорее простые примеры из базового курса по Computer Science - то есть, если вы этот курс прошли, и прорешали эти задачи, то вероятность встретить задачу уровня easy/medium, к которой вообще непонятно, как подступиться, мала. Даже если в вузе такого курса не было, их на ютубе много, от MIT или МФТИ, например. Другое дело, что многим быстрее рискнуть и бессистемно запомнить принцип решения пары сотен задач, чем проходить годовой курс и разбираться в теории, но я не знаю, насколько это проблема собеседований.
По поводу сделать research - далеко не всегда его можно делать, если вы не знаете основы computer science (А если знаете - то решение задачек на собеседовании не будет проблемой). В гугле часто возникают задачи, для которых надо придумать новый, прежде несуществующий, алгоритм, а не просто применить новый, они публикуют научные статьи каждый год.
ну это почти определение предела в хаусдорфовом топологическом пространстве (если окрестность заменить на замкнутое множество). Для евклидовых пространств - одно из нескольких десятков эквивалентных, далеко не самое мощное. Собственно, такое количество эквивалентных определений и удобно, что для доказательства можно выбрать наиболее подходящее. Я очень сомневаюсь, что оно может упростить ряд доказательств, потому что для него даже метрики не нужно, только наличие свойства отделимости (я тут, конечно, говорю о строгих доказательствах)
ну это же просто неверно в общем случае. Возьмите последовательность 0, sinx, 0, sin2x, 0, sin3x, ... в пространстве непрерывных функций на отрезке от 0 до 2π (с практически любой метрикой, например, L2). У нее единственная точка сгущения - 0, но предела нет. вместо sin(nx) можно взять базис в любом бесконечномерном пространстве с метрикой.
да я уже понял, что зря залез со своим комментарием. Я просто хотел поделиться подходом к решению таких задач, который минимизирует скорость написания и количество ошибок.
Такие задачи - это не ентерпрайз, это либо собеседования, либо соревнования по программированию.
И на хабре, и на реддите многие жалуются, что на собесе не решили задачу, стресс, не хватило времени, запутались в граничных условиях, не нашли ошибку (На контестах тоже частая проблема - не хватает времени на сложные задачи, так как слишком много времени ушло на написание и отлаживание простых). Это нормально - в условиях стресса люди всегда делают больше ошибок, поэтому всегда имеет смысл писаль код максимально близкий к объяснению решения задачи на словах.
Ну и если вы думаете, что это - говнокод, значит вы не видели, как пишут код люди уровня чемпионов 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).
Интересно, оказывается, эта структура имеет название. Я думал, это "народный" трюк, чтобы делать "дешевый аналог" деревьев, если в вашем языке программирования нет их из коробки, и нет возможности использовать дополнительные библиотеки. Я похожий трюк даже один раз использовал для какой-то задачи с литкода, потому что не знал, есть ли в питоне sorted set)
Основное ее преимущество перед деревьями - простота реализации. Если не гнаться за излишней оптимизацией, реализация [на питоне] занимает буквально десяток строчек!
Она, кажется, позволяет делать большую часть того, что могут и обычные деревья, за счет дополнительного log-фактора. Этот лог фактор можно убить с помощью эзотерической техники fractional cascading (но непонятно, нафига, так как это уже сложнее, чем "вращать деревья").
Этот подход, если я правильно понимаю, является частным случаем log-structure merge tree, на котором основаны поисковые движки типа lucene, и многие nosql базы данных (cassandra, rocksdb)
Хорошая задача, она демонстрирует основной результат теории, которую называют красивым словом "heavy hitters theory" (не знаю, как правильно перевести на русский - может, "важные чуваки"?)
Лет 10 назад она активно развивалась, и было много научных работ на эту тему (последнее время я за ней не слежу, может, до сих пор там что-то новое придумывают)
Там два основных результата - это теорема Бойера-Мура о поиске значений, встречающихся в потоке больше половины раз , о которой @Alexandroppolus упоминает, и ее обобщение на n/k раз теорема Мисра-Грис.
Также там активно исследовались вероятностные методы, так что идея автора (если я правильно понимаю) - очень хорошая на практике, потому что вероятность ложного результата обычно падает экспоненциально по количеству попыток. То есть, если взять ваш алгоритм и повторить раз 50, то вероятность его ошибки будет сильно меньше вероятности того, что прилетит заряженная частица с солнца и поменяет бит в памяти компьютера. Конечно, есть еще вероятность злонамеренной атаки на генератор случайных чисел, но эта проблема тоже имеет теоретическое решение :)
Ну и важная часть исследований доказывает разные ограничения. Я знаю реальный случай, когда начальник попросил программиста найти моду (самое повторяющееся значение в потоке) с использованием констатной памяти. Программист ему гордо показал теорему, которая говорит, что это невозможно!
если номера изначально не отсортированы, и их много, то наверно самый быстрый теоретический подход - это для каждого номера выполнять predecessor query за O(1) по началам диапазонов. Например, сохранять a_i в Van Emde Boas tree.
Я когда-то слышал, что якобы в роутерах похожий подход используют для матчинга ip по диапазонам, но в википедии про это нет, так что это, наверно, anecdotal evidence.
Но, судя по тому, что эта структура в реальности почти не используется, там наверняка слишком большие константы, и бинпоиск выгоднее на задачах ожидаемого размера.
Ну, может, и изврат)) мне просто интересны эти задачи с точки зрения ментальной нагрузки. Иногда это называют cyclomatic complexity, но я определяю как матожидание количества исправлений от первой версии до полностью рабочей.
Я иногда могу потратить пару часов на задачу LeetCode easy, пытаясь ее написать так, чтобы минимизировать количество потенциальных ошибок. С этой точки зрения heap для меня проще бинпоиска, у которого много пограничных случаев, которые надо в голове держать.
Это, кстати, и в работе помогает - развивает интуицию, как надо писать код, чтобы потом его мучительно не отлаживать ))
да, если его оформлять как отдельный переиспользуемый класс, то получается много кода. Но на интервью, вроде бы, обычно нормально относятся к сокращению кода. Я сейчас попробовал написать по памяти хип сорт, примерно так получилось:
Спасибо за подробный рассказ! Я, конечно, поражаюсь (ну и немного завидую) вашему упорству!
Вы пишете про динамическое программирование: "Прорыв произошёл не сразу и не за одну тему" - А это было сколько по времени? В смысле, месяц, год, неделя?
Ну и конечно, главный вопрос: почему не питон? :)
И чтоб два раза не вставать, хочу "защитить" мой любимый Heap - я не согласен, что его долго писать, он довольно простой, если в голове держать, какие элементы куда просеиваются. А если делать heapsort - там даже просеивания вверх не нужно, только просеивание вниз, и весь код умещается строчек в 15 на питоне! Для меня бинпоиск сложнее, чем heap, потому что там надо в голове держать, что вернуть, если элемент не найден, или есть несколько одинаковых элементов.
Не соглашусь, скорее это как хотеть играть на пианино, но вместо того, чтобы сразу учить концерт Рахманинова и писать свою симфонию, два года играть гаммы и "к Элизе". Для профессиональных писанистов это скорее норма.
И если уж продолжать аналогию, то цель была - попасть в оркестр пианистом, а теперь поменялась на "научиться играть на пианино" - я бы не назвал это провалом))
Я, кажется, решил задачу для n=10 (получается, задача 3025 года!) Мой результат - 290,794,520 решений, или 36,349,315 решений без учета симметрии.
Программа работала 3 недели на 8-ядерном AMD EPYC, и проверила чуть больше 500 триллионов позиций (шагов DFS). Конечно, надо будет перепроверять результат, тем более что там много хитрых оптимизаций, и вероятность ошибки не исключена. Для сравнения, программа считает результат для n=8 за 2 секунды (16 секунд однопоточно), а для n=9 - за 15 минут (2 часа однопоточно).
Надо, наверно, будет потом опубликовать код и подробно описать оптимизации, они сами по себе довольно интересные.
Я часто вижу такую точку зрения, что эти задачки на литкоде и собеседованиях - это такая лотерея, что человек их заучивает, и потом либо ему повезло, и он похожую задачу решал, либо не повезло.
Мне кажется, эти задачи скорее простые примеры из базового курса по Computer Science - то есть, если вы этот курс прошли, и прорешали эти задачи, то вероятность встретить задачу уровня easy/medium, к которой вообще непонятно, как подступиться, мала. Даже если в вузе такого курса не было, их на ютубе много, от MIT или МФТИ, например.
Другое дело, что многим быстрее рискнуть и бессистемно запомнить принцип решения пары сотен задач, чем проходить годовой курс и разбираться в теории, но я не знаю, насколько это проблема собеседований.
По поводу сделать research - далеко не всегда его можно делать, если вы не знаете основы computer science (А если знаете - то решение задачек на собеседовании не будет проблемой). В гугле часто возникают задачи, для которых надо придумать новый, прежде несуществующий, алгоритм, а не просто применить новый, они публикуют научные статьи каждый год.
ну это почти определение предела в хаусдорфовом топологическом пространстве (если окрестность заменить на замкнутое множество). Для евклидовых пространств - одно из нескольких десятков эквивалентных, далеко не самое мощное. Собственно, такое количество эквивалентных определений и удобно, что для доказательства можно выбрать наиболее подходящее.
Я очень сомневаюсь, что оно может упростить ряд доказательств, потому что для него даже метрики не нужно, только наличие свойства отделимости (я тут, конечно, говорю о строгих доказательствах)
ну это же просто неверно в общем случае. Возьмите последовательность 0, sinx, 0, sin2x, 0, sin3x, ... в пространстве непрерывных функций на отрезке от 0 до 2π (с практически любой метрикой, например, L2). У нее единственная точка сгущения - 0, но предела нет.
вместо sin(nx) можно взять базис в любом бесконечномерном пространстве с метрикой.