За последний год было достаточно статей, как с высокой оценкой необходимости знания алгоритмов, так и умеренных и радикальных. Я скорее отношусь к умеренным, но всё же считаю, что всегда важен сам контекст задачи.
В любом случае в этой небольшой статье я затрону весьма простую задачу - поиск самого длинного слова в строке.
Сразу покажу код на питоне, актуальный для многих языков высокого уровня (со страниц StackOverflow):
s = "a aa aaa aa"
max(s.split(), key=len)Суть этого примера в том, что многие простейшие задачи оборачивают в готовые методы актуального ЯП, что в первую очередь решает основную задачу бизнеса - быструю разработку. Опосредовано - это уменьшает размер кода, причем не всегда с заботой о наших SSD, а скорее с заботой о крупных серверах, что так же влияет на скорость парсинга.
Мои же примеры будут на C#, не претендую на уникальность и божественную красоту кода, это только моё хобби. Моя цель - лишь донести мысль.
Наивный старт
Для примера у нас будет строка с каким-то стишком с просторов интернета:
string str = "I have a friend Whose name is... And we have fun together. We laugh and play And sing all day In any kind of weather.";Самое длинное слово together 8 символов.
Любой наивный алгоритм, по своей сути, реализует концепцию простейшего решения "в лоб". Для этой задачи наивным будет алгоритм обхода всех символов строки с подсчётом непрерывных последовательностей букв, что и формирует такой элемент строки как слово. Сразу скажу, что задача по сложности O(n) вне зависимости от реализации, поэтому критерием у нас будет - производительность, то есть мы будем изучать тот самый коэффициент k который в нотации BigO всегда отбрасывается.
// Naive
int maxlen = 1;
int maxindex = -1;
int temp_maxlen = 0;
int temp_maxindex = 0;
bool solidword = false;
int i = 0;
while (i < str.Length)
{
if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
{
if (!solidword)
{
temp_maxindex = i;
solidword = true;
}
temp_maxlen++;
}
else
{
if (solidword && temp_maxlen > maxlen)
{
maxlen = temp_maxlen;
maxindex = temp_maxindex;
}
temp_maxlen = 0;
solidword = false;
}
i++;
}
Console.WriteLine("Длина = {0}, слово = {1}", maxlen, str.Substring(maxindex, maxlen));Тут подпилить, там подкрасить...
Мы можем избавиться от переменной solidwordи от блока с else. Теперь мы будем искать начало слова пропуская остальные символы, а когда начало найдено - считать сколько букв идёт подряд.
// SkipWord
int maxlen = 1;
int maxindex = -1;
int temp_maxlen = 0;
int temp_maxindex = 0;
int i = 0;
while (i < str.Length)
{
if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
{
temp_maxlen = 0;
temp_maxindex = i;
do
{
temp_maxlen++;
i++;
}
while (((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')) && i < str.Length);
if (temp_maxlen > maxlen)
{
maxlen = temp_maxlen;
maxindex = temp_maxindex;
}
}
i++;
}
Console.WriteLine("Длина = {0}, слово = {1}", maxlen, str.Substring(maxindex, maxlen));Имея на руках две реализации можем посмотреть как они себя поведут в бенчмарке (Length - кратное увеличение размера строки, чтобы смотреть как ведет себя реализация на больших данных):
| Method | Length | Mean |
|------------|--------|--------------|
| SkipWord | 1 | 199.9 ns |
| Naive | 1 | 283.9 ns |
|------------|--------|--------------|
| SkipWord | 100 | 18,964.9 ns |
| Naive | 100 | 25,586.9 ns |
|------------|--------|--------------|
| SkipWord | 1000 | 188,669.3 ns |
| Naive | 1000 | 254,468.1 ns |Наивный способ ожидаемо на последнем месте.
А что же C#?
Используем LINQ. И тут мы видим нечто похожее на то, что я специально показал в самом начале на питоне, я только добавил чуть больше разделителей в строку:
// Agregate
string word = str.Split(' ', ',', '.').Aggregate(string.Empty, (seed, f) => (f == null ? 0 : f.Length) > seed.Length ? f : seed);
Console.WriteLine("Длина = {0}, слово = {1}", word.Length, word);Ну и конечно бенчмарк:
| Method | Length | Mean |
|-----------|--------|----------------|
| SkipWord | 1 | 197.5 ns |
| Naive | 1 | 280.7 ns |
| Agregate | 1 | 628.4 ns |
|-----------|--------|----------------|
| SkipWord | 100 | 18,910.3 ns |
| Naive | 100 | 25,494.7 ns |
| Agregate | 100 | 60,087.6 ns |
|-----------|--------|----------------|
| SkipWord | 1000 | 188,210.6 ns |
| Naive | 1000 | 253,552.4 ns |
| Agregate | 1000 | 1,415,382.6 ns |Можно записать конечно попроще, без Agregate:
// OrderBy
string word = str.Split(' ', ',', '.').OrderByDescending(s => s.Length).First();
Console.WriteLine("Длина = {0}, слово = {1}", word.Length, word);И бенчмарк:
| Method | Length | Mean |
|----------|--------|----------------|
| Agregate | 1 | 641.7 ns |
| OrderBy | 1 | 714.4 ns |
|----------|--------|----------------|
| Agregate | 100 | 58,891.5 ns |
| OrderBy | 100 | 64,705.9 ns |
|----------|--------|----------------|
| Agregate | 1000 | 1,381,087.1 ns |
| OrderBy | 1000 | 1,438,873.3 ns |Мы можем написать еще две реализации, одна будет использовать Split() для разделения строки на слова и работать с массивом строк, а вторая вместо архаичных интервалов в if будет использовать метод char.IsLetter()(точнее char.IsAsciiLetter() - у нас же английский текст). Ниже в бенчмарке опубликую их оба для сравнения:
// AsciiLetter
int maxlen = 1;
int maxindex = -1;
int temp_maxlen = 0;
int temp_maxindex = 0;
int i = 0;
while (i < str.Length)
{
if (char.IsAsciiLetter(str[i]))
{
temp_maxlen = 0;
temp_maxindex = i;
do
{
temp_maxlen++;
i++;
}
while (char.IsAsciiLetter(str[i]) && i < str.Length);
if (temp_maxlen > maxlen)
{
maxlen = temp_maxlen;
maxindex = temp_maxindex;
}
}
i++;
}
Console.WriteLine("Длина = {0}, слово = {1}", maxlen, str.Substring(maxindex, maxlen));// Split
string[] arr = str.Split(' ', ',', '.');
int index = 0;
for (int i = 1; i < arr.Length; i++)
if (arr[index].Length < arr[i].Length)
index = i;
Console.WriteLine("Длина = {0}, слово = {1}", arr[index].Length, arr[index]);| Method | Length | Mean |
|----------------|--------|----------------|
| AsciiLetter | 1 | 149.8 ns |
| Letter | 1 | 284.9 ns |
| Split | 1 | 751.1 ns |
|----------------|--------|----------------|
| AsciiLetter | 100 | 13,410.9 ns |
| Letter | 100 | 26,899.9 ns |
| Split | 100 | 72,257.9 ns |
|----------------|--------|----------------|
| AsciiLetter | 1000 | 138,026.1 ns |
| Letter | 1000 | 271,715.2 ns |
| Split | 1000 | 1,578,812.1 ns |Немножко в алгоритмы
Ну и наконец то, зачем мы все собрались. Есть группа алгоритмов по поиску подстроки в строке, которые уже неплохо описаны в статьях на Хабре. Я, например, читал эту. Из неё мы можем узнать про алгоритм Кнута-Морриса-Пратта, так же прыгая по вики можно узнать про еще один - Бойера-Мура.
Нашу задачу мы скорректируем так, чтобы применить некоторые из идей вышеобозначенных алгоритмов. Новое условие не будет противоречить основному условию задачи, но позволит существенно изменить сам подход к поиску, а именно:
Нам нужно найти слово, которое будет длиннее предыдущего.
Казалось бы - в чем разница? И причем тут вышеобозначенные алгоритмы? А дело всё в том, что нам нет нужды проверять все символы подряд, нам нужно совершать прыжки на длину последнего слова +1 символ и выполняя несколько проверочных действий или получать искомое или подготавливать почву для очередного прыжка.
А те алгоритмы, что я указал, как раз пытаются изменить подход к поиску таким образом, чтобы искать подстроки шагая некоторыми интервалами, которые и зависят от конкретного алгоритма.
Бонус, на который стоит рассчитывать - в случае, если прыжок будет попадать не на букву, то мы можем смело игнорировать все предыдущие символы, то есть максимальный положительный прыжок будет составлять длину максимально найденного слова плюс один символ.
// 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++;
}В текущей реализации происходит следующее - после прыжка, если мы попали на букву, то у нас складывается ситуация, схематично обозначенная ниже:
Где Б1 - это первая буква в слове, мы точно знаем о ней, Б2 - это просто какая-то буква, мы тоже точно знаем что это буква, но нам ничего неизвестно о промежутке Б1<->Б2 и о том, что после Б2.
Так как длина (Б1, Б2) ровно на 1 букву больше длины предыдущего самого длинного слова, то это для нас потенциальное решение. И в текущей реализации выбрано решение - двигаться от Б2 к Б1 проверяя на принадлежность буквам по всему интервалу. И у нас два возможных исхода: 1) из Б2 мы попадем в Б1 встретив только буквы и 2) мы встретим другой символ, схематично последнее будет выглядеть так:
В таком состоянии мы можем определить следующее - новое слово на этом отрезке не может быть сформировано и для следующего прыжка мы должны начать с позиции с буквой "C".
Почему с "C", а не сразу с Б2 или с символа за Б2? Потому что мы не знаем что за Б2, там может быть бескрайнее количество букв, так и например всего лишь 4 буквы и прыгая с Б2 или символом за Б2 мы пропустим новое слово из 8 букв, которое как раз начинается с позиции буквы "С":
Так же, если при проверке отрезка (Б2, Б1) мы встретим только буквы, нам следует продолжить поиск за пределами Б2. С этого момента мы точно знаем что мы нашли новое слово, и оно обязательно максимальное для этого участка строки, но двигаясь дальше, мы можем найти более длинное слово:
На примере выше мы смогли обнаружить еще 2 буквы за пределами Б2, тем самым найдя новое слово длиной в 10 букв. Но дальше мы не можем просто прыгнуть на 10 символов, нам сначала нужно найти начало нового потенциального слова (прыгнуть можно, но это абсолютно неэффективно, так как прыжок заведомо не в зоне предполагаемого нового слова и алгоритму придется, определив новую Б2 двигаться посимвольно и вполне вероятно оказаться на том самом пробеле, если остальные символы будут буквами - так мы будем делать лишнюю работу).
На примере выше я специально справа показал кроме запятой еще и пробел, то есть мы не можем знать в каком количестве и как расположены разделители для слов (если точно знаем, то это упрощает нам задачу). Поэтому мы продолжаем поиск букв с символа за ",".
Для отрезка (Б2, Б1) не подойдёт бинарный поиск, так как нужна 100%-я информация о буквах. Посмотрим на такую часть строки:
Мы знаем про букву "И" и прыгнули на 11 букв вперёд (10+1) и тоже узнали что там буква "Ч", но мы ничего не знаём о том, что внутри этого отрезка. И на примере видно, что там три пробела. В случае какого-то другого алгоритма поиска мы можем найти пробел например перед словом "ЗНАЛ" минуя пробел перед словом "ЧТО", что нам совсем никак не поможет. Поэтому поиск в обратном направлении решает сразу две задачи - ищет новое слово, то есть проверяет символы на принадлежность буквам и определяет позицию для следующего прыжка в случае если мы встретим другой символ. В нашем примере первый же шаг от "Ч" скажет нам однозначно, что можно делать следующий прыжок, так как мы встретим пробел.
Для тестовой строки, которую я использовал в этой статье, общее число итераций для этого алгоритма составило 66, при длине строки в 117 символов. То есть мы почти в 2 раза сократили число проверок.
У такого алгоритма есть лучший и худший случаи и они, конечно, зависят от того, насколько близко к началу строки находится самое длинное слово. Например если наше слово "together" поставить в начало строки, то число итераций уменьшится на 19 и составит 47, а в случае если все слова расположить в строке в порядке возрастания, то алгоритм найдёт самое длинное слово только в самом конце, но и в таком случае понадобится меньше итераций, а именно 81.
Финальный бенчмарк:
| Method | Length | Mean |
|----------------|--------|----------------|
| Jump | 1 | 117.6 ns |
| AsciiLetter | 1 | 149.1 ns |
| SkipWord | 1 | 198.7 ns |
| Naive | 1 | 282.9 ns |
| Letter | 1 | 284.4 ns |
| Agregate | 1 | 617.4 ns |
| OrderBy | 1 | 710.1 ns |
| Split | 1 | 752.9 ns |
|----------------|--------|----------------|
| Jump | 100 | 6,362.7 ns |
| AsciiLetter | 100 | 13,405.3 ns |
| SkipWord | 100 | 18,577.6 ns |
| Naive | 100 | 25,357.0 ns |
| Letter | 100 | 26,842.0 ns |
| Agregate | 100 | 58,716.9 ns |
| OrderBy | 100 | 63,863.6 ns |
| Split | 100 | 71,165.0 ns |
|----------------|--------|----------------|
| Jump | 1000 | 62,674.4 ns |
| AsciiLetter | 1000 | 137,721.3 ns |
| SkipWord | 1000 | 187,522.2 ns |
| Naive | 1000 | 254,050.8 ns |
| Letter | 1000 | 268,058.5 ns |
| Agregate | 1000 | 1,383,670.3 ns |
| OrderBy | 1000 | 1,469,519.7 ns |
| Split | 1000 | 1,519,161.3 ns |На больших строках: двукратное опережение лучшей реализации, а быстрее худшего варианта в 22.2 раза. Разница с наивной реализацией в 4 раза.
Ну и для полноты реальной картины (вряд ли кто-то будет что-то искать копируя одну и ту же строку), вот результат поиска в текстовой книжке (роман) на 840 килобайт размером:
| Method | Length | Mean | Allocated |
|--------------- |------ |------------:|----------:|
| Jump | 1 | 804.8 us | 66 B |
| Split | 1 | 22,075.9 us | 6490169 B |Код на стандартных методах ещё и скушал оперативной памяти 7.7N, ну а про производительность мы говорили выше, разница в ~27.5 раз. Что касается итераций и прыжков - реализация названная как Jump осуществила поиск за 252846 итераций для файла размером в 839328 байт. Размер найденного слова semiphosphorescent составил 18 букв, а средний прыжок ~4.77 символа.
Финал
Собственно мысль, которую я хотел озвучить - ни алгоритмы, ни современность ЯП, ни ваши зазубренные знания стандартных методов напрямую не оказывают влияния на качество вашего кода. Всё зависит от того - как вы всем этим научитесь пользоваться.
Алгоритмы полезны, но вот пригодятся ли они на собеседовании, если от вас там не ждут свершений, а только лишь хотят понять - насколько хорошо вы знаете современный ЯП? Ну и при написании кода не забывайте смотреть на качество стандартной реализации, она совсем не обязательно будет удовлетворять вашим запросам.
PS: я не профессиональный программист, я не произвожу код за деньги, поэтому возможно мой подход неприменим к таким людям, но я всегда сначала пишу "наивный код", мне нужно проникнуться задачей, поймать волну так сказать. И только потом заниматься оптимизацией. Я понимаю что это неэффективно, но мне кажется тот, кто сразу напишет через Split или LINQ и будет думать, что у него всё отлично - тоже не особо эффективен. Я знаю пару человек, которые практически сразу генерируют хороший код с учётом всех нюансов и ЯП в том числе, но мне кажется это очень хороший и нечастый скилл.
Всех с наступающим Новым годом, мира и добра!
UPD: "если долго всматриваться в бездну - бездна начинает всматриваться в тебя"
В голове крутились мысли и я всё думал - нет ли чего-то еще, что могло бы повлиять на работу этого алгоритма. И такое дополнение я смог придумать, но, к сожалению, оно разочаровало меня по производительности, хотя в теории призвано уменьшить число итераций. Сейчас я уже понимаю почему эффект оказался незначительным, но для полноты картины о нём рассказать всё равно стоит.
Использую прошлую графику
Дополнение к алгоритму отслеживает ситуацию, когда мы двигаемся от Б2 к Б1 и встречаем любой символ кроме буквы (на рисунке красным оттенком). Для нас это является разрывом слова. В этот момент мы знаем, что слово (Б1, Б2) нам не подходит. А следующие итерации начнутся с символа "С".
В этот момент мы можем достоверно сказать, что символы в ячейках "C", "B", "A" и Б2 на сто процентов являются буквами, а значит при следующем прыжке нам не нужно обратный отсчёт вести до символа "C", мы уже сможем прерваться на символе Б2.
Но бенчмарк и последующие исследования показали, что такие ситуации очень редки и на скорость выполнения или почти не оказывают влияния или даже замедляют работу, скорее всего из-за дополнительных арифметических операций, к стандартному коду добавились еще три операции. Из 199817 итераций на тестовом файле мы сэкономили только 33 итерации, то есть 0.0165%. Таким образом число итераций не снижается настолько чтобы компенсировать возросшее число вычислений. Но сама идея мне понравилась.
// JumpNew
// переменная tail сохраняет тот "хвост",
// который нужно учесть при следующей проверке
int maxlen = 1, maxindex = -1, tail = 0;
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 + tail) && char.IsAsciiLetter(str[i]));
// она же переходит ниже
if (i == (index + tail))
{
// тот пришлось изменить точку входа с учётом "хвоста"
// чтобы понять почему именно так, нужно отправной точкой брать
// (index + maxlen + 1), на рисунке это точка за Б2. И тогда
// можно написать i = index + maxlen + 1 и это тоже будет правильно.
// я же, посмотрел что в этом месте i == (index + tail) и решил вычислить
// значение, на которое i можно увеличить, то есть
// нужно убрать tail и прибавить maxlen + 1
for (i += maxlen - tail + 1; i < str.Length && char.IsAsciiLetter(str[i]); i++) ;
if (maxlen < (i - index))
{
maxindex = index;
maxlen = i - index;
}
tail = 0; // обнуляем "хвост"
continue;
}
else
{
// считаем "хвост"
tail = index + maxlen - i - 1;
i++;
continue;
}
}
else
{
tail = 0; // обнуляем "хвост"
continue;
}
}
tail = 0; // обнуляем "хвост"
i++;
}| Method | Length | Mean |
|---------|--------|-------------|
| Jump | 1 | 107.5 ns |
| JumpNew | 1 | 105.2 ns |
|---------|--------|-------------|
| Jump | 100 | 6,615.6 ns |
| JumpNew | 100 | 7,168.1 ns |
|---------|--------|-------------|
| Jump | 1000 | 65,292.7 ns |
| JumpNew | 1000 | 71,391.4 ns |UPD2: отпусти меня травааааааа... (с) народное
Продолжая - нашёл ошибку в реализации Jump и JumpNew, а так же немного переделал код, стало почище и попроще.
// Jump
int maxlen = 0, maxindex = -1, len = str.Length;
for (int i = 0; i < len - maxlen; i++)
{
if (char.IsAsciiLetter(str[i]))
{
int index = i;
i += maxlen;
if (i < len && char.IsAsciiLetter(str[i]))
{
for (; i > index && char.IsAsciiLetter(str[i]); i--) ;
if (i == index)
{
for (i += maxlen + 1; i < len && char.IsAsciiLetter(str[i]); i++) ;
if (maxlen < (i - index))
{
maxindex = index;
maxlen = i - index;
}
}
}
}
}// JumoNew
int maxlen = 0, maxindex = -1, tail = 0, len = str.Length;
for (int i = 0; i < str.Length - maxlen; i++)
{
if (char.IsAsciiLetter(str[i]))
{
int index = i;
i += maxlen;
if (i < len && char.IsAsciiLetter(str[i]))
{
for (; i > (index + tail) && char.IsAsciiLetter(str[i]); i--) ;
if (i == (index + tail))
{
for (i = index + maxlen + 1; i < len && char.IsAsciiLetter(str[i]); i++) ;
if (maxlen < (i - index))
{
maxindex = index;
maxlen = i - index;
}
}
else
{
tail = index + maxlen - i - 1;
continue;
}
}
}
tail = 0;
}
Собственно изменения:
вынес
i++в основной циклfor, связано это с тем, что все условияifтак или иначе позволяют продолжить со следующего шага, ранее у меня там было недопонимание с тем в каком случае можно сделать шаг, а в каком нет. Найдя ошибку стал пошагово проверять все состояния и понял, что можно исключить лишние шаги с проверкойif, это позволило уменьшить общее число итераций;Переделывая
SkipWordкод вJumpоставил циклdo-while, но тамiработает в обратном порядке, переделал наforи изменил переменнуюmaxlenна0. Это создавало ситуацию когда строка с минимальным одним словом в 1 букву приводила бы к состоянию - "в этой строке нет слов".
| Method | Length | Mean |
|----------------|--------|---------------|
| Jump | 1 | 65.07 ns |
| JumpNew | 1 | 71.61 ns |
|----------------|--------|---------------|
| JumpNew | 100 | 3,391.07 ns |
| Jump | 100 | 3,435.72 ns |
|----------------|--------|---------------|
| Jump | 1000 | 32,434.37 ns |
| JumpNew | 1000 | 35,162.05 ns |UPD3 новогодний:
Много тестируя и всё ещё думая об вариантах улучшения я изменил код ещё раз, причём мне удалось найти стабильное решение, которое для первого апдейта иногда даёт лучший результат чем "классический" вариант с прыжками из статьи или держится к нему достаточно близко.
Интересно, что основное влияние оказал не сам алгоритм, а реализация do-while вместо for. Причём разница в производительности в 10-20%, что для меня, как редко пользующегося C# - выглядит странным.
Основное изменение касается того, что я убрал первый if, который логически конечно был на своем месте, но в реализации дублировался следующим if.
Возможно вы заметите странную запись i -= maxlen > 0 ? 1 : 0; - это результат моей борьбы с разной производительностью for и do-while, в итоге такая конструкция вместе с do-while всё равно оказывается быстрее for.
UPD4: исправления/изменения
Изменил код с учётом "упрощений" предложенных в своей реализации пользователем ARad. Реализации всё равно различаются, в том числе по производительности, версия ARad работает быстрее.
// Jump
int maxlen = 0, maxindex = -1, len = str.Length;
for (int i = 0; i < len - maxlen; i += maxlen + 1)
{
if (!char.IsAsciiLetter(str[i])) continue;
int index = i - maxlen;
int k = maxlen > 0 ? 1 : 0;
do
{
i -= k;
if (!char.IsAsciiLetter(str[i])) goto Continue;
}
while (i > index);
i += maxlen;
do i++;
while (char.IsAsciiLetter(str[i]) && i < len);
maxindex = index;
maxlen = i - index;
Continue:
;
}// JumpNew
int maxlen = 0, maxindex = -1, tail = 0, len = str.Length;
for (int i = 0; i < len - maxlen; i += maxlen + 1)
{
if (!char.IsAsciiLetter(str[i]))
{
tail = 0;
continue;
}
int index = i - maxlen;
int k = maxlen > 0 ? 1 : 0;
do
{
i -= k;
if (!char.IsAsciiLetter(str[i]))
{
tail = index + maxlen - i - 1;
goto Continue;
}
}
while (i > (index + tail));
i = index + maxlen;
do i++;
while (char.IsAsciiLetter(str[i]) && i < len);
if (maxlen < (i - index))
{
maxindex = index;
maxlen = i - index;
}
tail = 0;
Continue:
;
}
