Comments 36
Не увидел, почему-то, самого короткого варианта:
text.Split().MaxBy(word => word.Length)
Не проводил бенчмарков, но на вскидку сказал бы что это будет работать шустрее, чем Aggreagate() и OrderByDescending().First(), да и читается лучше
я тоже люблю короткую запись, но когда нет задачи найти решение лучше.
вот тесты для кода
string word = str.Split(' ', ',', '.').MaxBy(word => word.Length);| Method | Length | Mean | Allocated |
|----------|--------|---------------|-----------|
| Jump | 1 | 61.76 ns | 40 B |
| Agregate | 1 | 312.72 ns | 920 B |
| MaxBy | 1 | 312.18 ns | 920 B |
|----------|--------|---------------|-----------|
| Jump | 100 | 3,525.11 ns | 40 B |
| Agregate | 100 | 28,048.78 ns | 82496 B |
| MaxBy | 100 | 26,584.78 ns | 82496 B |
|----------|--------|---------------|-----------|
| Jump | 1000 | 38,580.05 ns | 40 B |
| Agregate | 1000 | 831,457.50 ns | 824133 B |
| MaxBy | 1000 | 809,927.50 ns | 824133 B |Не увидел, почему-то, самого короткого варианта
К сожалению я не настолько продвинут в C#, поэтому многие вещи могу не знать.
У самурая нет императивного подхода, только декларатив..!
Если вы хотите быстрое решение, то всё таки в первую очередь надо знать и использовать стандартные методы. А именно использование IndexOf метода должно поднять производительность относительно поиска в циклах как у вас. Особенно если вы будете использовать .Net 8 варианты этого метода.
Спасибо, я посмотрю. Но статья именно о том, что большинство используют что-то неэффективное даже медленнее наивного способа. Интернет как раз забит решениями которое я поставил в самом начале и для меня, человека далекого от программирования, этот факт - боль печаль.
почитал спеки на MSDN и что-то я не понял как именно IndexOf должен увеличить производительность. Я конечно позже попробую реализовать через него, но пока я не вижу разницы с IsAsciiLetter например.
Если не трудно, напишите пример реализации с использованием IndexOf, так как я не смог придумать как это сделать. Например с IndexOfAny если задать массив char[] то вроде и можно поработать, но это же будет O(m*n) где m - длина массива char[], что точно не будет быстрым решением. А как фильтровать хотя бы латинские символы с помощью IndexOf я пока не могу понять, но и там это получится просто вариант IsLetter.
Да в .Net 7 нет вариантов которые ускорят обычный алгоритм, согласен.
В .Net 8 возможно можно ускорить обычный алгоритм. Там уже работа со спанами, что достаточно неудобно и это может помешать производительности... В общем у меня тут тоже сомнения что могут...
Алгоритм с прыжками этими методами уже не ускорить к сожалению.
Вообще я бы в проде использовал обычный RegEx. Если производительность критична, то с компиляцией в код... Получилась бы почти производительность обычного поиска, и возможность быстрого изменения, если бизнес правила изменятся...
public static int FastTwoLoops(string str)
{
var maxLength = 0;
for (int startIndex = 0, endIndex = 0; endIndex < str.Length;
startIndex = ++endIndex,
endIndex += maxLength)
{
if (!char.IsAsciiLetter(str[endIndex]))
continue;
for (var breakIndex = endIndex - 1; breakIndex >= startIndex; breakIndex--)
{
if (!char.IsAsciiLetter(str[breakIndex]))
{
endIndex = breakIndex;
goto Continue;
}
}
while (++endIndex < str.Length && char.IsAsciiLetter(str[endIndex])) ;
maxLength = endIndex - startIndex;
Continue:
;
}
return maxLength;
}Мой вариант алгоритма с прыжками, у вас как то путано показалось написано...
у вас как то путано показалось написано
я ваш разобрать не могу, мне кажется всегда так с чужими мыслями.
У вас интересная реализация получилась, буду изучать, так как непонятно немного )))
| Method | Length | Mean |
|--------------|--------|--------------|
| Jump | 1 | 46.07 ns |
| JumpNew | 1 | 50.30 ns |
| FastTwoLoops | 1 | 44.20 ns |
|--------------|--------|--------------|
| Jump | 100 | 2,464.11 ns |
| JumpNew | 100 | 2,706.07 ns |
| FastTwoLoops | 100 | 2,628.97 ns |
|--------------|--------|--------------|
| Jump | 1000 | 24,759.34 ns |
| JumpNew | 1000 | 28,123.92 ns |
| FastTwoLoops | 1000 | 27,054.33 ns |Небольшая оптимизация
public static int TwoLoops1Jump(string str)
{
var maxLength = 0;
for (int endIndex = 0, len = str.Length; endIndex < len; endIndex += maxLength + 1)
{
if (!char.IsAsciiLetter(str[endIndex]))
continue;
// Can IndexOf be faster here?
var startIndex = endIndex - maxLength;
for (var breakIndex = endIndex - 1; breakIndex > startIndex; breakIndex--)
{
if (!char.IsAsciiLetter(str[breakIndex]))
{
endIndex = breakIndex;
goto Continue;
}
}
if (!char.IsAsciiLetter(str[startIndex]))
startIndex++;
// Can IndexOf be faster here?
while (++endIndex < len && char.IsAsciiLetter(str[endIndex])) ;
maxLength = endIndex - startIndex;
Continue:
;
}
return maxLength;
}Небольшая оптимизация
| Method | Length | Mean |
|-----------------|--------|--------------|
| Jump | 1 | 43.56 ns |
| JumpNew | 1 | 48.33 ns |
| FastTwoLoops | 1 | 42.81 ns |
| FastTwoLoopsNew | 1 | 47.74 ns |
|-----------------|--------|--------------|
| Jump | 100 | 2,405.17 ns |
| JumpNew | 100 | 2,842.87 ns |
| FastTwoLoops | 100 | 2,561.28 ns |
| FastTwoLoopsNew | 100 | 3,324.67 ns |
|-----------------|--------|--------------|
| Jump | 1000 | 23,956.23 ns |
| JumpNew | 1000 | 27,156.41 ns |
| FastTwoLoops | 1000 | 26,018.34 ns |
| FastTwoLoopsNew | 1000 | 23,978.35 ns |Попробуйте переделать на do-while, эта реализация цикла сильно быстрее работает.
Насчёт циклов вы не правы. Любой цикл компилируется в условные переходы. В дотНет достаточно неплохой компилятор циклов, хоть и не идеальный.
Вы нашли у себя неоптимальности в главном цикле? Там у вас шаг по одному символу, я поэтому дальше смотреть код не стал, там явно ошибка...
Для отладки разделите слова в тестах большим количеством пробелов, например 100, в этом случае ваша реализация будет медленно работать, у вас там нет прыжков на длину слова. Думал заметите сами.
Насчёт циклов вы не правы
Я не настолько продвинут в C# чтобы спорить, я только руководствуюсь экспериментальными значениями и do-while работает быстрее чем for/while.
Вы нашли у себя неоптимальности в главном цикле? Там у вас шаг по одному символу, я поэтому дальше смотреть код не стал, там явно ошибка...
Вроде вот эта строка этим занимается, вы об этом? Я как раз тут учитывал прыжки по "пробелам"
i += maxlen;
Это как раз в 3 апдейте в статье появилось.
https://github.com/AlexRadch/dotNetMisc HabrMisc\LongestWordLength\LongestWordLength.sln
Я ваши методы только что добавил, у них есть проблема когда разделение слов длинное.
| TwoLoops | 100000 | 3,674.812 μs | 71.7678 μs | 95.8080 μs | 3,645.900 μs | 736 B |
| TwoLoops1Jump | 100000 | 1,283.652 μs | 29.3687 μs | 83.3142 μs | 1,278.200 μs | 736 B |
| Jump | 100000 | 3,133.623 μs | 48.3515 μs | 40.3757 μs | 3,129.000 μs | 736 B |
| JumpNew | 100000 | 3,255.214 μs | 61.6167 μs | 54.6216 μs | 3,239.050 μs | 736 B |
вы взяли старые версии, свежее в UPD3
Это версия из "начала" и она у вас в проекте:
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;Это версия из UPD3:
int maxlen = 0, maxindex = -1, len = str.Length;
for (int i = 0; i < len - maxlen; i++)
{
int index = i;
i += maxlen;так же легко видно по замене на do-while
int k = maxLen > 0 ? 1 : 0;
do i -= k;
while (i > index && char.IsAsciiLetter(str[i]));а у вас старая версия
у меня ваш бенч не хочет проходить при размере в 1000, а ошибку я сам не найду.
Да обновил до версии UPD3, видать невнимательно скопировал.
Этот вариант не проходит тесты, к сожалению. Jump return 15 should 14
Он возращает что самое длинное слово имеет длину 15, по моим расчётам должна быть 14.
LongestWord = Regex.Split(Words, "[^a-zA-Z]+").Max(word => word.Length);Я использую такую регулярку для проверки.
я немного переделал основной цикл, пока тестирую, там под вашу идею, сразу в цикле i += maxlen + 1, это позволяет убрать из первого if проверку на выход за пределы строки, так как такая проверка уже проводится в for.
public string Jump()
{
int maxlen = 0, maxindex = -1, len = str.Length;
for (int i = 0; i < len - maxlen; i += maxlen + 1)
{
int index = i - maxlen;
//i += maxlen;
if (char.IsAsciiLetter(str[i]))
{По ошибке сложно сказать, у меня с разными строками выполняется сразу несколько реализаций и все дают одинаковый результат.
Тест на такой строке:
"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. . . . . . ."| Method | Length | Mean |
|---------------|--------|--------------|
| Jump | 1 | 98.17 ns |
| JumpNew | 1 | 97.57 ns |
| TwoLoops | 1 | 113.38 ns |
| TwoLoops1Jump | 1 | 88.61 ns |
|---------------|--------|--------------|
| Jump | 100 | 4,847.12 ns |
| JumpNew | 100 | 5,204.50 ns |
| TwoLoops | 100 | 5,322.67 ns |
| TwoLoops1Jump | 100 | 5,534.59 ns |
|---------------|--------|--------------|
| Jump | 1000 | 56,442.69 ns |
| JumpNew | 1000 | 53,372.84 ns |
| TwoLoops | 1000 | 53,534.55 ns |
| TwoLoops1Jump | 1000 | 51,109.82 ns |Можете еще одну статью посмотреть, там автор вроде IndexOf использует, возможно это тот вариант что вы хотели проверить.
Полностью поддерживаю автора, по концепции, не люблю я писать сложные алгоритмы которые тяжело поддерживать при изменении требований.
Лучше написать простую и достаточно эффективную реализацию, которая пусть даже в 5-10 раз медленнее, но которую легко менять под изменения.
Грубо говоря я бы сделал алгоритм который бы быстро и лениво возвращал следующее слово без учёта всяких других требований.
А вот вокруг него уже можно натянуть какие хочешь требования бизнеса. Да конкретно для поиска самого длинного слова он будет примерно в 3 раза медленнее, но если требования будут меняться, добавляться, его поддерживать буде раз в 100 быстрее. А это важнее...
Насчёт конкретной реализации я думаю что у автора не самая удачная. Можно лучше и проще.
del
У вас во втором сниппете кода баг. Сможете найти?
// 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));
О багах знаю, нашел сильно после выхода статьи, исправлять не стал так как из головы уже всё выветрилось, а заново изучать код, быстро вникать в тему - я не способен. Поэтому просто не стал трогать.
Сниппет — это блок с краткой информацией о странице сайта, содержащий ссылку на документ, который отображается в результатах поиска.
Основная задача сниппета — дать пользователю первоначальное представление о содержимом страницы и показать, насколько страница соответствует поисковому запросу, не позволяя при этом переходить по ссылке на саму страницу.
В сниппете могут отображаться:
фавикон;
заголовок и описание;
адрес страницы;
быстрые ссылки;
контактная информация;
метки (если у сайта есть знаки);
рейтинг организации.
Что вы подразумеваете под сниппетом в контексте статьи?
Если что я не программист даже в ближайшем приближении, так что копание в моих статьях с целью найти ошибку и таким образом компенсировать недостатки вашей статьи - плохая затея. Примите как константу что я тупой и глупый говнокодер.
О багах знаю, нашел сильно после выхода статьи, исправлять не стал так как из головы уже всё выветрилось, а заново изучать код, быстро вникать в тему - я не способен. Поэтому просто не стал трогать.
Получается, если я захочу воспроизвести ваши результаты на своем компьютере и измерить время работы у себя, у меня не получится это сделать? В чем смысл тогда вообще код приводить, если вы знаете, что он работать не будет?
Сниппет — это блок с краткой информацией о странице сайта, содержащий ссылку на документ, который отображается в результатах поиска.
Сниппет - это просто англицизм от англ. snippet - фрагмент, отрывок. Тем более, смысл был из контекста понятен.
Получается, если я захочу воспроизвести ваши результаты на своем компьютере и измерить время работы у себя, у меня не получится это сделать?
се-ля-ви, 80% кода в интернете имеет такие качества. Но вы так пишете словно у меня вообще всё не работает.
В чем смысл тогда вообще код приводить, если вы знаете, что он работать не будет?
Это называется - докопаться до столба. Я же вам уже ответил, что знание об ошибке я получил сильно позже выхода статьи, то есть в ваших словах нет ни грамма логики.
Сниппет - это просто англицизм от англ. snippet - фрагмент, отрывок. Тем более, смысл был из контекста понятен.
Я не знаю английский, поэтому аналогию я попробовал взять из поисковика, который вам привёл, там что-то про сайты, что не вписывалось в тему.
del
Имея на руках две реализации можем посмотреть как они себя поведут в бенчмарке (Length - кратное увеличение размера строки, чтобы смотреть как ведет себя реализация на больших данных)
Из статьи не совсем ясно, что такое "большие данные". Нет ни слова о том, как вы их на самом деле генерируете, а это может существенно влиять на бенчмарки.
Если я верно понял, вы просто много раз повторяете исходную строку? В таком случае, это не совсем честный бенчмарк, т.к. максимум достигается почти сразу (на первом же вхождении исходной строки в длинную). Интереснее было бы посмотреть на тест, в котором максимум постоянно растет.
Из статьи не совсем ясно, что такое "большие данные"
10 байт - маленькие данные, 10 гигабайт - большие данные
Нет ни слова о том, как вы их на самом деле генерируете
это вне рамок статьи, мы же не про бенчмарки говорим, или вы когда картинку выкладывали для статьи рассказывали как ее рисовали в Paint? Это просто инструмент.
а это может существенно влиять на бенчмарки
может, но я тестировал и на цельном TXT, на романе Жюля Верна и результаты не менялись, так что это опять не важно для статьи.
Если я верно понял, вы просто много раз повторяете исходную строку? В таком случае, это не совсем честный бенчмарк, т.к. максимум достигается почти сразу (на первом же вхождении исходной строки в длинную). Интереснее было бы посмотреть на тест, в котором максимум постоянно растет.
Если вы внимательно читали статью, то заметили что она о другом. На экстремумах я всё так же тестировал, флуктуации есть, но не принципиальные. Например в упомянутом тексте Верна максимальное слово находится на отметке кажется в 240000 знаков, а весь файл 840000, учитывая что вероятность появления длинного слова в начале такая же кк и в конце, то изучение этого может быть чем-то самостоятельным, но не для этой статьи, она о другом.
В поисках алгоритмического дзена