За последний год было достаточно статей, как с высокой оценкой необходимости знания алгоритмов, так и умеренных и радикальных. Я скорее отношусь к умеренным, но всё же считаю, что всегда важен сам контекст задачи.

В любом случае в этой небольшой статье я затрону весьма простую задачу - поиск самого длинного слова в строке.

Сразу покажу код на питоне, актуальный для многих языков высокого уровня (со страниц 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 |