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

@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]);
 
        }
    }
}

@Wolfdp · 19.12.2023, 09:36

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

расскажите что именно не получилось.

Читаемость нулевая. И явно сказывается минимум опыта и отсутсвия гибкости. Скажем эта строчка

C#
1
for (step = 0; (i + step) < str.Length && punctuations.Contains(str[i + step]); step++) ;

Вместо того чтобы ввести новый счетчик и просто считать его и общий индекс -- for явно завязывается только на step. А всё потому что у вас в голове конструкция for(int = 0; i < count; i++) не подразумевает каких либо модификаций, хотя по факту там можно объявлять любое количество переменных, условий и действия для итераций, включая ноль (их отсутсвие).

@OwenGlendower · 19.12.2023, 11:01

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

вы знаки препинания в обоих случаях сделайте одинаковые. Может и не сильно повлияет на результат, но так будет правильно.

С одинаковыми разделителями разница в скорости стала меньше, но общая картина не изменилась. Для сравнения также добавил к тесту вариант Wolfdp (под названием NoSplit2). Он показывает наилучший результат.

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

Результаты

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
| Method   | Count | Mean            | Error         | StdDev        | Ratio | Gen0     | Gen1     | Gen2     | Allocated | Alloc Ratio |
|--------- |------ |----------------:|--------------:|--------------:|------:|---------:|---------:|---------:|----------:|------------:|
| Split    | 1     |       154.45 ns |      0.545 ns |      0.483 ns |  1.00 |   0.0405 |        - |        - |     424 B |        1.00 |
| NoSplit  | 1     |       257.44 ns |      0.957 ns |      0.849 ns |  1.67 |   0.0043 |        - |        - |      48 B |        0.11 |
| NoSplit2 | 1     |        39.12 ns |      0.240 ns |      0.224 ns |  0.25 |   0.0046 |        - |        - |      48 B |        0.11 |
|          |       |                 |               |               |       |          |          |          |           |             |
| Split    | 100   |    11,608.00 ns |     34.145 ns |     31.940 ns |  1.00 |   3.1433 |   0.3357 |        - |   32896 B |       1.000 |
| NoSplit  | 100   |    25,013.70 ns |     63.627 ns |     56.404 ns |  2.15 |        - |        - |        - |      48 B |       0.001 |
| NoSplit2 | 100   |     3,128.21 ns |      7.027 ns |      6.229 ns |  0.27 |   0.0038 |        - |        - |      48 B |       0.001 |
|          |       |                 |               |               |       |          |          |          |           |             |
| Split    | 10000 | 5,362,807.34 ns | 97,531.587 ns | 91,231.107 ns |  1.00 | 367.1875 | 359.3750 | 117.1875 | 3280307 B |       1.000 |
| NoSplit  | 10000 | 2,369,402.37 ns |  8,997.763 ns |  7,976.283 ns |  0.44 |        - |        - |        - |      50 B |       0.000 |
| NoSplit2 | 10000 |   313,964.75 ns |    912.642 ns |    809.033 ns |  0.06 |        - |        - |        - |      48 B |       0.000 |

Код

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
[MemoryDiagnoser]
public class MaxLenBenchmark
{
    string str;
 
    [Params(1, 100, 10_000)]
    public int Count { get; set; }
 
    [GlobalSetup]
    public void GlobalSetup()
    {
        //str = string.Concat(Enumerable.Repeat("Разбейте строку на слова посчитайте длины и возьмите max", Count));
        str = string.Concat(Enumerable.Repeat("Lorem ipsum dolor sit amet, consectetur adipiscing elit", Count));
    }
 
    [Benchmark(Baseline = true)]
    public string Split()
    {
        string[] mas = str.Split(' ', ',', '.', '!', '?', ':', ';');
        int index = 0;
        for (int i = 1; i < mas.Length; i++)
            if (mas[index].Length < mas[i].Length)
                index = i;
 
        return mas[index];
    }
 
    [Benchmark]
    public string NoSplit()
    {
        int maxlen = 0;
        int index_maxlen = 0;
        string punctuations = " ,.!?:;";
 
        int step;
        for (int i = 0; i < str.Length; i += step)
        {
            for (step = 0; (i + step) < str.Length && punctuations.Contains(str[i + step]); step++) ;
 
            int temp_idx;
            for (temp_idx = i + step; (i + step) < str.Length && !punctuations.Contains(str[i + step]); step++) ;
            if (maxlen < ((i + step) - temp_idx))
            {
                index_maxlen = temp_idx;
                maxlen = ((i + step) - temp_idx);
            }
        }
 
        return str.Substring(index_maxlen, maxlen);
    }
 
    [Benchmark]
    public string NoSplit2()
    {
        int wordLength, index, maxWordLength = -1, maxIndex = -1;
        for (var i = 0; i < str.Length; i++)
        {
            if (char.IsLetter(str[i]))
            {
                wordLength = 0;
                index = i;
                do
                {
                    wordLength++;
                    i++;
                }
                while (i < str.Length && char.IsAsciiLetter(str[i]));
                if (wordLength > maxWordLength)
                {
                    maxWordLength = wordLength;
                    maxIndex = index;
                }
            }
        }
 
        return str.Substring(maxIndex, maxWordLength);
    }
}

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

А какое объяснение вы видите? Тогда наверное MS для Split использует какие-то оптимизации, которые для общих случаев не работают.

Какие-то оптимизации, да. В текущей версии .NET их много.

@belalugoci · 19.12.2023, 11:14

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

Читаемость нулевая

Мне всё понятно.

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

Вместо того чтобы ввести новый счетчик

Зачем?

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

и просто считать его

А текущий считает непросто?

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

и общий индекс

Какую задачу они решат?

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

for явно завязывается только на step

Если можно обойтись одной переменной зачем их 10 штук?

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

А всё потому что у вас в голове конструкция for(int = 0; i < count; i++) не подразумевает каких либо модификаций

Нет, это у вас в голове что-то не подразумевается. И большая любовь развешивать ярлыки. А я for и так и сяк использую совершенно нормально, вот вам ссылки на ранее опубликованное - тут и тут.

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

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

(под названием NoSplit2). Он показывает наилучший результат

Изучил. Отличное решение. Тот вариант, который написал я, но избавлен от недостатка делать кучу условий при проходе по знакам препинания, а использование стандартных методов для определения принадлежности символа вполне возможно заметно быстрее чем постоянная проверка подстроки со знаками препинания.

Сделайте замеры еще с вариантом с HashSet, у меня оно работало медленнее чем с обычной строкой.

@Wolfdp · 19.12.2023, 11:27

OwenGlendower, на всякий -- всё тестируется же в релизной сборке?
В целом, если прям копать по перфомансу, скорее всего все эти i+k и генерят лишнюю работу, хотя как-то разрыв подозрительно большой.

@belalugoci · 19.12.2023, 11:46

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

скорее всего все эти i+k и генерят лишнюю работу

ну с C# я не удивлюсь, хотя у меня уже была тема где появление новой переменной замедляло работу программы на внушительное время.
в моем случае i не меняется, а вот step постоянно меняется, поэтому вводить переменную для i+step смысла нет, вам всё равно её постоянно вычислять.
У вас один if убивает целиком строку
for (step = 0; (i + step) < str.Length && punctuations.Contains(str[i + step]); step++) ;
а стандартные методы IsLetter и т.п. вполне могут быть реализованы уже через хэш.
В общем отличная задачка для разминки и для того чтобы узнать новое.

@OwenGlendower · 19.12.2023, 12:16

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

на всякий -- всё тестируется же в релизной сборке?

Да. Это же BenchmarkDotNet. Он в Debug конфигурации вообще не запускается.

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

Сделайте замеры еще с вариантом с HashSet, у меня оно работало медленнее чем с обычной строкой.

Да, с HashSet медленнее (NoSplit_HS).

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

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| Method     | Count | Mean            | Error         | StdDev        | Ratio | Gen0     | Gen1     | Gen2     | Allocated | Alloc Ratio |
|----------- |------ |----------------:|--------------:|--------------:|------:|---------:|---------:|---------:|----------:|------------:|
| Split      | 1     |       161.01 ns |      0.764 ns |      0.678 ns |  1.00 |   0.0412 |        - |        - |     432 B |        1.00 |
| NoSplit    | 1     |       247.34 ns |      0.943 ns |      0.787 ns |  1.54 |   0.0043 |        - |        - |      48 B |        0.11 |
| NoSplit_HS | 1     |       391.96 ns |      1.398 ns |      1.308 ns |  2.43 |   0.0396 |        - |        - |     416 B |        0.96 |
| NoSplit2   | 1     |        40.38 ns |      0.414 ns |      0.387 ns |  0.25 |   0.0046 |        - |        - |      48 B |        0.11 |
|            |       |                 |               |               |       |          |          |          |           |             |
| Split      | 100   |    13,121.34 ns |     52.595 ns |     49.197 ns |  1.00 |   3.4485 |   0.4272 |        - |   36072 B |       1.000 |
| NoSplit    | 100   |    25,008.03 ns |     77.574 ns |     72.563 ns |  1.91 |        - |        - |        - |      48 B |       0.001 |
| NoSplit_HS | 100   |    28,566.21 ns |     81.071 ns |     75.834 ns |  2.18 |   0.0305 |        - |        - |     416 B |       0.012 |
| NoSplit2   | 100   |     3,231.04 ns |      7.136 ns |      6.675 ns |  0.25 |   0.0038 |        - |        - |      48 B |       0.001 |
|            |       |                 |               |               |       |          |          |          |           |             |
| Split      | 10000 | 6,260,053.75 ns | 64,937.168 ns | 60,742.268 ns |  1.00 | 406.2500 | 398.4375 | 132.8125 | 3600485 B |       1.000 |
| NoSplit    | 10000 | 2,373,111.72 ns |  6,786.859 ns |  6,348.432 ns |  0.38 |        - |        - |        - |      50 B |       0.000 |
| NoSplit_HS | 10000 | 2,849,974.02 ns |  6,338.950 ns |  5,619.314 ns |  0.46 |        - |        - |        - |     418 B |       0.000 |
| NoSplit2   | 10000 |   326,804.33 ns |  1,244.566 ns |  1,039.269 ns |  0.05 |        - |        - |        - |      48 B |       0.000 |

@belalugoci · 19.12.2023, 13:10

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

Да. Это же BenchmarkDotNet

а можете весь проект выложить? Я не смог повторить.

@OwenGlendower · 19.12.2023, 13:25

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

а можете весь проект выложить?

Ловите.

@Элд Хасп · 19.12.2023, 15:54

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

Сделайте замеры еще с вариантом с HashSet, у меня оно работало медленнее чем с обычной строкой.

Где-то попадались замеры производительности линейного поиска с HashSet (table).
Линейный растёт пропорционально количеству элементов. HashSet зависит от количества с очень маленьким коэффициентом. Но затраты на начало поиска значительные.
Скорее всего вот эти значительные начальные затраты и превысили выигрыш от HashSet для маленькой коллекции.
Не думал, что они будут настолько значительны.

@golosalex · 19.12.2023, 16:51

Сообщение от Элд Хасп

Где-то попадались замеры производительности линейного поиска с HashSet (table).
Линейный растёт пропорционально количеству элементов. HashSet зависит от количества с очень маленьким коэффициентом. Но затраты на начало поиска значительные.
Скорее всего вот эти значительные начальные затраты и превысили выигрыш от HashSet для маленькой коллекции.
Не думал, что они будут настолько значительны.

ну там надо хеш считать, вероятно это долгая операция для строк. мб там какая-то криптография замешана

@OwenGlendower · 19.12.2023, 17:04

Сообщение от Элд Хасп

Скорее всего вот эти значительные начальные затраты и превысили выигрыш от HashSet для маленькой коллекции.

Проверил эту гипотезу сделав HashSet<char> полем класса вместо локальной переменной. Всё равно медленнее работает. Моя гипотеза что накладные расходы на поиск в HashSet выше чем string.Contains т.к. символов мало.

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

ну там надо хеш считать, вероятно это долгая операция для строк. мб там какая-то криптография замешана

Какие строки? Тут же HashSet<char>. Реализация же char.GetHashCode очень простая

C#
1
2
3
4
public override int GetHashCode()
{
    return (int)(this | ((uint)this << 16));
}

@golosalex · 19.12.2023, 17:09

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

Какие строки? Тут же HashSet<char>. Реализация же char.GetHashCode очень простая

виноват, с какого-то момента потерял ход рассуждений в теме. думал, что HashSet<string>

@Элд Хасп · 19.12.2023, 17:48

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

Моя гипотеза что накладные расходы на поиск в HashSet выше чем string.Contains т.к. символов мало.

Ну, так я это и имел ввиду.

Добавлено через 7 минут
Грубо.
Сложность линейного поиска O₁(n).
А HashSet O₂(1)+O₃(n), где O₂ >> O₁ >> O₃.

@OwenGlendower · 19.12.2023, 17:56

Сообщение от Элд Хасп

Ну, так я это и имел ввиду.

Окей. Значит я неправильно понял выражение "начальные затраты".

@Wolfdp · 19.12.2023, 19:44

Не по теме:

Ужс эти ваши бейчмарки... я еле дождался, пока отработает.

Глянул откуда такие просадки у нашего местного активиста -- таки в вопросе определения "а это буква или нет". Основной профит в том что дотнетовская проверка на "букву" выглядит так public static bool IsAsciiLetter(char c) => (uint)((c | 0x20) - 'a') <= 'z' - 'a'; и переплюнуть это любым хештейблом крайне сложно. Заменив на неё, получил 702.6 us против 386.7 us, шо уже в рамках погрешности (ну и может таки строит срезать лишние операции над индексами).

Ещё отдельно замечу что проверка " ,.!?:;".Contains(ch) -- крайне неполная. Более правильно было бы делать на вхождение символа в алфавит (шо несколько увеличивает работу кода, но зато всегда правильно). Если не брать в расчет дотнетовский метод, всегда можно сделать в духе ch is >= 'a' and <= 'z' or >= 'A' and <= 'Z' Ну и семь раз i + step... ужс.

@OwenGlendower · 19.12.2023, 19:50

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

таки в вопросе определения "а это буква или нет".

Он же на пунктуацию проверяет, а не на букву. Отсюда и " ,.!?:;".

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

Ужс эти ваши бейчмарки... я еле дождался, пока отработает.

Серьезный инструмент. Не хухры-мухры!

@Wolfdp · 19.12.2023, 20:14

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

Он же на пунктуацию проверяет, а не на букву. Отсюда и " ,.!?:;".

Я же и говорю -- это не правильно (в общем случае. В рамках постановки задачи на "сдать и забыть" -- может и ок). Не буквенных символов гораздо больше семи. Опуская всякие табуляции и переносы -- где тире? На самом деле тут и проверка на вхождение в алфавит на самом деле канает только для русского языка. В английском апостроф -- часть слова (всякие word`s), и реальная проверка резко становится веселее.

Вообще я уже скинул что нужно ТСу. Пытаться на этой задаче постичь какие-то азы перфоменса... Ну, в целом когда я глянул внутрянку IsLetter, понял что порой правильнее определять рейндж, а не перечислять все значения и сверяться с ними. Может кому-то полезно узнать что можно массив анализирует кусками, а не дробить на отдельные строки (выедая память и время). Не говнокодить тоже вроде полезно.

@belalugoci · 19.12.2023, 21:33

Сохраню пока интригу

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

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
| Method             | Count | Mean            | Error          | StdDev         | Ratio | Gen0     | Gen1     | Gen2     | Allocated | Alloc Ratio |
|------------------- |------ |----------------:|---------------:|---------------:|------:|---------:|---------:|---------:|----------:|------------:|
| Split              | 1     |       184.32 ns |       2.524 ns |       2.361 ns |  1.00 |   0.0515 |        - |        - |     432 B |        1.00 |
| NoSplit_belalugoci | 1     |        41.92 ns |       0.248 ns |       0.220 ns |  0.23 |   0.0048 |        - |        - |      40 B |        0.09 |
| NoSplit_Wolfdp     | 1     |        48.58 ns |       0.428 ns |       0.401 ns |  0.26 |   0.0057 |        - |        - |      48 B |        0.11 |
|                    |       |                 |                |                |       |          |          |          |           |             |
| Split              | 100   |    14,349.10 ns |     167.551 ns |     148.529 ns |  1.00 |   4.3030 |   0.5188 |        - |   36072 B |       1.000 |
| NoSplit_belalugoci | 100   |       392.13 ns |       4.404 ns |       4.119 ns |  0.03 |   0.0057 |        - |        - |      48 B |       0.001 |
| NoSplit_Wolfdp     | 100   |     3,628.83 ns |      26.630 ns |      24.909 ns |  0.25 |   0.0038 |        - |        - |      48 B |       0.001 |
|                    |       |                 |                |                |       |          |          |          |           |             |
| Split              | 10000 | 6,890,771.40 ns | 133,658.389 ns | 223,313.142 ns | 1.000 | 500.0000 | 484.3750 | 156.2500 | 3600508 B |       1.000 |
| NoSplit_belalugoci | 10000 |     4,175.27 ns |      18.373 ns |      17.187 ns | 0.001 |        - |        - |        - |      48 B |       0.000 |
| NoSplit_Wolfdp     | 10000 |   366,600.11 ns |   4,727.857 ns |   4,422.440 ns | 0.054 |        - |        - |        - |      48 B |       0.000 |

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

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

Более правильно было бы делать на вхождение символа в алфавит

Ну тут проблема с условием задачи, сам препод должен решать что считать знаками препинания, то что указал я не сильно влияет на производительность если и добавить еще штук 7-10, так как знаков препинания все равно меньше чем букв и это будет эффективнее.

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

Ужс эти ваши бейчмарки

Run time: 00:03:11 для трёх по три

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

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

Ну и семь раз i + step... ужс

да как-то нет разницы, заменил на отдельную переменную.

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

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
| Method             | Count | Mean            | Error          | StdDev         | Ratio | Gen0     | Gen1     | Gen2     | Allocated | Alloc Ratio |
|------------------- |------ |----------------:|---------------:|---------------:|------:|---------:|---------:|---------:|----------:|------------:|
| Split              | 1     |       178.16 ns |       1.674 ns |       1.566 ns |  1.00 |   0.0515 |        - |        - |     432 B |        1.00 |
| NoSplit_belalugoci | 1     |        44.32 ns |       0.336 ns |       0.315 ns |  0.25 |   0.0048 |        - |        - |      40 B |        0.09 |
| NoSplit_Wolfdp     | 1     |        48.34 ns |       0.595 ns |       0.556 ns |  0.27 |   0.0057 |        - |        - |      48 B |        0.11 |
|                    |       |                 |                |                |       |          |          |          |           |             |
| Split              | 100   |    14,571.37 ns |     190.648 ns |     178.332 ns |  1.00 |   4.3030 |   0.5188 |        - |   36072 B |       1.000 |
| NoSplit_belalugoci | 100   |       393.69 ns |       2.679 ns |       2.237 ns |  0.03 |   0.0057 |        - |        - |      48 B |       0.001 |
| NoSplit_Wolfdp     | 100   |     3,619.62 ns |      31.165 ns |      29.152 ns |  0.25 |   0.0038 |        - |        - |      48 B |       0.001 |
|                    |       |                 |                |                |       |          |          |          |           |             |
| Split              | 10000 | 6,626,430.45 ns | 128,864.256 ns | 211,727.669 ns | 1.000 | 507.8125 | 500.0000 | 164.0625 | 3600410 B |       1.000 |
| NoSplit_belalugoci | 10000 |     4,163.27 ns |      17.505 ns |      16.374 ns | 0.001 |        - |        - |        - |      48 B |       0.000 |
| NoSplit_Wolfdp     | 10000 |   364,455.51 ns |   5,080.850 ns |   4,752.630 ns | 0.055 |        - |        - |        - |      48 B |       0.000 |

Добавлено через 57 минут
лошпет я, проверял варианты туда сюда и теперь не могу вернуться к 41 ns в бенче )
char.Punctuation работает иначе чем я подумал.

@belalugoci · 20.12.2023, 11:11

в общем сколько не крутил вчера вариантов но 41 нс так и не смог повторить, 68 нс самый минимальный.
еще странно себя повёл тест, сделал проверку на символы английского алфавита

C#
1
2
3
4
        bool Contains(char c)
        {
            return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
        }

в отдельном приложении всё работает исправно, а в тесте происходит зависание и вместо минуты крутилось пол часа без результата.
как видно я практически полностью переделал всё под вариант Wolfdp.

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

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
    [Benchmark]
    public string NoSplit_While()
    {
        int index = 0, maxindex = 0;
        int maxlen = 0;
        for (int i = 0; i < str.Length;)
        {
            if (Contains(str[i]))
            {
                index = i;
                for (; i < str.Length && Contains(str[i]); i++) ;
                if (maxlen < (i - index))
                {
                    maxindex = index;
                    maxlen = i - index;
                }
            }
            else
                i++;
        }
        if (maxlen > 0)
            Console.WriteLine("Длина = {0}, индекс в строке = {1}, слово = {2}", maxlen, maxindex, str.Substring(maxindex, maxlen));
        else
            Console.WriteLine("В тексте нет слов");
        Console.ReadLine();
        bool Contains(char c)
        {
            return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
        }
 
        return str.Substring(maxindex, maxlen);
    }

Может вы ошибку разглядите.
----

Еще придумал вариант для реализации, но мне кажется он если и будет интересным, то только на больших строках.
Суть вот в чём - нам не нужно смотреть всю строку, нам нужно искать слова которые больше текущего максимального, то есть нужно грубыми шагами выбирать интервал и если он удовлетворяет условию (ниже), то тогда делать полную проверку на слово.
Условие: после прыжка на длину+1 мы попали на букву, таким образом остаётся проверить на соответствие только интервал со второй буквы до предпоследней, если там будут все буквы, то можно проверять дольше чем прыжок, до тех пор пока не закончатся буквы. Во-первых это железно уже новое длинное слово, во-вторых - следующий поиск идёт с момента появления буквы с прыжком на длину+1.
Давайте в ручном режиме посмотрим на тестовую строку:
" Lorem ipsum dolor sit amet, consectetur adipiscing elit"
На старте длина слова 0, поэтому формируем первое слово "Lorem" с длиной 5.
Когда попадаем на первую букву слова "ipsum" то делаем прыжок на 5+1, попадаем на пробел.
Переходим к слову "dolor" прыгаем на 5+1, попадаем на пробел.
Переходим к "sit", прыгаем, попадаем на "m" в слове "amet", двигаемся назад проверяя на буквы, попадаем на пробел.
Переходим к "amet", прыгаем, попадаем на пробел.
Переходим к "consectetur", прыгаем на 5+1, проверка назад даёт все буквы, движемся вперёд и получаем новое длинное слово в 11 букв.
Переходим к слову "adipiscing", прыгаем на 11+1, попадаем на "e" ("elit"), назад проверка на буквы не проходит.
Строка закончилась.
Всего будет итераций:
1. первый пробел = 1
2. всё первое слово = 5
3. пропуск пробела = 1
4. прыжок за слово ipsum на пробел = 1
5. пропуск пробела = 1
6. прыжок за слово dolor на пробел = 1
7. пропуск пробела = 1
8. прыжок за слово sit на слово amet, при обратном проходе делаем 2 шага до пробела = 3
9. прыжок за слово amet на пробел = 1
10. пропуск пробела = 1
11. прыжок по слову consectetur на букву "c", обратная проверка 4 шага, дальше вперед вычисляем длину нового слова = 9
12. пропуск пробела = 1
13. прыжок через adipiscing на слово elit на букву "e" + 1 итерация до пробела = 2
14. конец строки = 1
При длине сроки в 56 байт мы сделали только 29 шагов.

Как-то так. Если кто-то быстро и ловко может реализовать этот алгоритм, буду признателен, я буду с ним возиться очень долго. Было бы интересно проверить его в работе, а так же понять на каких длинах строк появится положительный эффект (и появится ли вообще). Во всяком случае выглядит интересно.

Добавлено через 4 минуты
Получается чем длиннее в начале встретится слово, тем быстрее пройдёт поиск.

@belalugoci · 20.12.2023, 11:20

визуально примерно так

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

@Wolfdp 3790 / 1767 / 371 Регистрация: 15.06.2012 Сообщений: 6,543 Записей в блоге: 3
	19.12.2023, 11:27
	OwenGlendower, на всякий -- всё тестируется же в релизной сборке? В целом, если прям копать по перфомансу, скорее всего все эти i+k и генерят лишнюю работу, хотя как-то разрыв подозрительно большой. 0

@Wolfdp 3790 / 1767 / 371 Регистрация: 15.06.2012 Сообщений: 6,543 Записей в блоге: 3
	19.12.2023, 19:44
	Не по теме: Ужс эти ваши бейчмарки... я еле дождался, пока отработает. Глянул откуда такие просадки у нашего местного активиста -- таки в вопросе определения "а это буква или нет". Основной профит в том что дотнетовская проверка на "букву" выглядит так `public static bool IsAsciiLetter(char c) => (uint)((c \| 0x20) - 'a') <= 'z' - 'a';` и переплюнуть это любым хештейблом крайне сложно. Заменив на неё, получил 702.6 us против 386.7 us, шо уже в рамках погрешности (ну и может таки строит срезать лишние операции над индексами). Ещё отдельно замечу что проверка `" ,.!?:;".Contains(ch)` -- крайне неполная. Более правильно было бы делать на вхождение символа в алфавит (шо несколько увеличивает работу кода, но зато всегда правильно). Если не брать в расчет дотнетовский метод, всегда можно сделать в духе `ch is >= 'a' and <= 'z' or >= 'A' and <= 'Z'` Ну и семь раз `i + step`... ужс. 0

@belalugoci 475 / 294 / 29 Регистрация: 01.06.2018 Сообщений: 3,676
	20.12.2023, 11:20
	визуально примерно так Миниатюры 0