Последовательный перебор хорошо локализованного списка влезшего в кэш процессора легко может оказаться быстрее поиска в размазанной по куче или вообще выгруженной в своп хэш-таблице.
Сравните:
Вы держите книгу в руках и ищете страницу 100 последовательно переворачивая страницы.
Вы пишете письмо другу в другой город с просьбой прислать страницу 100 и неделю ждёте ответа с одной страницей.
Асимптотики алгоритмов знать безусловно надо, но они нужны не столько для сравнения скорости алгоритмов сколько для сравнения их способности к масштабированию. А оценить именно скорость без учёта окружения и особенностей реализации невозможно.
Я допускаю, что тебе это не нужно, но вообще это метод решения очень большого класса проблем (тот же квиксорт и динамическое программирование растут именно отсюда).
Достаточно потратить пару вечеров на доказывание классических алгоритмов на графах (которые всяко полезнее и применимее тех же сортировок, и доказывается через эту самую индукцию) и шансы резко повысятся.
Вот соглашусь. Квиксорт я могу воспроизвести не задумываясь (потому что общая идея описывается одним предложением), а пузырек надо вспоминать с бумажкой.
Это на самом деле очень сложный вопрос.
Хэш-таблицы имеют хорошую амортизированную асимптотику, но это совсем не значит, что в общем случае они ищут быстрее или медленнее.
Изучение алгоритмов сортировки крайне полезно для того чтобы научиться строить и анализировать свои алгоритмы. Вот только здесь та же ситуация, что описана в статье. Многие уже забыли зачем на самом деле спрашивают про сортировки.
Понимаете, из ваших статей рисуется образ человека, который собрал в своей карьере все возможные грабли, которые мог собрать разработчик, включая граблю непризнанного гения. Мне сложно поверить, что так бывает, это выглядит как собирательный образ, созданный человеком (или группой людей), которые очень хорошо понимают какие грабли бывают и куда надо давить. Думаю, не только мне, отсюда и теории заговора у людей.
Знаете, я бы ни слова не сказал, если бы в статье просто описывался подход и лежала ссылка на гитхаб. Но эти крайне интересные подробности про плохих менеджеров и удаленные исходники...
Собственно, я бы с удовольствием сам посравнивал, да вот проблема — работающей библиотеки у пацанов нет и сравнивать не с чем. А какое угодно, но работающее решение заведомо лучше удаленного (если оно вообще работало).
Если пацаны так ценят хорошую инженерию, то они могли поступить как инженеры — поискать готовые решения, сравнить, выделить плюсы и минусы, сделать прототип своего и дать менеджеру цифры. Это принятый у профессионалов способ доносить вещи.
Конечно, правда говорят, что массивы в numpy как раз хорошо локализованы. Но я не питонист, не знаю :(
Это просто пример того, что O-нотация и реальная жизнь сложнее чем "O(1) быстрее O(n)".
Я никогда не зубрил сортировки, но могу написать квиксорт из головы. ЧЯДНТ?
Последовательный перебор хорошо локализованного списка влезшего в кэш процессора легко может оказаться быстрее поиска в размазанной по куче или вообще выгруженной в своп хэш-таблице.
Сравните:
Асимптотики алгоритмов знать безусловно надо, но они нужны не столько для сравнения скорости алгоритмов сколько для сравнения их способности к масштабированию. А оценить именно скорость без учёта окружения и особенностей реализации невозможно.
Речь в комментарии на который я отвечал шла о том "какой алгоритм быстрее", а не о том сложность какого алгоритма быстрее растет при росте n.
"хэш-таблица отработает за O(L)"
Все равно за O(1).
Я допускаю, что тебе это не нужно, но вообще это метод решения очень большого класса проблем (тот же квиксорт и динамическое программирование растут именно отсюда).
Ты переооцениваешь сложность навыка. Или ты про алгоритмы на графах?
Достаточно потратить пару вечеров на доказывание классических алгоритмов на графах (которые всяко полезнее и применимее тех же сортировок, и доказывается через эту самую индукцию) и шансы резко повысятся.
Вот соглашусь. Квиксорт я могу воспроизвести не задумываясь (потому что общая идея описывается одним предложением), а пузырек надо вспоминать с бумажкой.
Если вы вызубрили quicksort, но не понимаете как он устроен и почему — толку от таких знаний нет.
Хэш-таблицы имеют хорошую амортизированную асимптотику, но это совсем не значит, что в общем случае они ищут быстрее или медленнее.
Меня учили в вузе.
Понимаете, из ваших статей рисуется образ человека, который собрал в своей карьере все возможные грабли, которые мог собрать разработчик, включая граблю непризнанного гения. Мне сложно поверить, что так бывает, это выглядит как собирательный образ, созданный человеком (или группой людей), которые очень хорошо понимают какие грабли бывают и куда надо давить. Думаю, не только мне, отсюда и теории заговора у людей.
Вы знаете, надо быть очень сильным синьором, чтобы так качественно и целенаправленно цеплять людей за больные места и косить под "миллениала в кедах".
То что статья написана с целью вызвать ещё один срачик (как и прошлые) — очевидно.
У меня такое ощущение возникло ещё в момент вброса про синьоров и virtual (ну просто потому что так не бывает), но хочется верить в хорошее.
Знаете, я бы ни слова не сказал, если бы в статье просто описывался подход и лежала ссылка на гитхаб. Но эти крайне интересные подробности про плохих менеджеров и удаленные исходники...
Уверен, что вам не ответят, но у комментария появятся ровно два минуса.
Собственно, я бы с удовольствием сам посравнивал, да вот проблема — работающей библиотеки у пацанов нет и сравнивать не с чем. А какое угодно, но работающее решение заведомо лучше удаленного (если оно вообще работало).
Почему вы думаете что рядом ошибаются?
Если пацаны так ценят хорошую инженерию, то они могли поступить как инженеры — поискать готовые решения, сравнить, выделить плюсы и минусы, сделать прототип своего и дать менеджеру цифры. Это принятый у профессионалов способ доносить вещи.