Всё ещё в поисках алгоритмического дзена
Не так давно прочитал статью «В поисках алгоритмического дзена», где автор обсуждает подходы к использованию алгоритмов в рабочих задачах. В статье подчеркивается, что даже наивная реализация конкретного алгоритма будет быстрее готовых средств/реализаций, существующих в платформе, и уж тем более будет быстрее специальный алгоритм для данного конкретного случая. Возникает ощущение, что использование самописных алгоритмов обладает абсолютным преимуществом над использованием готовых реализаций. С этой точкой зрения я не могу согласиться.
Стоит ли использовать специальные алгоритмы?
На этот вопрос нельзя дать однозначный ответ. Всё зависит от контекста, в котором будет работать алгоритм.
Если у нас хайлоад и метод находится в горячей секции, там самописные алгоритмы могут быть очень полезны, и использование более сложного в поддержке кода вполне оправдано.
В других случаях, я бы не стал торопиться добавлять алгоритмы, во всяком случае до проведения нагрузочных тестов, просмотра метрик системы и прочего.
В этой статье я постараюсь показать почему использование самописного алгоритма не всегда оправдано, даже если он работает значительно быстрее. А также предложу некоторый компромиссный вариант оптимизации.
Постановка задачи
Если речь идет не об олимпиадном программировании, а о реальной задаче, то всегда важно понимать, что именно мы делаем, в каких условиях, и, главное, для чего будет использоваться наш код.
Давайте рассмотрим такую задачу:
Допустим, у нас есть сайт, на котором разные авторы публикуют свои статьи оригинальная идея, все совпадения случайны. После публикации мы показываем некоторую статистику по этой статье.
И, собственно, наша сегодняшняя задача — добавить самое длинное слово из статьи в статистику. Для чего? Чтобы мериться длиной слов, конечно!
Реализация
Автор оригинальной статьи предлагает такой алгоритм. Его я и буду рассматривать (далее в тексте называю его просто 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
public string GetLongestWordMemory(string s, SearchValues separators)
{
ReadOnlyMemory memory = s.AsMemory();
var maxWord = memory.SplitAny(separators).MaxBy(w => w.Length);
return maxWord.ToString();
}
Код не стал сильно сложнее, алгоритм не поменялся, мы всё так же разбиваем текст на слова, но теперь вместо строк, мы создаем структуры типа ReadOnlyMemory которые по сути являются просто указателями на диапазон в исходном массиве символов.
Посмотрим, что получилось:
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 IsWordPredicate = str => str.Count(c => c == '-') < 3;
public string GetLongestWordSplit(string s, char[] separators, Func 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 separators, SpanPredicate predicate)
{
ReadOnlyMemory 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 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 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 separators, SpanPredicate predicate, int count)
{
ReadOnlyMemory 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 predicate, int count)
{
int maxlen = 1;
int maxindex = -1;
SortedSet 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 — Сложность
На мой взгляд, это самая главная проблема данного подхода в целом и этого алгоритма в частности. Его сложно читать. А добавьте сюда корректную реализацию со списком самых длинных слов, и там уже без ста грамм не разберешься.
Даже Райдеру не нравится этот метод:
Rider’у тоже сложно понять, что тут написано
Cognitive Complexity = 41
Для сравнения, методы Split и Memory имеют Cognitive Complexity = 0! Они линейные и супер очевидные. В них не страшно вносить изменения, и самое главное — это можно делать быстро!
Так что в итоге?
Отвечу на вопрос «Какой код вы чаще пишете?», заданный в оригинальной статье.
В первую очередь, я пишу код для людей. Он должен легко читаться, поддерживаться и меняться по мере необходимости. Алгоритмы или нет, в данном контексте не важно, код в любом случае придется поддерживать.
Во-вторых, я пишу код, который учитывает возможности и ограничения используемой платформы. Современные языки/платформы предоставляют кучу готовых алгоритмов, структур данных, которые могут сильно улучшить производительность без необходимости писать сложный код. Самое главное — их правильное использование. Все эти ReadOnlyMemory вместо строки, SearchValues вместо линейного поиска в массиве, SortedSet (красно-черное дерево) вместо того же массива, мало знать, что они существуют, необходимо понимать в каком случае их применять, где они будут эффективны.
И вот этот навык, на мой взгляд, гораздо более ценен для программиста, чем знание каких-либо специальных алгоритмов. И вот такие оптимизации можно делать сразу, даже нужно если они не противоречат первому пункту.
На техническом интервью я часто прошу кандидата рассказать, как бы он написал аналог метода Except из LINQ: задача, которую можно решить вложенным циклом, за квадратичное время, или за линейное, но уже с применением структур данных из фреймворка.
И большое количество кандидатов, всего пару минут назад рассказывавших мне что такое хэш-таблица, не знают, как решить эту задачу за линейное время.
И только когда мне уже не хватает стандартного набора, предоставленного платформой, и есть реальная потребность в оптимизации, вот тогда настает время алгоритмов!
А начинать писать свой алгоритм сразу, в самом начале, я считаю очень вредной практикой, даже если он работает в 27 раз быстрее. Эта разница может быть совершенно не заметна в метриках целой системы. Её съедят сетевые задержки, обращения к БД и куча всего прочего, что у нас есть в реальном продукте. А вот стоимость поддержки такой системы возрастает значительно.
