Комментарии 17
В большинстве случаев использование алгоритмов действительно может ускорить работу систем, сделать их компактнее, унифицировать участки кода.
Очередной раз, когда путают какое-то абстрактное "знание алгоритмов" и умение оценить сложность алгоритма по времени и по памяти. У меня вот бесполезно спрашивать алгоритм Дейкстры или решето Эратосфена. Зато я регулярно обнаруживаю на код-ревью линейную сложность вместо константной.
В этой статье я собрал примерный список алгоритмов, которые использую в работе с высоконагруженным проектом с большой кодовой базой.
Т.е. берём бинарный и рекурсивный поиски с сортировкой выбором и наше высоконагруженное приложение взлетает на раз? Оке-е-ей.
Из личного опыта.
Часто приходится работать с различными кешами. И тут ситуация двоякая. Есть кеши разного рода настроек, которые читаются один раз при старте и затем многократно используются (поиск по ключу). И есть кеши, которые постоянно меняются (элементы добавляются/удаляются).
Для сравнения два алгоритма
Сортированный массив структур ключ+данные с сортировкой и двичным поиском по ключу
Динамический список, основанный на алгоритме SkipList (не требует отдельной сортировки, при добавлении нового элемента он сразу "встает на место").
И вот такое вот сравнение.
Статический кеш с однократным заполнением (один раз заполнили и отсортировали, много раз ищем), 131 184 уникальных элементов
Заполнение и сортировка массива 0.274087 сек, поиск по массиву (суммарно для каждого элемента в случайном порядке) 0.082968 сек.
Для списка SkipList - заполнение 1.016377 сек, поиск - 0.789519 секДинамический кеш (добавли элемент, отсортировали, ищем, удалили, отсортировали, ищем, добавили, отсортировали, ищем и т.п.). То же самое количество элементов. Тут все радикально меняется:
Для сортированного массива имеем катастрофический провал производительности - изменения содержимого кеша с пересортировками после каждого изменения занимает суммарно 2258.823760 сек, В то время как SkipList показывает тот же самый результат - 0.990625 сек
Вывод такой - несмотря на то, что двоичный поиск является самым быстрым (в общем случае), он требует сортировки, являющейся достаточно дорогим удовольствием. Это оправдывает себя в том случае, когда количество изменений массива, требующих последующей пересортировки, многократно меньше (в идеале, однократно) количества поисков в нем.
В идеале для динамических кешей нужно писать свой алгоритм, который позволит вносить изменения в данные без последующей полной пересортировки всего массива (например, поиск подходящего места и вставка нового элемента "по месту".
...удалили, отсортировали...
Вам, должно быть, очень сортировать нравится, но вообще-то удаление элемента не нарушает порядка оставшихся.
Да и вставка при помощи insort() выйдет подешевле, чем просто вставка/сортировка.
Про удаление - да. Но обычно там речь идет о добавлении элементов. Или изменении ключевого значения.
К сожалению, вставка в массив не такое простое дело - оно связано со сдвижкой элементов после вставки (это если это классический массив, а не что-то иное). Что тоже не бесплатно.
Так что в любом случае надо смотреть что в итоге будет работать быстрее - сортированный массив или сортированный список.
Ну ежели вставлять и удалять активно и ключ для словаря не сделаешь, тут стоит смотреть в сторону бинарного дерева. В зависимости от задачи может быть вообще куча подойдет
Можно использовать хэш-таблицу.
Так для "динамических кешей" может пригодятся более эффективные структуры данных нежели использование массива и его сортировки? Здесь и сравнивать бессмысленно метод "бинпоиск" со структурой данных SkipList. Допустим не вижу никаких проблем использовать к/ч дерево чисто для вашей задачи, где поиск элемента и есть по своей сути бинарный поиск.
В комментариях под статьёй, что вы предоставили, сравнили к/ч дерево и SkipList, к сожалению SkipList оказался медленнее почти в 2 раза. (все-таки обе структуры имеют логарифмическую сложность, но так как у SkipList в основе вероятностный алгоритм, то бывают так называемые выбросы, из-за которых придется потратить чуток поболее времени).
И какой вывод тогда?
Конечно, стоит использовать тот или иной инструмент не потому что о нём написали в статье и сказали что log(n) -- это очень круто, но и впадать в другую крайность бессмысленно. Иногда простейший бинарный поиск оказывается ни чем не хуже, а может даже и лучше каких-то замудрёных математических штук.
Бинарный поиск
Это алгоритм поиска, который работает только в отсортированном списке. На вход отдаём отсортированный список, а на выходе получаем позицию нужного нам элемента, если он присутствует в списке.
Только что выше определили структуры данных массив и связный список, а алгоритм поиска вводим на «списке»… Думаю, не-Java программистов это собьёт с толку.
Вы серьёзно? Где-то в Platform V DataSpace есть написанная вами реализация бинарного поиска и сортировки выбором? Зачем?
При этом нотация рассматривает худший сценарий, то есть позволяет определить, что алгоритм не будет работать медленнее O(n).
Нет, не совсем так. Алгоритм может потребовать для своей реализации (сто_тыщ_миллиардов * n) итераций, и всё равно он будет O(n), т. к. нотация O - характеристика асимптотической сложности алгоритма без учета константы.
Нотация O показывает нам общее направление движения, а там еще может профилироваться придется до потери пульса...
И, Александр, попросите, пожалуйста, PR службу Сбера по возможности не использовать AI-generated иллюстрации для корпоративного блога, выглядит прям очень не очень. В конце концов, если уж они отрывают вас от работы для написания статей, то, наверное, могут потратить сотню долларов на работу нормального художника.
private static int binarySearch(int[] sortedArray, int value, int low, int high) { ... }
Что за параметры low и high и зачем они в данном примере? Ведь в linearSearch нет таких параметров.
И вместо "Сортировка выбором" у вас функция linearSearch.
Когда-то (в 94...95-м) считался крутым математиком по вышке, потому и зацепило ваше "что такое логарифм"
Навскидку, (про математический смысл) как с листа -- это потенцирование диффура n-го порядка для приведения к частному виду (решаемому) неопределённого интеграла, по результатам которого , по граничным значениям аргумента, строится логарифмический график, умещающийся на листе А4 (в противном случае график не уместился бы и в формате 4*А0)) -- в этом заключался физический смысл потенцирования.
Как бы так)
хз, чел расписал самые дефолтные алгоритмы которые даже ребенок написать сможет, причем некоторые написаны странно и их можно написать эффективнее
Слово "высоконагруженного" в названии статьи вводит в заблуждение. Ожидал что-то из HiLoad, а прочитал это?
Если в пример взяли 57, то оно найдётся перебором на 57 итерации, а не иначе 100. А 1, найдётся на первой, что в 7 раз быстрее. По поводу времени итерации для каждого метода - они будут равны, только если равно количество математических операций на аппаратном уровне. Взять число и проверить, явно проще чем рассчитать его на основе других, и менее ресурсоемко. Исходя из этого, мне кажется тут два конца палки - быстро и затратно, медленно но бесплатно.
Разбираемся в «базовых» алгоритмах для проекта