Самое длинное слово в строке

@dmitrynikolaev3 · Регистрация: 12.10.2021

Студворк — интернет-сервис помощи студентам

Можете объяснить почему не правильно выдаёт?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using System;
using System.Text;
 
namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            // Дана строка, состоящая из английских слов,
            // разделенных пробелами и знаками препинания. Определить длину самого короткого слова.
            string str = "Разбейте строку на слова посчитайте длины и возьмите max";
            string[] mas = str.Split(' ');
            string max = null;
            int index = 0;
 
            for (int i = 0; i < mas.Length; i++)
            {
                for (int j = i + 1; j < mas.Length; j++)
                {
                    if (mas[i].Length > mas[j].Length)
                    {
                        max = mas[i];
                        index = i;
                    }
                }
            }
            Console.WriteLine(mas[index]);
 
        }
    }
}

@belalugoci · 20.12.2023, 17:29

первая реализация, нужно еще посмотреть может как-то можно упросить.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int index = 0, maxindex = -1, ii, iii;
for (int i = 0; i < str.Length; i = iii)
{
    if (char.IsAsciiLetter(str[i]))
    {
        index = i;
        ii = iii = i + maxlen;
        if (iii < str.Length && char.IsAsciiLetter(str[iii]))
        {
            do
            {
                iii--;
            }
            while (iii > index && char.IsAsciiLetter(str[iii]));
            if (i == iii)
            {
                while (ii < str.Length && char.IsAsciiLetter(str[ii]))
                {
                    ii++;
                }
                if (maxlen < (ii - i))
                {
                    maxindex = index;
                    maxlen = ii - i;
                }
                iii = ii;
            }
            else
            {
                iii++;
            }
        }
    }
    else
        iii = i + 1;
}

Добавлено через 31 минуту
Ну что ж, я дважды тупица, тратил время чтобы догнать 41 нс, но при этом имел только 68 нс, но дело в том что я сейчас всё делаю на другом ПК с другим ЦПУ )))
---
В общем я реализацию подсунул в бенчмарк, вроде без проблем посчитало. Я удивлён что получилось быстрее на такой короткой строке. На 10000 прогоню позже, на этом ЦПУ будет очень долго тестироваться.

Code
1
2
3
4
5
6
7
8
9
| Method         | Count | Mean         | Error      | StdDev     | Ratio | Gen0    | Allocated | Alloc Ratio |
|--------------- |------ |-------------:|-----------:|-----------:|------:|--------:|----------:|------------:|
| Split          | 1     |    361.00 ns |   3.001 ns |   2.808 ns |  1.00 |  0.1373 |     432 B |        1.00 |
| NoSplit_Wolfdp | 1     |     87.71 ns |   0.301 ns |   0.267 ns |  0.24 |  0.0153 |      48 B |        0.11 |
| NoSplit_new    | 1     |     62.57 ns |   0.792 ns |   0.741 ns |  0.17 |  0.0153 |      48 B |        0.11 |
|                |       |              |            |            |       |         |           |             |
| Split          | 100   | 29,444.22 ns | 382.477 ns | 357.769 ns |  1.00 | 11.4746 |   36072 B |       1.000 |
| NoSplit_Wolfdp | 100   |  7,111.35 ns |  23.695 ns |  22.164 ns |  0.24 |  0.0153 |      48 B |       0.001 |
| NoSplit_new    | 100   |  1,809.82 ns |   3.310 ns |   3.097 ns |  0.06 |  0.0153 |      48 B |       0.001 |

Добавлено через 1 час 23 минуты
Немного прибрался в переменных, но стало хуже, я хз что- там нужно C#.

Кликните здесь для просмотра всего текста

Code
1
2
3
4
5
6
7
8
9
10
11
| Method         | Count | Mean         | Error      | StdDev     | Ratio | Gen0    | Allocated | Alloc Ratio |
|--------------- |------ |-------------:|-----------:|-----------:|------:|--------:|----------:|------------:|
| Split          | 1     |    358.70 ns |   4.532 ns |   4.239 ns |  1.00 |  0.1373 |     432 B |        1.00 |
| NoSplit_Wolfdp | 1     |     90.45 ns |   0.808 ns |   0.756 ns |  0.25 |  0.0153 |      48 B |        0.11 |
| NoSplit_new    | 1     |     60.96 ns |   0.368 ns |   0.326 ns |  0.17 |  0.0153 |      48 B |        0.11 |
| NoSplit_new2   | 1     |     66.21 ns |   0.254 ns |   0.238 ns |  0.18 |  0.0153 |      48 B |        0.11 |
|                |       |              |            |            |       |         |           |             |
| Split          | 100   | 29,265.33 ns | 136.194 ns | 120.733 ns |  1.00 | 11.4746 |   36072 B |       1.000 |
| NoSplit_Wolfdp | 100   |  7,120.67 ns |  34.525 ns |  30.605 ns |  0.24 |  0.0153 |      48 B |       0.001 |
| NoSplit_new    | 100   |  1,775.22 ns |   5.306 ns |   4.963 ns |  0.06 |  0.0153 |      48 B |       0.001 |
| NoSplit_new2   | 100   |  2,021.62 ns |   6.171 ns |   5.772 ns |  0.07 |  0.0153 |      48 B |       0.001 |

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int maxlen = 1;
int maxindex = -1;
for (int i = 0; i < str.Length;)
{
    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; i < str.Length && char.IsAsciiLetter(str[i]); i++) ;
                if (maxlen < (i - index))
                {
                    maxindex = index;
                    maxlen = i - index;
                }
            }
            else i++;
        }
    }
    else i++;
}

Добавлено через 36 минут
забыл немного про микро-улучшайзер:

C#
1
for (i += maxlen; i < str.Length && char.IsAsciiLetter(str[i]); i++) ;

Здесь нужно i увеличивать на maxlen+1, так как место на maxlen мы уже знаем что это буква.
Изменение в выполнении:

Кликните здесь для просмотра всего текста

Code
1
2
3
4
5
6
7
8
9
| Method         | Count | Mean        | Error     | StdDev    | Ratio | Gen0   | Allocated | Alloc Ratio |
|--------------- |------ |------------:|----------:|----------:|------:|-------:|----------:|------------:|
| NoSplit_Wolfdp | 1     |    89.94 ns |  0.950 ns |  0.889 ns |  1.00 | 0.0153 |      48 B |        1.00 |
| NoSplit_new    | 1     |    62.37 ns |  1.227 ns |  1.148 ns |  0.69 | 0.0153 |      48 B |        1.00 |
| NoSplit_new2   | 1     |    64.23 ns |  0.450 ns |  0.399 ns |  0.71 | 0.0153 |      48 B |        1.00 |
|                |       |             |           |           |       |        |           |             |
| NoSplit_Wolfdp | 100   | 7,147.81 ns | 22.442 ns | 20.992 ns |  1.00 | 0.0153 |      48 B |        1.00 |
| NoSplit_new    | 100   | 1,810.99 ns | 10.655 ns |  9.967 ns |  0.25 | 0.0153 |      48 B |        1.00 |
| NoSplit_new2   | 100   | 2,013.75 ns |  5.950 ns |  4.646 ns |  0.28 | 0.0153 |      48 B |        1.00 |

Ну и на пробу увеличил строку в 10 раз, и эффект от такого подхода хорошо проявился, если для строки в 56 байт разница с посимвольным обходом была в 1.5 раза в пользу "прыгающего" алгоритма, то на 560 байтах разница составила уже 3.2 раза на одном проходе и 4.18 раза на 100. (надеюсь я правильно понял смысл Count и Ratio?)

Кликните здесь для просмотра всего текста

Code
1
2
3
4
5
6
7
8
9
| Method         | Count | Mean        | Error     | StdDev    | Ratio | Gen0   | Allocated | Alloc Ratio |
|--------------- |------ |------------:|----------:|----------:|------:|-------:|----------:|------------:|
| NoSplit_Wolfdp | 1     |    730.6 ns |   8.10 ns |   7.58 ns |  1.00 | 0.0153 |      48 B |        1.00 |
| NoSplit_new    | 1     |    226.5 ns |   0.79 ns |   0.74 ns |  0.31 | 0.0153 |      48 B |        1.00 |
| NoSplit_new2   | 1     |    244.1 ns |   0.57 ns |   0.51 ns |  0.33 | 0.0153 |      48 B |        1.00 |
|                |       |             |           |           |       |        |           |             |
| NoSplit_Wolfdp | 100   | 71,227.3 ns | 431.72 ns | 403.83 ns |  1.00 |      - |      48 B |        1.00 |
| NoSplit_new    | 100   | 17,326.5 ns | 108.97 ns |  96.60 ns |  0.24 |      - |      48 B |        1.00 |
| NoSplit_new2   | 100   | 19,689.5 ns |  68.77 ns |  60.96 ns |  0.28 |      - |      48 B |        1.00 |

Добавлено через 24 минуты

Сообщение от belalugoci

Ну и на пробу увеличил строку в 10 раз

в тесте конкатенация по Count для самой строки, я в ударе

Добавлено через 16 минут
Подумал будет ли как-то лучше работать если искать внутри буквы после прыжка в прямом направлении а не в обратном, но мне кажется в обратном лучше в том смысле, что вы по сути не только проверяем новое слово, но так же находим начало сплошного набора букв, если попадем в поисках на знак препинания. Если бы мы двигались в прямом направлении, то найденный знак препинания конечно нам давал информацию о том, что это не будет новое слово, но мы не знаем с какой позиции делать новый прыжок и придется цикл продолжать. С другой стороны букв в строке должно быть всегда больше чем знаков препинания, которые обычно идут по 1-2. Самым выгодным при прыжках будет попадание на знак препинания, так как можно 100% пропускать знаки препинания и делать следующий прыжок.
В общем наверное в случае если знак препинания 1, то разницы нет, а если их два, например запятая+пробел или точка+пробел и т.п., то выгоднее делать обратный поиск, так как он гарантирует только 1 итерацию для обхода знака препинания.

Добавлено через 3 минуты
Я всё думал, на что похожа эта реализация поиска и тут меня осенило, так это же частный случай алгоритма Кнута-Морриса-Пратта

Добавлено через 15 минут

Сообщение от belalugoci

так это же частный случай алгоритма Кнута-Морриса-Пратта

Ошибся, перечитал сейчас вики, это скорее Алгоритм Бойера-Мура-Хорспула.

Добавлено через 15 минут
Нужно еще бинарный поиск затолкать в поиск букв в слове после прыжка.

Худший случай, это когда вся строка состоит из возрастающих по длине слов, тогда алгоритм превратится в O(n) и бинарный поиск не поможет, так как мы ищем буквы и во всех случаях придется завершать полный поиск.

Добавлено через 1 час 33 минуты

Сообщение от belalugoci

Code
1
2
3
4
5
6
7
8
9
| Method | Count | Mean | Error | StdDev | Ratio | Gen0 | Allocated | Alloc Ratio |
|--------------- |------ |------------:|----------:|----------:|------:|-------:|----------:|------------:|
| NoSplit_Wolfdp | 1 | 89.94 ns | 0.950 ns | 0.889 ns | 1.00 | 0.0153 | 48 B | 1.00 |
| NoSplit_new | 1 | 62.37 ns | 1.227 ns | 1.148 ns | 0.69 | 0.0153 | 48 B | 1.00 |
| NoSplit_new2 | 1 | 64.23 ns | 0.450 ns | 0.399 ns | 0.71 | 0.0153 | 48 B | 1.00 |
| | | | | | | | | |
| NoSplit_Wolfdp | 100 | 7,147.81 ns | 22.442 ns | 20.992 ns | 1.00 | 0.0153 | 48 B | 1.00 |
| NoSplit_new | 100 | 1,810.99 ns | 10.655 ns | 9.967 ns | 0.25 | 0.0153 | 48 B | 1.00 |
| NoSplit_new2 | 100 | 2,013.75 ns | 5.950 ns | 4.646 ns | 0.28 | 0.0153 | 48 B | 1.00 |

Интересно что тест выше запускался на Core i5-2400, а тест ниже на Ryzen 5 3600, обратил внимание что при короткой строке реализация new2 быстрее.

Code
1
2
3
4
5
6
7
8
9
| Method         | Count | Mean        | Error     | StdDev    | Ratio | Gen0   | Allocated | Alloc Ratio |
|--------------- |------ |------------:|----------:|----------:|------:|-------:|----------:|------------:|
| NoSplit_Wolfdp | 1     |    47.10 ns |  0.582 ns |  0.544 ns |  1.00 | 0.0057 |      48 B |        1.00 |
| NoSplit_new    | 1     |    37.69 ns |  0.661 ns |  0.586 ns |  0.80 | 0.0057 |      48 B |        1.00 |
| NoSplit_new2   | 1     |    35.73 ns |  0.315 ns |  0.294 ns |  0.76 | 0.0057 |      48 B |        1.00 |
|                |       |             |           |           |       |        |           |             |
| NoSplit_Wolfdp | 100   | 3,560.25 ns | 36.378 ns | 34.028 ns |  1.00 | 0.0038 |      48 B |        1.00 |
| NoSplit_new    | 100   | 1,200.00 ns | 23.787 ns | 33.346 ns |  0.34 | 0.0057 |      48 B |        1.00 |
| NoSplit_new2   | 100   | 1,461.71 ns | 28.829 ns | 41.345 ns |  0.42 | 0.0057 |      48 B |        1.00 |

@belalugoci · 21.12.2023, 07:43

Wolfdp, OwenGlendower, что скажете по поводу разницы в производительности двух последних вариантов, один, где я использовал переменные i, ii, iii и второй где только i, почему вариант с i работает медленнее?

@OwenGlendower · 21.12.2023, 11:11

Сообщение от belalugoci

что скажете по поводу разницы в производительности двух последних вариантов

Я ничего не скажу. Лично у меня это задача не вызывает большого интереса. Извините.

Сообщение от belalugoci

надеюсь я правильно понял смысл Count и Ratio?

С Count вы ошиблись. Это параметр теста означающий количество раз сколько нужно размножить строку. Смотрите метод GlobalSetup. Он автоматически вызывается перед выполнением теста. Count является аргументом для string.Concat. Таким образом регулируется длина строки. Я использовал три значения - 1, 100, 10000 - для симуляции сценариев короткая, средняя, длинная строка.

@belalugoci · 21.12.2023, 11:43

Сообщение от OwenGlendower

Лично у меня это задача не вызывает большого интереса

ну это не вопрос самой задачи, это скорее проблема C#, которую я озвучивал ранее - когда манипуляции с переменными приводят к падению/повышению производительности, Иногда весьма значительно.

Сообщение от OwenGlendower

С Count вы ошиблись

я следом уже написал об этом.

Новые блоги и статьи Все статьи Все блоги /
Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .
Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты

@belalugoci 475 / 294 / 29 Регистрация: 01.06.2018 Сообщений: 3,676
	21.12.2023, 07:43
	Wolfdp, OwenGlendower, что скажете по поводу разницы в производительности двух последних вариантов, один, где я использовал переменные i, ii, iii и второй где только i, почему вариант с i работает медленнее? 0