Не так давно прочитал статью "В поисках алгоритмического дзена", где автор обсуждает подходы к использованию алгоритмов в рабочих задачах. В статье подчеркивается, что даже наивная реализация конкретного алгоритма будет быстрее готовых средств/реализаций, существующих в платформе, и уж тем более будет быстрее специальный алгоритм для данного конкретного случая. Возникает ощущение, что использование самописных алгоритмов обладает абсолютным преимуществом над использованием готовых реализаций. С этой точкой зрения я не могу согласиться.
Стоит ли использовать специальные алгоритмы?
На этот вопрос нельзя дать однозначный ответ. Всё зависит от контекста, в котором будет работать алгоритм.
Если у нас хайлоад и метод находится в горячей секции, там самописные алгоритмы могут быть очень полезны, и использование более сложного в поддержке кода вполне оправдано.
В других случаях, я бы не стал торопиться добавлять алгоритмы, во всяком случае до проведения нагрузочных тестов, просмотра метрик системы и прочего.
В этой статье я постараюсь показать почему использование самописного алгоритма не всегда оправдано, даже если он работает значительно быстрее. А также предложу некоторый компромиссный вариант оптимизации.
Постановка задачи
Если речь идет не об олимпиадном программировании, а о реальной задаче, то всегда важно понимать, что именно мы делаем, в каких условиях, и, главное, для чего будет использоваться наш код.
Давайте рассмотрим такую задачу:
Допустим, у нас есть сайт, на котором разные авторы публикуют свои статьи оригинальная идея, все совпадения случайны. После публикации мы показываем некоторую статистику по этой статье.
И, собственно, наша сегодняшняя задача - добавить самое длинное слово из статьи в статистику. Для чего? Чтобы мериться длиной слов, конечно!
Реализация
Автор оригинальной статьи предлагает такой алгоритм. Его я и буду рассматривать (далее в тексте называю его просто 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 раз быстрее. Эта разница может быть совершенно не заметна в метриках целой системы. Её съедят сетевые задержки, обращения к БД и куча всего прочего, что у нас есть в реальном продукте. А вот стоимость поддержки такой системы возрастает значительно.
Комментарии (81)
Zara6502
10.01.2024 08:51+1Спасибо за статью и приятно что моя статья получила отклик.
Если позволите, то дам комментарии.
1) Вы неверно протрактовали смысл моей статьи. Ваша статья как раз является полным подтверждением моей и высказанных там тезисов, что легко подтвердить:
мои слова "всё же считаю, что всегда важен сам контекст задачи" и ваши "Всё зависит от контекста, в котором будет работать алгоритм", то есть в основной части смысла мы сходимся.
Так же, я объясняю, почему кастомная реализация может быть неприменима "многие простейшие задачи оборачивают в готовые методы актуального ЯП, что в первую очередь решает основную задачу бизнеса - быструю разработку", что соответствует тезису из вашей статьи "В первую очередь, я пишу код для людей. Он должен легко читаться, поддерживаться и меняться по мере необходимости".
То есть и в введении и в заключении мы оба говорим абсолютно одинаковые вещи.
2) Так как я жутко не люблю когда мне приписывают то, чего я не говорил, то отдельного комментирования требуют следующие ваши слова,
Не так давно прочитал статью "В поисках алгоритмического дзена", где автор обсуждает подходы к использованию алгоритмов в рабочих задачах
Я в своей статье не обсуждал подходы к использованию алгоритмов в рабочих задачах. Я чётко обозначил проблему использования стандартных методов при решении задач на собеседованиях и при выдаче результатов на сервисах вроде StackOverflow. Это раз. И два - я однозначно пишу в финале статьи что
ни алгоритмы, ни современность ЯП, ни ваши зазубренные знания стандартных методов напрямую не оказывают влияния на качество вашего кода. Всё зависит от того - как вы всем этим научитесь пользоваться.
Что полностью соответствует финалу вашей статьи
Современные языки/платформы предоставляют кучу готовых алгоритмов, структур данных, которые могут сильно улучшить производительность без необходимости писать сложный код. Самое главное - их правильное использование.
3)
В статье подчеркивается, что даже наивная реализация конкретного алгоритма будет быстрее готовых средств/реализаций, существующих в платформе
Ну этому есть подтверждающие факты.
и уж тем более будет быстрее специальный алгоритм для данного конкретного случая
и это тоже факт.
Возникает ощущение, что использование самописных алгоритмов обладает абсолютным преимуществом над использованием готовых реализаций
Только у малопосвященных в тему.
Например я еще с 80-х, используя стандартные библиотеки часто говорил, что "пишут их люди поумнее нас", на вопросы от тех, кто вместо std норовил написать что-то своё. Тут мы возвращаемся к началу - важен контекст.
4)
В этой статье я постараюсь показать почему использование самописного алгоритма не всегда оправдано, даже если он работает значительно быстрее
Стандартные методы сами по себе являются специальными реализациями определенных алгоритмов, просто их делают универсальными, а не привязанными к char, byte или int, а так же оформляют соответствующим образом - чтобы ЛЮДИ могли легко читать написанное. В этом смысл. И вы не спешите их переписывать и вас не волнует насколько красиво они написаны внутри. Ну во всяком случае это точно не будет волновать 99% тех кто ими будет пользоваться (я частенько залезаю внутрь чтобы посмотреть как именно происходит какая-то проверка, хотя бы тот же
IsAsciiLetter()).То есть любой специальный метод легко можно сделать "стандартным", разместить в Nuget и ставить для своего проекта. Не вижу почему моя реализация Jump хуже того-же TimSort или RuNS, которые мало кто даже написать своими силами сможет, не то что исправить (вы же в курсе что TimSort входил в состав Java/Python >10 лет имея на борту ошибку?).
---
В заключении - вы написали хорошую статью в качестве продолжения затронутой мной проблематики, но неверно расставили акценты. Статье я поставил плюс, а вам поднял карму, так как на мой взгляд проблематика первичнее, нежели моё отношение к недоработкам статьи.
Тем более я не отношусь к профессиональному сообществу программистов, хотя образование и позволяет, и наверное могу в чём-то ошибаться, хотя в рамках этих статей считаю что мы оба говорим об одном и том же.
Zara6502
10.01.2024 08:51Дополню - можно Jump реализовать как класс с методами для <T>, <object>, ну и в целом расширить задачу как - поиск однотипного максимума последовательности, добавить возможность использования своей реализации компаратора. В общем в по уму, по ООПэшному. Завернуть в пакет, разместить в Nuget и github и отдать сообществу в пользование. Не вижу причин в таком виде игнорировать его в проде для любой софтверной компании.
То есть это не задача поиска экстремума, а поиск максимальной длительности сигнала.
Кстати никто не мешает для стандартных типов написать реализации с применением каких-то хитростей, что например для char даст сопоставимую производительность, которая показана в наших статьях, а для <object> вероятно как-то более универсально реализовать.
zolroman Автор
10.01.2024 08:51Спасибо за отзыв, и за плюсы!
Если я не так понял ваш посыл, и, на самом деле, мы сходимся во мнении, то это замечательно! И я прошу прощения если где-то неправильно передал ваши слова.
Я написал эту статью, потому что хочу явно прояснить некоторые моменты, для себя, и для тех, кто, возможно, так же, как и я понял вашу статью, и для тех кто может воспринять её как руководство к действию.
вы пишите: "Всё зависит от контекста, в котором будет работать алгоритм", но не даёте тот самый контекст для задачи. И, по умолчанию, я воспринял это в контексте бизнес задачи.
Я чётко обозначил проблему использования стандартных методов при решении задач на собеседованиях и при выдаче результатов на сервисах вроде StackOverflow.
Я не увидел в статье упоминания того, что это задача для собеседований.
ни алгоритмы, ни современность ЯП, ни ваши зазубренные знания стандартных методов напрямую не оказывают влияния на качество вашего кода. Всё зависит от того - как вы всем этим научитесь пользоваться.
Со вторым предложением я полностью согласен, без умения пользоваться никакой ЯП не поможет. А вот с первой частью - совсем нет!
Что полностью соответствует финалу вашей статьи
Совсем нет, я пытался высказать противоположное мнение! Именно современные ЯП и знание стандартных методов могут сильно улучшить качество кода. А вот использование алгоритмов может сделать код сложнее в поддержке.
Возникает ощущение, что использование самописных алгоритмов обладает абсолютным преимуществом над использованием готовых реализаций
Только у малопосвященных в тему.
Это отлично что вы понимаете, когда стоит использовать свой алгоритм, а когда стандартный. Но лично мне это не было очевидно из вашей статьи. И, возможно, у кого-то еще возникло подобное ощущение, и я постарался предостеречь людей, чуть меньше посвященных в тему.
Стандартные методы сами по себе являются специальными реализациями определенных алгоритмов
Ну с этим трудно спорить)
Если вам показалось, что я во всех случаях отговариваю пользоваться самописными алгоритмами из-за их сложности, то это не так. При написании библиотек/фреймворков они могут быть очень полезны и востребованы, я рассматривал контекст именно бизнес задач.
Если сократить мою статью до одного предложения:
Не нужно использовать специальные алгоритмы, пока вы можете решить вашу задачу стандартными средствами языка/фреймворка.
Zara6502
10.01.2024 08:51Не нужно использовать специальные алгоритмы, пока вы можете решить вашу задачу стандартными средствами языка/фреймворка
Полностью я такую точку зрения не разделяю. Скорее я придерживаюсь подхода (в опросе упомянул о нем), что нужно БЫСТРО написать наивно и стандартно, а потом, как от точки старта плясать в сторону улучшения. Тут есть один момент, мы подразумеваем что сама архитектура решения уже спроектирована оптимально (или близко к оптимальному), то есть вопрос только в реализации. При "кривой" архитектуре не важно вообще что и как вы напишете, так как переписывать придутся всё и много раз.
zolroman Автор
10.01.2024 08:51Переписывать придётся много раз, потому что требования будут меняться много раз.
И вопрос только в том, на сколько легко вы сможете адаптировать свой код под новые требования.
Zara6502
10.01.2024 08:51Ну а какая разница между TimSort и Jump? Я разницу не вижу. Это такой же придуманный алгоритм как и все. Сделайте класс универсальный, не вижу никакой проблемы. Если ваша задача уйдет за рамки использования TimSort вам точно так же придется менять код под другой алгоритм.
zolroman Автор
10.01.2024 08:51+1Я никогда не сравнивал TimSort и Jump.
Разница между Jump и связкой Split().MaxBy() в том, что метод Jump вам придется написать, протестировать, поддерживать, а Split и MaxBy уже есть в системе.
Для Jump тоже есть своя ниша, он не бесполезен. Но, затраты на его написание и поддержку должны быть оправданы, только и всего.
Zara6502
10.01.2024 08:51Сравниваю я, так как TimSort появился как "поделка на коленке", оброс, возмужал и был встроен в библиотеки (при этом оставался забагован). Так почему вы запрещаете такому (не багам конечно) происходить с другими алгоритмами? Но всегда есть какое-то начало. Какая-то контора применит у себя, будет тяжелый к сопровождению код, потом кто-то напишет реализацию удобную в работе (если вы про ООП, так как я и сейчас не вижу проблем с её использованием).
Какая разница напишете вы Split или Jump? Split в NET 1 вообще был?
zolroman Автор
10.01.2024 08:51Запрещаю? Ни в коем случае!
Если вы оформите свой алгоритм в виде библиотеки, это будет отличным решением. Буду ли я ей пользоваться - вопрос. Выбор опенсурсной библиотеки это тема на отдельную статью.
У меня есть вопросы только в том случае, если вы пишите подобный код как решение конкретной бизнес задачи.
zolroman Автор
10.01.2024 08:51Split в NET 1 вообще был?
Важно что он есть сейчас, и сейчас мы можем его использовать
Zara6502
10.01.2024 08:51Ну то есть вопрос не в самописных методах, а в том как они оформлены?
zolroman Автор
10.01.2024 08:51Вопрос в том, какую задачу вы решаете этим кодом.
Zara6502
10.01.2024 08:51Это понятно, просто раз вы статью пишете в противовес моей, то вас не устроили мои тезисы. Я и пытаюсь найти что же не так. Пока вы всё пишете - похоже на то, что писал я, не в деталях конечно. Почему? Потому что я в статье написал например такое:
1) многие простейшие задачи оборачивают в готовые методы актуального ЯП, что в первую очередь решает основную задачу бизнеса - быструю разработку
2) я всегда сначала пишу "наивный код", мне нужно проникнуться задачей, поймать волну так сказать. И только потом заниматься оптимизацией
3) мне кажется тот, кто сразу напишет через Split или LINQ и будет думать, что у него всё отлично - не особо эффективен
И я в статье не трогал задачи бизнеса совсем, а вы, как я понимаю, как раз и говорите о том, что важнее для бизнеса, то есть в этом аспекте статьи даже не пересекаются.
Может из статьи не понятно, но основные штрихи там о том, что много говорят про алгоритмы, а на деле их не применяют, это раз. Когда применяют, то делают это бездумно. И меня в первую очередь занимает контекст того как это подано в общедоступном интернете, для новичков в том числе. Тот же SO не научит вас выбирать, потому что на SO не обсуждаются задачи, там обсуждаются реализации, а без контекста, как мы уже выяснили любой способ - это пальцем в небо. SO не бесполезен, просто он не решает этой проблемы (вероятно никогда и не пытался).
SpiderEkb
10.01.2024 08:51+2что в первую очередь решает основную задачу бизнеса - быструю разработку
Быстрая разработка не всегда есть основная задача бизнеса.
Строго говоря, основная задача любого бизнеса есть получение прибыли. А разработка есть способ автоматизации бизнес-процессов для увеличения прибыли (напрямую, за счет снижения накладных расходов и т.п.).
Но у любого бизнеса есть приоритеты. Есть бизнес, основанный на скорейшем выводе на рынок некоего продукта. Пусть кривого-косого, но вперед всех (сейчас и так сойдет, потом поправим). Тут да. Скорость разработки.
Но есть бизнес, где требуется предоставить качественный продукт. Или бизнес, где некачественная автоматизация процессов приведет к убыткам (репутационные, штрафы регулятора и т.п.). И здесь уже главное не скорость разработки, а качество кода. Другие приоритеты, другие требования.
В остальном с Вашими тезисами в целом согласен.
CorwinH
10.01.2024 08:51Быстрая разработка не всегда есть основная задача бизнеса.
Тут во многом зависит от цены ошибки и стоимости доставки. Команда, которая пишет софт для стиральной машины, вряд ли будет применять agile.
По моему опыту, в Альфа-банке такие ТЗ пишут, что во время разработки ни одного вопроса не возникает. Больше нигде не видел настолько проработанных ТЗ.
SpiderEkb
10.01.2024 08:51+1По моему опыту, в Альфа-банке такие ТЗ пишут, что во время разработки ни одного вопроса не возникает. Больше нигде не видел настолько проработанных ТЗ.
Потому что ТЗ является еще и документацией по задаче. Если что-то приходит на доработку, всегда логику можно по ТЗ понять.
Больше скажу - часто ТЗ потом еще корректируется по написанному коду для полного соответствия.
vkni
10.01.2024 08:51Переписывать придётся много раз, потому что требования будут меняться много раз.
Ну, казалось бы, если мы начинаем с начала, то есть со сборки требований, то мы можем примерно понять, в каком диапазоне они меняются. Таким образом, предусмотреть архитектуру так, чтобы переписывать пришлось минимальное кол-во раз.
CorwinH
10.01.2024 08:51+1Крупные проекты живут десятилетиями. В таких случаях изменение требований предсказать, практически, невозможно. Преждевременное абстрагирование в ООП так же вредно, как и преждевременная оптимизация. Годами поддерживать ненужный (неиспользуемый) уровень абстракции - довольно дорого. ИМХО дешевле будет отрефакторить, когда (если) он понадобится.
zolroman Автор
10.01.2024 08:51В статье как раз есть пример подобных изменений: сначала нам было нужно только 1 слово, а потом список самых длинных.
Если предусмотреть заранее такое изменение, и писать сразу под список, то придётся писать гораздо более сложный алгоритм, и работать он будет медленнее чем для одного слова. И ещё не факт что в дальнейшем нам вообще он потребуется.
Хороший ли это подход? На мой взгляд - нет. Я лучше напишу код который решает текущую задачу, но напишу его так, чтобы в дальнейшим было легко его править.
Не хочу быть неправильно понятным, так что сразу оговорюсь : это не значит что я считаю что не надо заранее выяснять требования, продумывать архитектуру. Архитектура важна, и она должна предусматривать изменения.
vkni
10.01.2024 08:51Я лучше напишу код который решает текущую задачу, но напишу его так, чтобы в дальнейшим было легко его править.
Ну, вообще-то, можно сразу уточнить про список. Если заказчику непонятно, то, конечно, пишете решая текущую задачу так, чтобы легко было изменить.
zolroman Автор
10.01.2024 08:51Так в этом и вся соль, заказчик не знает что ему потребуется через неделю, месяц, год.
Потому и подход такой, аджаил)
Zara6502
10.01.2024 08:51на хабре было, если правильно помню, про один проект, который лет за 15 стал очень крупным, и когда начались проблемы кто-то пытливый докопался до сути и оказалось, что изначально (тут я просто придумываю так как не помню саму статью) код был написан под работу со строками, потом на него повесили надстройку, а чтобы не переписывать надстройка генерировала данные в строках. Спустя десятилетие огромный проект в основном занимался конвертацией данных в строки и обратно.
Так что я просто не верю что вы сразу можете написать так, что всё будет правильно и легко.
CorwinH
10.01.2024 08:51+1Так что я просто не верю что вы сразу можете написать так, что всё будет правильно и легко.
Любое усложнение кода должно быть обосновано. И "быстрее работает" - вообще не аргумент. У бизнеса не может быть требования вида "надо, чтобы в коде продукта приватная функция f работала как можно быстрее".
Zara6502
10.01.2024 08:51Тут говорят что бизнес вообще ничего не решает и ничего не знает, вот вы кодите, а у вас требования к памяти, к производительности и бизнесу вы разве будете что-то говорить? Мне кажется нужно сначала найти консенсус того какой он этот бизнес и какое его участие, а то у одного одно, у другого другое, а я за всему не угонюсь.
CorwinH
10.01.2024 08:51+1вот вы кодите, а у вас требования к памяти, к производительности и бизнесу вы разве будете что-то говорить?
Я не совсем понимаю вопрос. Если есть требования к памяти и производительности, то их нужно удовлетворить. Если исследование вопроса показало, что для этого нужно поменять Split на Jump, то это нужно сделать.И это будет уже обоснованное (требования + замеры вариантов 1 и 2) усложнение кода.
Zara6502
10.01.2024 08:51Если есть требования к памяти и производительности, то их нужно удовлетворить
Нет, все тут пишут что заказчик туп и его не нужно посвящать в детали разработки (что я считаю откровенной ерундой), вот в этой парадигме вы пишете код, при реализации вы понимаете (может еще на этапе проектирования), что будут определенные требования к тому-то и тому-то. Если ранее озвученная парадигма работает, то вы ничего бизнесу говорить не станете.
В моей парадигме заказчик определяет архитектуру, вы её разрабатываете и предлагаете, озвучивая минусы и плюсы, а заказчик идёт на выбор. Так как платить ему.
SpiderEkb
10.01.2024 08:51Нет, все тут пишут что заказчик туп и его не нужно посвящать в детали разработки (что я считаю откровенной ерундой)
Вы серьезно рассказываете заказчику что "вот тут у меня Split, а вот там Jump"? Ему это реально интересно?
Наш бизнес работает так - "у нас тут вебсервис который должен получать ответ на запрос .... - сделаете нам сервис-модуль для него". Ну не вопрос - делаем. Внутри достаточно сложный скуль с агрегатными функциями и вот этим всем. Отдаем на тест. Нам отвечают - "на реальных данных ваш сервис-модуль работает до 3-х секунд (данных достаточно много, выборка сложная), наш вебсервис через раз по таймауту отваливается, нам нужно чтобы оно гарантированно укладывалось в 200мс".
Следующий этап - сопровождение. Которое тоже может сказать - ваш модуль потребляет слишком много ресурсов процессора. В условиях пиковых нагрузок это может привести к нехорошим последствиям. Надо поправить.
При этом ни тех ни других не интересует как я это реализую внутри. Им важен правильный результат за минимальное время и с минимальными затратами ресурсов.
Zara6502
10.01.2024 08:51Вы серьезно рассказываете заказчику что "вот тут у меня Split, а вот там Jump"? Ему это реально интересно?
Нет. Я предлагаю два варианта - один с требованием к ОЗУ в размере 128 Гб, а второй к 32Гб и быстрее в работе, но в дополнительной потребности к обслуживанию кастомных сервисов (обслуживать же мне, значит это отдельный договор). Вот пусть и выбирают сами что им проще - памяти купить или сопровождать сервис.
При этом ни тех ни других не интересует как я это реализую внутри. Им важен правильный результат за минимальное время и с минимальными затратами ресурсов.
Ну судя по вашему описанию там не заказчик, а стадо дебилов. Если их не интересует как вы реализуете, то откуда требования про 200 мс? Показания не сходятся.
SpiderEkb
10.01.2024 08:51+1Ну судя по вашему описанию там не заказчик, а стадо дебилов. Если их не интересует как вы реализуете, то откуда требования про 200 мс? Показания не сходятся.
Очень интересное суждение.
Бизнес выставляет требования - данные на входе, данные на выходе, максимальный таймаут. Это все, что их интересует.
Вы когда покупаете стиральную машину - вас что интересует в первую очередь? Функционал, или то, какие микросхемы там внутри?
Нет. Я предлагаю два варианта - один с требованием к ОЗУ в размере 128 Гб, а второй к 32Гб и быстрее в работе, но в дополнительной потребности к обслуживанию кастомных сервисов (обслуживать же мне, значит это отдельный договор). Вот пусть и выбирают сами что им проще - памяти купить или сопровождать сервис.
Каких кастомных сервисов? О чем вы? Мы сейчас говорим исключительно о внутренней реализации. Split который работает медленно и требует больше памяти (зато не думая, левой ногой), или Jump, который работает быстро и требует меньше памяти (но чуть больше строк кода и нужно ум наморщить немного). Вы всерьез считаете, что вариант с Jump потребует какого-то особого обслуживания? Или что в Вашем коде реализации Jump кроме вас никто не разберется? Остальные настолько тупы? Вы пишете такой закрученный код, что кроме Вас никто его не понимает? Серьезно?
Ну и если говорить о железе, то мы работаем на
IBM Power E980
• 120 процессорных ядра Power9
• RAM - 12Тб
• LAN - 10Гигабит
• Storage - 400Тб на SSD
• Operation System: IBMi7.4Как думаете, сколько стоит нарастить его мощность раза в два?
Zara6502
10.01.2024 08:51Функционал, или то, какие микросхемы там внутри?
В первую очередь платформа, технологии, ремонтопригодность. Функциональность месте на 4-5.
Бизнес выставляет требования - данные на входе, данные на выходе, максимальный таймаут.
Ну вы это преподнесли иначе, сначала вы написали софт, а потом вам рассказали про 200 мс.
Вы всерьез считаете, что вариант с Jump потребует какого-то особого обслуживания?
Я как раз так не считаю, но достаточно тех кто так считает.
Или что в Вашем коде реализации Jump кроме вас никто не разберется? Остальные настолько тупы? Вы пишете такой закрученный код, что кроме Вас никто его не понимает? Серьезно?
Процитируйте где я такое утверждаю.
Как думаете, сколько стоит нарастить его мощность раза в два?
К чему этот вопрос вообще?
SpiderEkb
10.01.2024 08:51У бизнеса требования типа "вот этот модуль должен выдавать ответ на запрос в течении не более чем 200мс". Как вы этого добьетесь их не волнует.
Кроме бизнеса есть еще сопровождение. У которого требования по нагрузке. И которые могут выдать вам такое вот заключение:
Из PEX статистики работы PBC01U01R видно, что 33% времени и 36% ресурсов CPU тратится на выполнение QSQRPARS в программе STL#CHKN, т.е. парсинг статических выражений при подготовке SQL запроса,
Поскольку CU130 один из наиболее активно используемых сервис модулей, необоснованное повышенное ресурсопотребление является малодопустимым. Просьба инициировать доработку STL#CHKN.
Zara6502
10.01.2024 08:51Как вы этого добьетесь их не волнует
Ну раз их не волнует, а вы везде написали Split то и имеете что имеете. Вы считаете что никто не виноват? )))
CorwinH
10.01.2024 08:51При "кривой" архитектуре не важно вообще что и как вы напишете, так как переписывать придутся всё и много раз.
Чем проще код, тем проще его переписывать. Если всё равно переписывать, то имеет смысл написать как можно проще.
ARad
10.01.2024 08:51+1@Zara6502мне кажется вы не правы, в том плане что как раз в вашей статье все внимание уделено узко специализированному алгоритму. А его даже не надо было делать. Нужно было просто убрать неоптимальные моменты метода Split и всё. И это просто сделать. Т.е. нужно было сделать быстрый алгоритм ленивого перечисления слов в строке и всё. Ленивое перечисление это ключевой момент, так так позволяет избавится от большого потребления памяти. Дальше можно легко выполнять любую необходимую обработку слов. Да он будет в 2-5 раз дольше работать для частного случая, но его можно будет легко менять под большинство требований.
Zara6502
10.01.2024 08:51в моей статье есть самый первый абзац, он и определяет то, почему статья написана. то что я сделал там что-то узкоспециализированное (а позже вы предложили свой вариант) это лишь частности. основной акцент как раз на том, что упор в алгоритмы, который обсуждается во множестве статей на Хабре, на мой взгляд, не имеет смысла. и ваши выводы только это подтверждают, то есть мы едины в понимании того, что алгоритмы ради алгоритмов - это не тот путь.
но в статье есть и вторая проблема - унифицированные библиотечные реализации порой сильно далеки даже от наивной, про которые тоже много пишут на Хабре, например применительно к сортировке. Поэтому я не зря упомянул TimSort в обсуждении этой статьи, так как когда-то TimSort был "узкоспециализированным". То есть использование чего-то узкоспециализированного не является табу, важен контекст.
поэтому пардон, но я не могу быть не правым, так как и с автором этой статьи и с вами мы говорим об одном и том же, разве что разными словами. я же нигде в своей статье не пишу о том, что срочно нужно запретить Split и начать пользоваться Jump, мысль моя описана в финале - нужно с умом пользоваться как ЯП так и бибилиотеками.
ARad
10.01.2024 08:51+1У вас нигде в статье не написано что НЕ надо писать реализации типа Jump вот в чем моё уточнение. Либо если вы такое написали, то очень незаметно или неявно.
Я же, как и автор второй статьи прямо говорим что надо писать простые и эффективные (пусть и не самые эффективные алгоритмы) и знание стандартной библиотеки это сильно упрощает. Стремление к максимальной эффективности частного алгоритма зло в подавляющем большинстве случаев.
Zara6502
10.01.2024 08:51У вас нигде в статье не написано что НЕ надо писать реализации типа Jump вот в чем моё уточнение. Либо если вы такое написали, то очень незаметно или неявно.
Акцент статьи строится на том, что когда мы бездумно пишем сами или требуем от других (это про вопрос образования и тестирования) использование стандартных методов, то это далеко не всегда тот результат, который действительно вам нужен. То есть это такая же крайность, как и написание собственного беспорядочного кода. Как вывод статьи - нужно уметь писать думая головой.
Мне кажется этот смысл сам говорит о том, что "не нужно писать Jump ради Jump'а", так как важен контекст задачи. Для ботлнека на высоконагруженном сервере это одно, для фронта который рисует одну кнопку - это другое.
Я же, как и автор второй статьи прямо говорим что надо писать простые и эффективные (пусть и не самые эффективные алгоритмы) и знание стандартной библиотеки это сильно упрощает.
Да, но это плохо коррелирует с контекстом задачи, иначе вы просто можете оказаться в условиях, когда сначала ляжет ваш сервис, будут у бизнеса убытки, а только потом вы возьмётесь за оптимизации. Об этом пишут и другие, не только я. Я не считаю что упрощение ради упрощения тоже хороший путь, это такая же крайность.
Стремление к максимальной эффективности частного алгоритма зло в подавляющем большинстве случаев.
Я думаю это верно только для определенных ситуаций и проектов. Вы ведь согласитесь, что например геймдев в таких вопросах будет сильно отличаться от вэб-сервера с лендингом, ну а само существование гугла прямо утверждает, что переписывать нужно всё подряд, так как требования и условия эксплуатации сильно отличаются от среднестатистических.
SpiderEkb
10.01.2024 08:51+2То есть это такая же крайность, как и написание собственного беспорядочного кода.
А можно пояснить - почему вы считает что библиотечный код есть абсолютное добро, а собственный - абсолютное зло.
Вы считаете, что сами не способны реализовать что-то эффективное? Вы всерьез считаете, что простой линейный алгоритм с минимумом ветвлений, занимающий 10-20 строк кода (и абсолютно прозрачный и понятный) будет хуже чем вызов какой-то библиотечной функции, под которой скрывается 100500 уровней абстракций и столько же уровней стека (а когда это вызывается, скажем, 20 000 000 раз это уже очень ощутимые накладные расходы)?
Вот откуда такая уверенность?
LaRN
10.01.2024 08:51-1Если взять например python, то в нем много чего в библиотеках написано на C, который на порядок быстрее paython. И любой ваш супер оптимальный алгоритм будет проигрывать в скорости коду на C. Да и по затратам памяти массив в numpy намного меньше чем аналогичный paython - ский список. Поэтому для прикладной разработки использовать библиотеки это наверное более оптимально, чем самому изобретать. А вот для системной разработки наверное уже может иметь смысл что-то придумывать.
ARad
10.01.2024 08:51Давайте посчитаем насколько Jump может быть быстрее. Средняя длина слова я думаю 5-7 букв от языка зависит, на английском думаю в районе 5, значит в 5 раз в теории.
В реальности последовательный перебор имет несколько меньше затрат, поэтому процентов на 20% быстрее остаётся примерно в 4-5 раз на практике.
И это только если требования не изменятся, как только они усложнятся будет ещё меньше разница.
Если вы хотите быстро, то такие расчёты выполняются раз и результат сохраняют. Вся работа по чтению и сохранению данных намного дольше чем сам алгоритм, итоговая разница десятки процентов максимум. Ну и зачем тогда, если на бизнес это не повлияет.
То что есть критические места для бизнеса я не спорю. Архитектура системы намного более тут критична чем супер оптимизация конкретного алгоритма, если она всего в 4-5 раз лучше, но с накладными расходами максимум 10-20%. А может и вообще меньше процента вносить в итоговый результат.SpiderEkb
10.01.2024 08:51Если вы хотите быстро, то такие расчёты выполняются раз и результат сохраняют
А теперь представьте, что это не один раз. А 10 000 000 раз. Т.е. задача, например, в том, что вам на вход дается 10млн строк и для каждой надо выбрать самое длинное слово.
Ну и зачем тогда, если на бизнес это не повлияет
Откуда такая уверенность? Вот предположим, что у вас на сервере одновременно работает десятки тысяч процессов. А ваш процесс всего лишь звено в длинной цепочке - его результат нужен другому процессу.
И если все они реализованы исходя из таких вот соображений, то все это будет работать очень медленно. А в случае увеличения нагрузки может вообще встать колом. А через год количество данных увеличится и оно потребует тотальной оптимизации всего и вся.
И все потому что вам просто лень лишний раз подумать "а как это можно реализовать быстрее и эффективнее".
ARad
10.01.2024 08:51Если вы будете в реальности то большие данные не из воздуха берутся, и там уже будет буферное чтение и чтение по словам по токенам и голого чтения по памяти у вас просто не будет... И следовательно вы и не сможете этот алгоритм применить.
SpiderEkb
10.01.2024 08:51Нет. Это может быть 10...50млн записей из БД которые требуют обработки. В том числе (среди всего прочего) - выбор самого длинного слова по одному из полей. Вполне реальный сценарий. Результаты обработки каждой записи потом уходят куда-то дальше.
Тормозит ваша задача - тормозит вся цепочка куда она встроена. А поскольку кроме вашей задачи еще параллельно крутится несколько десятков тысяч других - больше ресурсов процессора вы на себя возьмете - меньше останется другим. И там тоже могут начаться тормоза. А если все это случится в периоды пиковых нагрузок, то есть риск вообще весь сервер затормозить так, что все это скажется в масштабах миллионов клиентов по всей стране. Прецеденты были.
А дальше - комиссия по инцидентам и разборки - кто писал код, кто делал ревью, кто тестировал, кто согласовывал внедрение...
Посему, любой код должен быть максимально быстрым и эффективным. Иначе никак. Не умеешь - ищи где попроще и требования пониже.
ARad
10.01.2024 08:51Чтение из БД настолько медленнее чем обработка строк в памяти что тут вообще нет смысла обсуждать. Я хоть за нулевое время буду делать обработку строк, в итоге это уменьшит общие затраты на пару процентов максимум.
Это может быть важно в каких то сетевых протоколах, да там есть много мест для тонкой оптимизации. Там её и пременяют, тут я спорить не буду.SpiderEkb
10.01.2024 08:51+2Вообще-то нет. Личный опыт.
Вообще, разговоры о том, что современный софт становится медленнее и требует больше ресурсов уже стали общим местом. И одна из причин как раз в том, что разработчикам лень лишний раз "включить мозг" и они предпочитают использовать готовые библиотеки, рассчитанные "на все случаи жизни", но не оптимальные под данную конкретную задачу. К тому же несущие большое количество накладных расходов вследствие большого количества уровней абстракции.
ARad
10.01.2024 08:51Я ваши желания понимаю, но вы попробуйте у себя на работе им последовать, мне будет интересно насколько быстро вас выставят на мороз или насколько быстро ваш продукт обойдут конкуренты. Для меня критерием является выбор покупателей, и конкуренция на рынке, за что покупатели платят деньги, а не о чем они просто мечтают и рассуждают, при этом многие их них не написали ни строчки кода.
Zara6502
10.01.2024 08:51Я понимаю что с ARad у нас не 100%-е общее представление в этом вопросе, но всё же я считаю что упираться рогом в оптимизации и производительность нельзя. Потому что есть классическое деление задачи 20/80, где 20% усилий дают 80% результата. Любое последующее усилие влияет на результат всё меньше и меньше. Поэтому написание быстрого и эффективного кода может просто быть экономически невыгодным. Иногда будет проще увеличить производительность аппаратной части, это ведь тоже вариант решения и бизнес смотрит на цифры, а не на абстрактное заявление "код должен быть ...". Вы же должны понимать что решение о внедрении кода принимают не программисты?
SpiderEkb
10.01.2024 08:51Иногда будет проще увеличить производительность аппаратной части
Вы готовы оплатить увеличение производительности аппаратной части из своего кармана, или предпочтете подумать и решить задачу так, чтобы оно работало на имеющемся железе?
Иными словами, вы предпочитаете делать как вам проще, и при этом "выставить" заказчика на закупку нового железа?
Наращивание производительности железа - те же самые 20/80. Чем дальше, тем дороже. А в современных условиях еще не любое железо здесь просто так доступно.
Zara6502
10.01.2024 08:51Вы готовы оплатить увеличение производительности аппаратной части из своего кармана, или предпочтете подумать и решить задачу так, чтобы оно работало на имеющемся железе?
Этот выбор делает заказчик а не я. А вот выбор предоставлю я. Моя задача реализация, а не размышления на тему вселенского блага.
Иными словами, вы предпочитаете делать как вам проще, и при этом "выставить" заказчика на закупку нового железа?
Вы читаете по диагонали.
Наращивание производительности железа - те же самые 20/80
Само собой, только если вы рогом упёрлись в софт забыв про железо, то и эффективного решения ваши заказчики не дождутся.
SpiderEkb
10.01.2024 08:51Само собой, только если вы рогом упёрлись в софт забыв про железо, то и эффективного решения ваши заказчики не дождутся.
За железо отвечаю не я. Я отвечают за максимально эффективное решение по софту. И мне не лень это решение найти.
Простой пример. Есть некая подсистема, которая разрабатывалась давно. На момент разработки скорость ее работы всех устраивала (и многое там писало именно "как проще", плюс возможности инструментария тогда были более ограничены). С тех пор объем данных увеличился в несколько раз (только по количеству клиентов более чем в два раза). И время работы подсистемы начало выходить за рамки отведенного для нее временного окна. Что делать? Покупать новый сервер помощнее? Я уже привел с чем мы работаем - стоимость нового железа сотни тысяч. Не рублей. Плюс время на закупку, доставку, развертывание и т.п. Все это может занять полгода.
Я за две недели провел рефакторинг подсистемы, ускорив ее в среднем в 4-5 раз (там много чего было, в т.ч. пара сопутствующих задачек, которые на много чего еще положительно повлияли за пределами данной подсистемы). За зарплату которую мне тут платят. Что стоит минимум на порядок дешевле нового сервера и существенно быстрее по времени.
По теперешним нормам такие решения, как были там, просто не пройдут ни кодревью, ни нагрузочное тестирование - требования по эффективности сейчас намного жестче. Именно ради того, чтобы реже тратить время и деньги на замену железа (да, периодически это приходится делать, но тут чем реже, тем лучше).
Zara6502
10.01.2024 08:51не влезая в разговор, просто о цифрах когда тестировал: обратный цикл, где
i--имело среднее значение в 3 и практически не определялось размерами текущего максимального слова, а средний прыжок сильно зависел от того, насколько близко к началу находится какое-то большое слово. Например для одной из книжек Жюля Верна среднее значение было 12.ARad
10.01.2024 08:51Соглашусь с вами, я неверно посчитал... Надо же брать не среднюю длину слова, а длину максимального (длина прыжка), тогда да раз в 10-15 и более вполне возможна разница. Что-то я поспешил с расчётами.
SpiderEkb
10.01.2024 08:51+2есть реальная потребность в оптимизации, вот тогда настает время алгоритмов!
Как вы узнаете что "есть реальная потребность в оптимизации"? Когда на проде в период пиковой нагрузки все встает колом?
Не устану приводить пример когда в одном из банков в период пиковой нагрузки (предновогодний период когда толпы людей ломятся в магазины за покупками) такая ситуация привела к тому, что в течении нескольких часов по всей стране у миллионов клиентов были проблемы при оплате картами в магазинах.
Вам такая ситуация нужна чтобы понять необходимость оптимизации?
zolroman Автор
10.01.2024 08:51По-хорошему, проводят нагрузочное тестирование, находят узкие места и оптимизируют именно их.
Использование более быстрого алгоритма в 1 месте не гарантирует что система начнёт работать быстрее.
SpiderEkb
10.01.2024 08:51+1У нас все поставки проходят через нагрузочное тестирование на копии промсреды. Но оно не дает ответа на вопрос - "что будет в условиях пиковых нагрузок". И "что будет через год когда количество обрабатываемых данных возрастет на 25%".
НТ может вам показать лишние вызовы, лишнюю динамическую работу с памятью, лишние переоткрытия файлов и т.п. Но это не серебряная пуля.
Задача разработчика писать не как ему проще (о чем многие забывают), но максимально эффективно в заданные сроки. И если вы видите, что можно реализовать алгоритм, который с учетом конкретики задачи будет работать быстрее "среднеуниверсальных" - вы просто обязаны это сделать. При том, что он скорее всего будет еще и проще (т.к. там решается одна конкретная задача с конкретными граничными условиями, а не попытка реализовать нечто на все случаи жизни).
zolroman Автор
10.01.2024 08:51вы просто обязаны это сделать
Вот тут я с вами не согласен.
Если ваш "хороший" алгоритм быстрый, простой в поддержке, в него легко вносить изменения, и стоимость его разработки аналогичная, то - да, его стоит реализовать.
Например, я не вижу ни одной причины не использовать Memory.Split вместо string.Split в данном случае, это необходимая оптимизация.
Но в других ситуациях это не всегда так очевидно, что я и попытался показать в статье: Jump быстрый, но вносить изменения в него в разы дольше.
И стоит делать осознанный выбор между стоимостью разработки и скоростью работы алгоритма для каждой конкретной ситуации.
SpiderEkb
10.01.2024 08:51Если ваш "хороший" алгоритм быстрый, простой в поддержке, в него легко вносить изменения, и стоимость его разработки аналогичная, то - да, его стоит реализовать.
Ну, видимо, вам просто не приходилось работать в условиях, где скорость и эффективность (прежде всего использования CPU) всегда стоят на первом месте.
А я в таких условиях работаю уже не один десяток лет. Так что считайте это профдеформацией.
DenSigma
10.01.2024 08:51Вы сравниваете велосипед с детским кодом. Сравнение совершенно неправомерно. Здесь нет лучшего варианта. Даже обсуждать и холиварить не стоит.
Честно говоря, слабо верится, что в шарпе нет аналога StringTokenizer, как в Java, либо strTok из C. В дельфи есть токенизер, и в плюсах тоже (уже не помню).
Не может быть, чтобы в шарпе не было. Задача профессионала - не быстро слепить детский код. Не написать велосипед. А найти подходящую для решения данной задачи библиотеку.
CorwinH
10.01.2024 08:51Честно говоря, слабо верится, что в шарпе нет аналога StringTokenizer, как в Java, либо strTok из C.
Есть. Это Split, который используется в статье.Вы сравниваете велосипед с детским кодом.
Почему детский?
DenSigma
10.01.2024 08:51+1Сплит напрямую создает массив строк. Токенизер никаких массивов не создает. При каждом вызове getNextToken объекта токенизера возвращается слово-токен. Его можно сравнить со словом максимумом и заменить им максимум.
"Детский" в том смысле, что берется первый попавшийся, без учета внутренней работы библиотечной функции/класса.
"Взрослый" подход, когда выбирается необходимый класс/функция, четко понимая, какие алгоритмы они реализуют и как вообще работают.
SpiderEkb
10.01.2024 08:51Сплит напрямую создает массив строк
А теперь представим, что проанализировать нужно, например, "Войну и мир". Или "Капитал"... И долго удивляемся - "чей-то у нас не так-то???"
CorwinH
10.01.2024 08:51+1В задаче на вход поступает строка, в которой нужно найти самое длинное слово. То есть, эта строка уже в памяти. Если нужно проанализировать "Войну и мир", то мы не будем считывать в память целиком, а напишем функцию, которая принимает путь к файлу.
string GetLongestWordMemory(string fileName, char[] separators) { IEnumerable<string> getWords(string s) => s.AsMemory().SplitAny(separators); var maxWord = File.ReadLines(fileName).SelectMany(getWords).MaxBy(w => w.Length); return maxWord.ToString(); }(писал в блокноте, поэтому возможны ошибки).
zolroman Автор
10.01.2024 08:51Сплит напрямую создает массив строк
Но ведь про это написано в статье)
И там же предложен альтернативный вариант с Memory, и он не создает строки, так же, как и озвученный вами StringTokenizer.
В чем тогда отличия? Почему один детский, а второй нет?
CorwinH
10.01.2024 08:51"Детский" в том смысле, что берется первый попавшийся, без учета внутренней работы библиотечной функции/класса.
Я вот всё учёл, всё проанализировал и взял Split. Мой код (точно такой же, как у автора) не детский?
p.s. Что бы Вы взяли?
SpiderEkb
10.01.2024 08:51Скорее всего, здесь будет быстрее всего работать простой потоковый проход в цикле по символам со счетчиком. Пока не наткнулись на разделитель - увеличиваем счетчик. Наткнулись - сравниваем значение счетчика с предыдущим максимальным. Больше - нашли очередной максимум. Сбрасываем счетчик и идем дальше.
Такой, с позволения сказать, "алгоритм" не будет содержать никаких лишних вызовов (которые тоже не бесплатные - не нужно разматывать и сматывать новые уровни стека) и уложится в десяток строк кода (он еще и компилятору будет прост для оптимизации).
По крайней мере от этого можно плясать.
Zara6502
10.01.2024 08:51Рекомендую прочитать мою статью, которую автор и обсуждает, ваш способ является наивным решением и может быть улучшен.
SpiderEkb
10.01.2024 08:51Я в курсе. Специально написал "от этого можно плясать".
Но реально понять может ли он быть улучшен можно только на нагрузочном тестировании. Поскольку много с НТ имею дел, то сталкивался с ситуациями когда наивные алгоритмы с силу своей простоты и линейности (минимум переходов, минимум ветвлений) на больших объемах данных показывают лучший результат, нежели "улучшенные" (казалось бы), но менее линейные и более сложные.
В принципе, этот алгоритм еще и легко параллелизуется - разбиваем входной текст на блоки, каждый блок обрабатываем в отдельном потоке (задании), затем из полученных результатов выбираем наилучший.
zolroman Автор
10.01.2024 08:51Мы обсуждаем с вами две разные проблемы:
Вы рассказываете о том, что этот код можно ускорить (с чем я абсолютно согласен)
Я же пытаюсь рассказать про реализацию бизнес-задач, где, зачастую, стоимость поддержки кода гораздо важнее скорости его работы.
Что будет с вашим супер оптимальным алгоритмом, когда изменятся требования к задаче? Вам придется его выбросить и написать новый. Новый тоже будет очень быстр, я не сомневаюсь, вот только на разработку вы потратите значительно больше времени.
И да, в каком-то случае оно будет стоить того, но далеко не всегда.
SpiderEkb
10.01.2024 08:51+1Я же пытаюсь рассказать про реализацию бизнес-задач, где, зачастую, стоимость поддержки кода гораздо важнее скорости его работы.
Точно? В наших, к примеру, бизнес-задачах на первом месте скорость, на втором эффективность использования ресурсов процессора, а потом уже все остальное.
Zara6502
10.01.2024 08:51мысль понял. но вступает в ход описанное мной же - важен контекст задачи. и моя статья как раз об этом в том числе.
SpiderEkb
10.01.2024 08:51+1Задача профессионала - решить задачу бизнеса максимально эффективно в заданные сроки. А как он это сделает заказчика не волнует вообще. Ему главное чтобы через полгода-год не пришлось искать очередного "профессионала" (который "будет искать очередную библиотеку" или просто скажет "это невозможно потому что нет нужной библиотеки") потому что увеличилось количество данных и текущее решение перестало удовлетворять по скорости работы.
Zara6502
10.01.2024 08:51А тот самый бизнес готов вам платить большие деньги чтобы вы не использовали готовые библиотеки так как есть гипотетическая вероятность каких-то там проблем в будущем? Сколько бизнесов видел я - платить много и сразу никто не собирается особенно за абстрактные ништяки в будущем. Это касается и западных компаний, благо интернет обильно пестрит такими историями.
SpiderEkb
10.01.2024 08:51Бизнесу все равно что я использую. Бизнес платить за то, чтобы все работало.
Реальный факап: предновогодняя суета, все ломятся по магазинам. Нагрузка на сервера доходит до 90% (при штатной 50-60%). И тут некий модуль начинает жрать ресурсы как не в себя, тормозить сам и тормозить остальные процессы. В результате по всей стране миллионы клиентов в течении пары часов (пока сопровождение в мыле откатывает кривые патчи и налаживает WA) не может расплатиться картами банка в магазинах - "нет ответа от банка" - вылеты по таймауту.
Или вот, от сопровождения письмо:
Коллеги, сервис *** за последние 5 недель увеличил потребление процессорных ресурсов в 3 раза!!!
Он уже является 2-м по величине сервисом после *****.
В качестве альтернативы мы рассматриваем перенос запуска сервиса на резервный сервер, но там есть лаг по отставанию до 10 мин.
Заказчикам сервиса это может не понравиться :(Так вот нам платят чтобы подобных вещей не было. Потому что "тушить" их приходится в авральном порядке. Да, это мы тоже умеем, и получать такие вот письма, конечно приятно (особенно с поименным перечислением героев), но лишний раз не хочется давать повода.
Спасибо за оперативное решение вопроса с устранением проблемы в онлайн-контроле платежей, которые генерировали для банка огромные риски и спровоцировали неприятное внимание к банку со стороны ЦБ
Очень оперативно собралась команда
Нашли нестандартное, но эффективное и быстрое решение вопроса.
Каждый этап для исправления и внедрения был пройден в полном контакте с командой, что позволило оперативно закрыть возникающие вопросы.Для понимания - это очень высоконагруженный сервис (возможно, один из самых "плотных" по объему перерабатываемой за сутки информации). И там тоже была проблема с эффективностью, приводящая к задержкам прохождения платежей. А "внимание со стороны ЦБ" запросто может обернуться штрафами с очень многими нулями. Что отрицательно сказывается на прибыли (как, впрочем, и репутационные издержки) и очень нехорошо для бизнеса в целом.
У нас огромное количество "нефункциональных требований", связанных как раз с эффективностью. По широкому кругу вопросов. От работы с БД до использования тех или иных паттернов. Потому что скорость работы и эффективность использования ресурсов для нас стоит на первом месте (с большим отрывом) от всего остального. Скорость разработки вообще мало влияет - кратно больше времени уходит на всестороннее тестирование - компоненты, бизнес, нагрузка, интеграция, техтест на прелайве...
mvv-rus
10.01.2024 08:51Ваша статья вызывает у меня ряд замечаний.
По учету затрат памяти. В C# затраты памяти конвертируются, прежде всего, в затраты времени на сборку мусора. И я не увидел, что вы не только пытаетесь их учесть,. ни явным образом - я понимаю - это непросто, особенно - на коротких методах: "естественная" (по решению GC) сборка мусора начне вносить непредсказуемость, принудительная - утопит производительность в накладных расходах - ни даже хотя бы упомянуть о них: может даже, бенчмарк их учитывает как-то сам, но об . этом упомянуть надо IMHO.
По выбору алгоритма, с которым вы сравниваете. (UPD: Да, я понял, что это - из обсуждаемой статьи, но IMHO контекст обсуждения в вашей статье шире). Вы взяли какой-то сильно оптимизированный вариант, пытающийся сэкономить количество просматриваемых символов, который, будучи оптимизированным, естественно, непонятен. Если писать алгоритм по-простому, не упарываясь преждевременной оптимизацией, то решение можно написать далеко не такое длинное и запутанное, хотя с той же, линейной по числу элементов, асимптотикой и без лишних выделений памяти. Например, так:
public string GetLongestWordMemory(string s, SearchValues<char> separators) { int ipos=0,maxlen=0; string maxstr=""; do { iposprev=ipos; ipos=str.IndexOfAny(AnyOf,iposprev); curlen=(ipos>=0?ipos:str.Length)-iposprev; if(curlnen>maxlen) { maxlen=curlen; maxstr=str.Substring(iposprev,curlen); } } while(ipos++>=0); return maxstr; }Достаточно компактно, почти линейно (один очевидный цикл) и вполне понятно, где модифицировать на проверку того, является ли слово годным и на сохранение нескольких слов - там, где if стоит . И да, никаих хитрых "алгоритмов" тут тоже нет.
И последнее. Сложность читать и модифицировать код - это, вообще говоря, субъективная оценка: кого чему учили. Ибо если человека не учили специально функциональному подходу (или, хотя бы, работе с множествами, на математике), то для него элементы функционального подхода будут вызывать затруднения сами по себе. Тогда как от императивного подхода таких затруднений не будет: он - пошаговый рецепт получения результата - в обыденной жизни куда чаще встречается. И это усложнение самих элементов может запросто съесть упрощение от снижения их числа.
zolroman Автор
10.01.2024 08:51Спасибо за критику, постараюсь ответить:
Затраты времени на сборку мусора я действительно не учитывал, не уверен, что бенчмарк такое умеет, если расскажете как - буду признателен. Косвенно их можно оценить через объем выделенной памяти, он есть в колонке Allocated.
Вот метрики предложенного вами метода (я назвал его Simple)
По производительности он что-то среднее между Split и Memory, для меня он читается хуже. Вкусовщина? возможно, но как минимум строк в нем больше) И переделать в список его будет уже и не так просто, не 2 строчки дописать.
Я бы, все же, остановился на Memory.
По выбору алгоритма: если рассматривать какой-то очень простой алгоритм, на 1 цикл, то тут и говорить не о чем: написать быстро, а в случае чего и выбросить не жалко. Моя статья именно о достаточно сложных алгоритмах.
ALexKud
10.01.2024 08:51Была у меня дилемма разработки отчёта-использовать свой алгоритм или стандартную библиотеку генератора отчётов. Свой алгоритм был основан на использовании стандартного excell и ole automation. Загрузив стандартную библиотеку отчёта, я не смог сделать отчёт, выдавалась какая то ошибка в модулях генератора отчётов, возможно требовался подбор нужной версии библиотеки. Надо было разбираться а времени как всегда было мало. Применив свой алгоритм я достаточно быстро добавил формирование его в excell их бланка-заготовки. К тому же отчёт получился редактируемым
, что и было нужно. Теперь всегда использую такую технологию генерации отчётов. Можно формировать отчёты любой сложности, в том числе и с переменным количеством строк, используя вложенные циклы запросов к бд и ole управление Excel используя готовые бланки. Не очень сложно. Не используешь зависимости от дополнительных библиотек генератора отчётов, код довольно прост для рефакторинга.
ARad
10.01.2024 08:51+1Я не нашёл у `ReadOnlyMemory` метода SplitAny с одним параметром, похоже вы его сами написали?
amphasis
Кажется, в последнем варианте было-бы оптимальнее сделать так:
zolroman Автор
Да, вы правы, так будет лучше. По скорости разница не очень большая, а вот памяти в 2 раза меньше расходует.
ARad
Это предложение не совсем универсальное, дело в тонкостях реализации метода
Distinct. Вообще говоря он не гарантирует что порядок сохранится. Это актуально если работать с базами данных, там порядок может изменится. Его реализация для работы в памятью сохраняет порядок. К тому же если предикат отсеивает много элементов, то его лучше поднять выше сортировки.