Не так давно прочитал статью "В поисках алгоритмического дзена", где автор обсуждает подходы к использованию алгоритмов в рабочих задачах. В статье подчеркивается, что даже наивная реализация конкретного алгоритма будет быстрее готовых средств/реализаций, существующих в платформе, и уж тем более будет быстрее специальный алгоритм для данного конкретного случая. Возникает ощущение, что использование самописных алгоритмов обладает абсолютным преимуществом над использованием готовых реализаций. С этой точкой зрения я не могу согласиться.
Стоит ли использовать специальные алгоритмы?
На этот вопрос нельзя дать однозначный ответ. Всё зависит от контекста, в котором будет работать алгоритм.
Если у нас хайлоад и метод находится в горячей секции, там самописные алгоритмы могут быть очень полезны, и использование более сложного в поддержке кода вполне оправдано.
В других случаях, я бы не стал торопиться добавлять алгоритмы, во всяком случае до проведения нагрузочных тестов, просмотра метрик системы и прочего.
В этой статье я постараюсь показать почему использование самописного алгоритма не всегда оправдано, даже если он работает значительно быстрее. А также предложу некоторый компромиссный вариант оптимизации.
Постановка задачи
Если речь идет не об олимпиадном программировании, а о реальной задаче, то всегда важно понимать, что именно мы делаем, в каких условиях, и, главное, для чего будет использоваться наш код.
Давайте рассмотрим такую задачу:
Допустим, у нас есть сайт, на котором разные авторы публикуют свои статьи оригинальная идея, все совпадения случайны. После публикации мы показываем некоторую статистику по этой статье.
И, собственно, наша сегодняшняя задача - добавить самое длинное слово из статьи в статистику. Для чего? Чтобы мериться длиной слов, конечно!
Реализация
Автор оригинальной статьи предлагает такой алгоритм. Его я и буду рассматривать (далее в тексте называю его просто Jump). Для удобства использования я обернул его в C# метод.
public string GetLongestWordJump(string str) { // Jump int maxlen = 1; int maxindex = -1; for (int i = 0; i < str.Length - maxlen;) { if (char.IsAsciiLetter(str[i])) { int index = i; i += maxlen; if (i < str.Length && char.IsAsciiLetter(str[i])) { do { i--; } while (i > index && char.IsAsciiLetter(str[i])); if (i == index) { for (i += maxlen + 1; i < str.Length && char.IsAsciiLetter(str[i]); i++) ; if (maxlen < (i - index)) { maxindex = index; maxlen = i - index; } continue; } } else continue; } i++; } return str.Substring(maxindex, maxlen); }
И, собственно, метод, не использующий никакие специальные алгоритмы, только возможности платформы.
public string GetLongestWordSplit(string str) { string[] strings = str.Split(new[]{' ', ',', '.'}, StringSplitOptions.RemoveEmptyEntries); return strings.MaxBy(m => m.Length); }
Сравниваем производительность (Бенчмарк из оригинальной статьи)
Method | Length | Mean | Allocated |
|---|---|---|---|
Jump | 1 | 804.8 us | 66 B |
Split | 1 | 22,075.9 us | 6490169 B |
Разница в 27.5 раз, да еще и версия со Split аллоцирует кучу памяти.
Казалось бы, ответ очевиден - специальный алгоритм выигрывает с разгромным счетом! Так почему же я не пропустил бы его на код-ревью?
Потому что я люблю, когда программы работают медленно, а пользователи страдают
Тут есть сразу несколько пунктов, и о них по прядку:
Проблема №1 - Алгоритм Jump и Split работают по-разному
Оба алгоритма возвращают самое длинно слово. Но что считать словом? Для Split это все что разделено конкретными перечисленными символами, но для Jump — это не так, здесь все что не IsAsciiLetter является разделителем.
Например, слова что-то, AC/DC, 2pac, I2C и прочие вполне себе законные слова будут посчитаны неверно (У нас же хипстерское современное издание)
Но не волнуйтесь, это легко справить:
public string GetLongestWordJump(string str, char[] separators) { int maxlen = 1; int maxindex = -1; for (int i = 0; i < str.Length - maxlen;) { if (Array.IndexOf(separators, str[i]) == -1) { int index = i; i += maxlen; if (i < str.Length && Array.IndexOf(separators, str[i]) == -1) { do { i--; } while (i > index && Array.IndexOf(separators, str[i]) == -1); if (i == index) { for (i += maxlen + 1; i < str.Length && Array.IndexOf(separators, str[i]) == -1; i++) ; if (maxlen < (i - index)) { maxindex = index; maxlen = i - index; } continue; } } else continue; } i++; } return str.Substring(maxindex, maxlen); }
И наш метод тоже
public string GetLongestWordSplit(string str, char[] separators) { string[] strings = str.Split(separators, StringSplitOptions.RemoveEmptyEntries); return strings.MaxBy(m => m.Length); }
Но что же теперь с метриками?
Здесь и далее будут уже мои метрики, я использовал только 2 значения для сравнения: строка из 100 символов (small) и текст целой книги на 700 KB (big)
Method | Length | Mean | Allocated |
|---|---|---|---|
Jump | small | 162.1 ns | 48 B |
Split | small | 384.5 ns | 896 B |
Jump | big | 267,960.8 ns | 96 B |
Split | big | 5,374,091.3 ns | 3428452 B |
Разница все еще значительна, но уже не так впечатляет: 2.4 раза на маленькой строке, и внушительные 20 раз на целой книге. По-прежнему остаются аллокации. Алгоритм всё ещё чертовски хорош на больших текстах, но для текстов малого размера преимущества уже не так очевидны.
Сможем ли мы сделать лучше средствами платформы?
Проблема Split в том, что он создаёт большое количество объектов типа "строка", которые нам не особо нужны, мы у них смотрим только длину и потом выбрасываем. К счастью, в .NET появились и альтернативные методы работы с текстовой информацией. Знакомьтесь наш герой - ReadOnlyMemory<char>
public string GetLongestWordMemory(string s, SearchValues<char> separators) { ReadOnlyMemory<char> memory = s.AsMemory(); var maxWord = memory.SplitAny(separators).MaxBy(w => w.Length); return maxWord.ToString(); }
Код не стал сильно сложнее, алгоритм не поменялся, мы всё так же разбиваем текст на слова, но теперь вместо строк, мы создаем структуры типа ReadOnlyMemory<char> которые по сути являются просто указателями на диапазон в исходном массиве символов.
Посмотрим, что получилось:
Metho | Length | Mean | Allocated |
|---|---|---|---|
Jump | small | 162.1 ns | 48 B |
Split | small | 384.5 ns | 896 B |
Memory | small | 360.1 ns | 224 B |
Jump | big | 267,960.8 ns | 96 B |
Split | big | 5,374,091.3 ns | 3428452 B |
Memory | big | 1,048,895.8 ns | 273 B |
На малом размере строки разница не особо видна, но вот на целой книге - сильно лучше: всего в 4 раза медленнее чем Jump, и практически нет аллокаций.
Проблема №2 - Доработки
Куда же без них! За всю свою карьеру я, наверное, не видел ни одной фичи, которую не приходилось бы менять и дорабатывать со временем. Хорошо написанный код готов к изменениям и расширению функционала. Чем проще код, тем меньше времени занимают доработки, а значит меньше стоимость поддержки. Это ли не показатель качества кода?
А что же у нас с готовность к изменениям в наших реализациях?
Правим раз
Мы реализовали наш алгоритм, он хорошо работает на тестовых данных, но проверка на реальных текстах показала, что набора символов ' ', ',', '.' недостаточно для разделения слов. Конечно, мы легко можем расширить этот набор, но этого всё ещё может оказаться недостаточно.
В текущей реализации у нас разрешены цифры и дефисы в словах (мы так и хотим), но тогда и такой набор символов 4892C218-C638-4C5E-8BC1-7EB972A4C6C6 тоже является словом. А вот это уже наших пользователей не устроило.
Пришло новое требование от аналитики: не более двух дефисов в слове, если больше, то словом вообще не считается.
Требование есть - придётся править:
Мы же с вами разработчики опытные, не будем вносить это условие в сам алгоритм, а попросим передавать его извне, параметром:
//где-то в коде Func<string, bool> IsWordPredicate = str => str.Count(c => c == '-') < 3; public string GetLongestWordSplit(string s, char[] separators, Func<string, bool> predicate) { string[] strings = s.Split(separators, StringSplitOptions.RemoveEmptyEntries); var max = strings .Where(predicate) .MaxBy(m => m.Length); return max; }
Нет ничего проще, добавили один параметр и один оператор LINQ, читаемость кода всё ещё отличная!
То же самое будет и с улучшенной версией (Memory):
public string GetLongestWordMemory(string s, SearchValues<char> separators, SpanPredicate predicate) { ReadOnlyMemory<char> memory = s.AsMemory(); var maxWord = memory.SplitAny(separators) .Where(w => predicate(w.Span)) .MaxBy(w => w.Length); return maxWord.ToString(); }
А вот для метода Jump придётся разобраться в работе алгоритма, потому что уже не так очевидно, в какой момент нужно проверять слово это или нет.
public string GetLongestWordJump(string str, char[] separators, Func<string, bool> predicate) { int maxlen = 1; int maxindex = -1; for (int i = 0; i < str.Length - maxlen;) { if (Array.IndexOf(separators, str[i]) == -1) { int index = i; i += maxlen; if (i < str.Length && Array.IndexOf(separators, str[i]) == -1) { do { i--; } while (i > index && Array.IndexOf(separators, str[i]) == -1); if (i == index) { for (i += maxlen + 1; i < str.Length && Array.IndexOf(separators, str[i]) == -1; i++) ; if (maxlen < (i - index)) { var word = str[index..i]; if (predicate(word)) { maxindex = index; maxlen = i - index; } } continue; } } else continue; } i++; } return str.Substring(maxindex, maxlen); }
Тесты проходят, а значит самое время посмотреть бенчмарки:
Method | Length | Mean | Allocated |
|---|---|---|---|
Jump | small | 426.2 ns | 360 B |
Split | small | 877.2 ns | 1808 B |
Memory | small | 572.2 ns | 296 B |
Jump | big | 567,655.5 ns | 1856 B |
Split | big | 12,390,896.9 ns | 7530546 B |
Memory | big | 2,943,862.7 ns | 330 B |
Jump всё ещё быстрее всех. На малых строках разница не особо заметна: с оптимизированной версией почти паритет, и в 2 раза быстрее чем Split. Однако на целой книге разница существенна: в 22 раза быстрее чем Split и в 5 раз чем Memory.
Этого и следовало ожидать: Split и Memory вызывают проверку для каждого слова, а Jump только для слова с длиной больше максимальной. Расплата за простоту.
Правим два
Приходит новое требование (а куда же мы без этого): теперь нужно отображать не одно самое длинное слово, а ТОП 3.
Ну, вроде бы, ничего сложного, приключение на 20 минут приступим:
public string[] GetTopLongestWordsSplit(string s, char[] separators, Func<string, bool> predicate, int count) { string[] strings = s.Split(separators, StringSplitOptions.RemoveEmptyEntries); var top = strings .Where(predicate) .Distinct() .OrderByDescending(w => w.Length) .Take(count) .ToArray(); return top; }
Убрали повторения, отсортировали по длине, взяли сколько требуется, всё очевидно.
И тоже самое с Memory, только ещё Memory в строку конвертировать нужно.
public string[] GetTopLongestWordsMemory(string s, SearchValues<char> separators, SpanPredicate predicate, int count) { ReadOnlyMemory<char> memory = s.AsMemory(); var top = memory.SplitAny(separators) .Where(w => predicate(w.Span)) .Distinct() .OrderByDescending(w => w.Length) .Take(count) .Select(w => w.ToString()) .ToArray(); return top; }
А вот с Jump не всё так очевидно...
Я уверен, есть какой-то крутой алгоритм, особенно хорошо решающий данную проблему, но я буду пользоваться тем, что предоставляет .net. А именно, Буду добавлять слова в SortedSet, и удалять наименьший элемент при превышении количеством элементов заданного числа.
public string[] GetTopLongestWordsJump(string str, char[] separators, Func<string, bool> predicate, int count) { int maxlen = 1; int maxindex = -1; SortedSet<string> res = new(new StringLenComparer()); for (int i = 0; i < str.Length - maxlen;) { if (Array.IndexOf(separators, str[i]) == -1) { int index = i; i += maxlen; if (i < str.Length && Array.IndexOf(separators, str[i]) == -1) { do { i--; } while (i > index && Array.IndexOf(separators, str[i]) == -1); if (i == index) { for (i += maxlen + 1; i < str.Length && Array.IndexOf(separators, str[i]) == -1; i++) ; if (maxlen < (i - index)) { var word = str[index..i]; if (predicate(word)) { maxindex = index; maxlen = i - index; res.Add(word); if (res.Count > 10) { res.Remove(res.Min!); } } } continue; } } else continue; } i++; } return res.Reverse().ToArray(); }
А что там по бенчмаркам?
Method | Length | Mean | Allocated |
|---|---|---|---|
Jump | small | 558.3 ns | 792 B |
Split | small | 1,257.2 ns | 2584 B |
Memory | small | 1,127.3 ns | 2016 B |
Jump | big | 513,280.5 ns | 2584 B |
Split | big | 12,390,896.9 ns | 7530546 B |
Memory | big | 3,880,643.8 ns | 2565209 B |
Jump опять выигрывает: в 2 раза лучше на коротком тексте, а на длинном - в 7.5 лучше оптимизированного варианта, и в 22 раза лучше, чем Split. Отличный результат!
Вот только результат выдаёт неверный. А вы нашли ошибку в алгоритме? Заметили бы её на код-ревью? Сколько займет времени чтобы её поправить?
Да, конечно, это можно было покрыть тестами... От таких ошибок должны спасать именно они, а не ревью... Всё верно, так и должно быть...
Вносить изменения в алгоритм Jump будет гораздо сложнее, особенно если это будет делать не тот программист, который его писал изначально. Необходимо вникнуть в детали метода, понять, что происходит в каждом цикле. Я не утверждаю, что это невозможно, или так делать нельзя, но это явно будет дороже.
Проблема №3 - Сложность
На мой взгляд, это самая главная проблема данного подхода в целом и этого алгоритма в частности. Его сложно читать. А добавьте сюда корректную реализацию со списком самых длинных слов, и там уже без ста грамм не разберешься.
Даже Райдеру не нравится этот метод:
Cognitive Complexity = 41
Для сравнения, методы Split и Memory имеют Cognitive Complexity = 0! Они линейные и супер очевидные. В них не страшно вносить изменения, и самое главное — это можно делать быстро!
Так что в итоге?
Отвечу на вопрос "Какой код вы чаще пишете?", заданный в оригинальной статье.
В первую очередь, я пишу код для людей. Он должен легко читаться, поддерживаться и меняться по мере необходимости. Алгоритмы или нет, в данном контексте не важно, код в любом случае придется поддерживать.
Во-вторых, я пишу код, который учитывает возможности и ограничения используемой платформы. Современные языки/платформы предоставляют кучу готовых алгоритмов, структур данных, которые могут сильно улучшить производительность без необходимости писать сложный код. Самое главное - их правильное использование. Все эти ReadOnlyMemory вместо строки, SearchValues вместо линейного поиска в массиве, SortedSet (красно-черное дерево) вместо того же массива, мало знать, что они существуют, необходимо понимать в каком случае их применять, где они будут эффективны.
И вот этот навык, на мой взгляд, гораздо более ценен для программиста, чем знание каких-либо специальных алгоритмов. И вот такие оптимизации можно делать сразу, даже нужно если они не противоречат первому пункту.
На техническом интервью я часто прошу кандидата рассказать, как бы он написал аналог метода Except из LINQ: задача, которую можно решить вложенным циклом, за квадратичное время, или за линейное, но уже с применением структур данных из фреймворка.
И большое количество кандидатов, всего пару минут назад рассказывавших мне что такое хэш-таблица, не знают, как решить эту задачу за линейное время.
И только когда мне уже не хватает стандартного набора, предоставленного платформой, и есть реальная потребность в оптимизации, вот тогда настает время алгоритмов!
А начинать писать свой алгоритм сразу, в самом начале, я считаю очень вредной практикой, даже если он работает в 27 раз быстрее. Эта разница может быть совершенно не заметна в метриках целой системы. Её съедят сетевые задержки, обращения к БД и куча всего прочего, что у нас есть в реальном продукте. А вот стоимость поддержки такой системы возрастает значительно.
