Не так давно прочитал статью "В поисках алгоритмического дзена", где автор обсуждает подходы к использованию алгоритмов в рабочих задачах. В статье подчеркивается, что даже наивная реализация конкретного алгоритма будет быстрее готовых средств/реализаций, существующих в платформе, и уж тем более будет быстрее специальный алгоритм для данного конкретного случая. Возникает ощущение, что использование самописных алгоритмов обладает абсолютным преимуществом над использованием готовых реализаций. С этой точкой зрения я не могу согласиться.
Стоит ли использовать специальные алгоритмы?
На этот вопрос нельзя дать однозначный ответ. Всё зависит от контекста, в котором будет работать алгоритм.
Если у нас хайлоад и метод находится в горячей секции, там самописные алгоритмы могут быть очень полезны, и использование более сложного в поддержке кода вполне оправдано.
В других случаях, я бы не стал торопиться добавлять алгоритмы, во всяком случае до проведения нагрузочных тестов, просмотра метрик системы и прочего.
В этой статье я постараюсь показать почему использование самописного алгоритма не всегда оправдано, даже если он работает значительно быстрее. А также предложу некоторый компромиссный вариант оптимизации.
Постановка задачи
Если речь идет не об олимпиадном программировании, а о реальной задаче, то всегда важно понимать, что именно мы делаем, в каких условиях, и, главное, для чего будет использоваться наш код.
Давайте рассмотрим такую задачу:
Допустим, у нас есть сайт, на котором разные авторы публикуют свои статьи оригинальная идея, все совпадения случайны. После публикации мы показываем некоторую статистику по этой статье.
И, собственно, наша сегодняшняя задача - добавить самое длинное слово из статьи в статистику. Для чего? Чтобы мериться длиной слов, конечно!
Реализация
Автор оригинальной статьи предлагает такой алгоритм. Его я и буду рассматривать (далее в тексте называю его просто 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 раз быстрее. Эта разница может быть совершенно не заметна в метриках целой системы. Её съедят сетевые задержки, обращения к БД и куча всего прочего, что у нас есть в реальном продукте. А вот стоимость поддержки такой системы возрастает значительно.
