PascalABC.NET версия 3.6.2 (будущие изменения)


#42

Проверьте свой код на вот этой задаче


#43

Публичный пример проходит нормально. Для остального просит зарегистрироваться.

P.S. Всё же зарегестрировался:

Но вообще задача не на 100% показывает возможности моего решения. Если бы было разрешено вводить сначала искомую строку - можно было бы всё потоково искать:

  SeqGen(1,i->ReadChar).Cycle
  .TakeWhile(ch->ch<>#10)
  .IndicesOf1(ReadString) // прочитает до начала вычисления последовательности
  .PrintLines;

#44

Там достаточно суровые тесты есть, раз прошло - значит работоспособная функция, можно больше тестов не искать. То, что все работает на последовательности - вполне понятно, КМП-алгоритм однопроходный. Вот только плохо, что он у Вас вдвое дольше работает при практически таких же затратах памяти.


#45

Ну правильно, как я и сказал - в том тесте строка, в которой ищут, находится в начале ввода, поэтому в любом случае приходиться всё заранее прочитать.

В итоге в моём коде память экономиться только на выводе, потому что у меня не создаётся куча лишних массивов в списке, и затем в .Select.ToArray .

Ну а насчёт сколько экономится - я не вижу чтоб там было сказано, для строк какой длины отображает расход памяти. Да и сомневаюсь что их тестер умеет вставлять System.GC.Collect в код, чтоб смотреть не на кол-во мёртвых объектов в куче, а на реальных расход памяти.


Насчёт скорости - в ближайшее время проверю со стопвочем.


#47

А Вы что, верите, будто вызов GC мгновенно освобождает память? Когда пользователь программу запускает, ему дела до GC нет никакого, это проблема системы - мусор убирать. Программирование всегда работает на результат, т.е. на общее время, которое уходит от запуска программы до получения результата. Также и расход памяти (если он интересен) интересен не в какой-то вымороченный момент и не функцию, а на программу в целом. Расход памяти и время на АСМР выдается для каждого прогона программы. И всегда можно посмотреть, как шло выполнение. %D0%A1%D0%BD%D0%B8%D0%BC%D0%BE%D0%BA

И не надо рассказывать, что если для Вашего решения создать какие-то особые условия, вот тут оно себя покажет. Решение должно нормально работать в любом случае, если уж Вы за него беретесь. А пока, извините, это все “я тут написал круто и оптимально, работает в потоке (нафига, спрашивается, нужна эта работа в потоке?), нет массива с лишним одним (!) элементом, да вообще - круть, как ни глянь” - оно программирование ради программирования, а не на результат. Получите на своем решении схожие значения - будет повод поговорить.


#48

Это хорошие результаты - и по времени и по памяти. Сравнимые с Free Pascal. Зная, как меряется время на олимпиадных сайтах для .NET-приложений, - это отличный результат.

@Sun_Serega - если сможете переписать и улучшить алгоритм - будет круто. Но потоковостью с моей точки зрения не надо увлекаться - она может замедлить. Массив - он самый быстрый.


#49

Не могу сейчас найти…

Ну, смысл прост: при запуске программы - запускаются 2 стопвоча. При каждом вызове Milliseconds и MillisecondsDelta - второй стопвоч обнуляется. Далее Milliseconds берёт время первого стопвоча, а MillisecondsDelta - второго. Больше, вроде, ничего не надо.

Да. Вызов System.GC.Collect замораживает вызвавший поток на пару сотен миллисекунд. Наверное же он там что то делает в это время. Без вызова System.GC.Collect - да, ничего сразу освобождаться не должно. И поэтому насиловать CLR вызовами сборщика - обычно плохая идея.

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

Да, я потихоньку тестирую что можно сделать… Но то что могу сразу сказать - если заменить в моём коде yield на заполнение списка - для больших строк всё становится раза в 2 медленнее. Потоковость это не всегда плохо.

Но, что я так же нашёл - foreach по строке это жесть как медленно. Без него я уже смог получить результаты примерно как у @RAlex. Но факт что при результате в виде yield должно быть быстрее - значит что можно найти ещё что то улучшаемое.


#50

А теперь я это не могу воспроизвести…

Ну, результаты лучше чему RAlex получаются без проблем:

program prog;

{$region RAlex 0}

function PrefixFunction0(s: string): array of integer;
// возвращает массив граней для строки-аргумента
begin
  var n := s.Length;
  Result := ArrFill(n + 1, 0);
  for var i := 1 to n - 1 do
  begin
    var temp := Result[i];
    while (temp > 0) and (s[i + 1] <> s[temp + 1]) do
      temp := Result[temp];
    Result[i + 1] := s[i + 1] = s[temp + 1] ? temp + 1 : 0
  end
end;

/// Возвращает массив индексов вхождений подстроки в основную строку 
///Параметр overlay определяет, разрешены ли перекрытия вхождений подстрок
function IndicesOf0(Self, SubS: string; overlay: boolean := False): array of integer; extensionmethod;
// Реализует КМП-алгоритм.
// Возвращает массив начальных позиций вхождений подстроки P в строку
// Параметр overlay определяет, разрешены ли перекрытия положений подстрок.
begin
  var L := new List<integer>;
  var (n, m) := (Self.Length, SubS.Length);
  var border := PrefixFunction0(SubS);
  var temp := 0;
  for var i := 1 to n do
  begin
    while (temp > 0) and (SubS[temp + 1] <> Self[i]) do
      temp := border[temp];
    if SubS[temp + 1] = Self[i] then
      temp += 1;
    if temp = m then
    begin
      var pos := i - m + 1;
      if overlay or (L.Count = 0) or (pos >= L[L.Count - 1] + m) then 
        L.Add(pos);
      temp := border[m]
    end;
  end;
  Result := L.Select(i -> i - 1).ToArray
end;

{$endregion RAlex 0}

{$region Sun Serega 1}

///Возвращает массив индексов вхождений подстроки в основную строку
///Использует алгоритм КМП
///Параметр allow_overlap определяет, разрешены ли перекрытия вхождений подстрок
function IndicesOf1(self, value: string; allow_overlap: boolean): List<integer>; extensionmethod;
begin
  
  {$region prefix inds}
  
  var val_inds := new integer[value.Length];
  // val_inds[0] никогда не заполняется и остаётся нулём
  // Примеры заполнения:
  
  // value   : abcab
  // знач. i : 01234
  // val_inds:  0012
  
  // value   : aabaabaaa
  // знач. i : 012345678
  // val_inds:  10123452
  
  var prev_val_ind := 0;
  for var i := 1 to value.Length-1 do
  begin
    
    while true do
    begin
      if value[prev_val_ind + 1] = value[i + 1] then
      begin
        prev_val_ind += 1;
        break;
      end;
      if prev_val_ind=0 then break;
      prev_val_ind := val_inds[prev_val_ind-1];
    end;
    
    val_inds[i] := prev_val_ind;
  end;
  
  {$endregion prefix inds}
  
  {$region Result}
  
  prev_val_ind := 0;
  var res_l := value.Length;
  var res_ind := -(res_l-1);
  
//  foreach var ch in self do
//  begin
  
//  var enmr := self.GetEnumerator;
//  while enmr.MoveNext do
//  begin
//    var ch := enmr.Current;
  
  var res := new List<integer>;
  for var i := 1 to self.Length do
  begin
    
    while true do
    begin
      if value[prev_val_ind + 1] = self[i] then
      begin
        prev_val_ind += 1;
        
        if prev_val_ind=res_l then
        begin
          res += res_ind;
//          yield res_ind;
          prev_val_ind := allow_overlap ? val_inds[prev_val_ind-1] : 0;
        end;
        
        break;
      end;
      if prev_val_ind=0 then break;
      prev_val_ind := val_inds[prev_val_ind-1];
    end;
    
    res_ind += 1;
  end;
  
  Result := res;
  {$endregion Result}
  
end;

{$endregion Sun Serega 1}

begin
  var lc1 := 100;
  var lc2 := 10;
  Randomize(0);
  var s := new string(ArrRandom(100000, integer('а'),integer('д')).ConvertAll(i->char(i)));
  var val := new string(ArrRandom(5, integer('а'),integer('д')).ConvertAll(i->char(i)));
  
  // проверка результатов
  s.IndicesOf0(val, true).Sum.Println;
  s.IndicesOf1(val, true).Sum.Println;
//  s.IndicesOf2(val, true).Println;
  
  // проверка скорости
  var sw0 := new System.Diagnostics.Stopwatch;
  var sw1 := new System.Diagnostics.Stopwatch;
  var sw2 := new System.Diagnostics.Stopwatch;
  
  for var i := 1 to lc1 do
  begin
    
    sw0.Start;
    loop lc2 do foreach var res in s.IndicesOf0(val, true) do ;
    sw0.Stop;
    
    sw1.Start;
    loop lc2 do foreach var res in s.IndicesOf1(val, true) do ;
    sw1.Stop;
    
//    sw2.Start;
//    loop lc2 do foreach var res in s.IndicesOf2(val, true) do ;
//    sw2.Stop;
    
    System.Console.Title := (i/lc1).ToString('P');
  end;
  
  Writeln(sw0.Elapsed);
  Writeln(sw1.Elapsed);
//  Writeln(sw2.Elapsed);
  
  Readln;
end.

Особенно если результатов много (как при val.Length=1) - у моего варианта преимущество вообще раза в полтора. Ну а при тех значениях что в коде выше - прирост небольшой.

Всё же, должно быть ещё что то что можно улучшить. Но я, почему то, не могу сосредоточится (такой чувство, как умудрился простыть не выходя из дома).


#51

А можно такую же табличку с АСМР, как я приводил?

Ну и толку тогда в последовательности, если результат все равное обычно приходится хранить в массиве?


#52

Не всегда. А когда нужно сохранить в списке - обычно ещё и с промежуточным преобразованием.

Последний пример когда мне на практике нужен был производительный поиск в строке - это когда я парсил .pdf файлы. Там надо было найти все вхождения определённых строк и начинать парсить с этих позиций.

Массив индексов был бы вообще ни к чему:

  1. Как и сказал - преобразование. В результате нужен не индекс, а экземпляр класса, содержащего пропарсенные данные.
  2. Не все результаты нужны. Большинство из них отбрасывалось.
  3. И результат тоже не нужен был в виде массива. Он как поточно парсился - так же поточно записывался в файл.

И объемы информации там были довольно большие, мне пришлось дополнительно упрощать и делать другие части поточными, потому что жрало слишком много оперативки.

Даже если бы я знал как - зачем? Результаты которые выдаёт тот сайт - не понятно откуда взяты. Для каких строк, как собранных, какой длины.

Я привёл тест, использующий StopWatch с его аппаратной поддержкой замеров времени. А так же возможностью видеть как создаются строки и удобно менять любые параметры.


#53

Иными словами, массив “ни к чему” в некоторых частных случаях. А поиск только одного первого вхождения - он лучше и быстрее работает с регуляркой.

Тем не менее, они есть. И, как ни странно, они улучшаются, если решение оптимизируешь - это проверено на 100%. Тесты там злобные, некоторые такие, что и в страшном сне не приснятся. Я бы так сказал - экстремальные. И поэтому результат прогона программы там - это тоже показатель, как бы Вам не хотелось считать иначе.


#54

А в каких применениях на практике нужен массив?

Регулярки? Быстрее? Это где такое видано?

Если б не улучшались - этот сайт вообще ничего не стоил бы. Но - представьте себе, со стопвочем тоже улучшается.

А суровость тестов может показать работоспособность алгоритма. Она не может адекватно применяться к проверкам производительности. Для проверок производительности надо вообще не одно число, а таблица значений, в зависимости от входных данных.

И вот мой тест позволяет построить такую таблицу. А тест приведённого вами сайта - нет.


#55

Ну, ждём таблицу с тестами )) Я тоже считаю, что тесты должны быть не только с acmp


#56

А, ну, я не имел в виду прям настоящую таблицу составлять, я говорил про сравнение в уме результатов с разными входными данными… Но, почему бы и нет:

program prog;

{$region RAlex 0}

function PrefixFunction0(s: string): array of integer;
// возвращает массив граней для строки-аргумента
begin
  var n := s.Length;
  Result := ArrFill(n + 1, 0);
  for var i := 1 to n - 1 do
  begin
    var temp := Result[i];
    while (temp > 0) and (s[i + 1] <> s[temp + 1]) do
      temp := Result[temp];
    Result[i + 1] := s[i + 1] = s[temp + 1] ? temp + 1 : 0
  end
end;

/// Возвращает массив индексов вхождений подстроки в основную строку 
///Параметр overlay определяет, разрешены ли перекрытия вхождений подстрок
function IndicesOf0(Self, SubS: string; overlay: boolean := False): array of integer; extensionmethod;
// Реализует КМП-алгоритм.
// Возвращает массив начальных позиций вхождений подстроки P в строку
// Параметр overlay определяет, разрешены ли перекрытия положений подстрок.
begin
  var L := new List<integer>;
  var (n, m) := (Self.Length, SubS.Length);
  var border := PrefixFunction0(SubS);
  var temp := 0;
  for var i := 1 to n do
  begin
    while (temp > 0) and (SubS[temp + 1] <> Self[i]) do
      temp := border[temp];
    if SubS[temp + 1] = Self[i] then
      temp += 1;
    if temp = m then
    begin
      var pos := i - m + 1;
      if overlay or (L.Count = 0) or (pos >= L[L.Count - 1] + m) then 
        L.Add(pos);
      temp := border[m]
    end;
  end;
  Result := L.Select(i -> i - 1).ToArray
end;

{$endregion RAlex 0}

{$region Sun Serega 1}

///Возвращает массив индексов вхождений подстроки в основную строку
///Использует алгоритм КМП
///Параметр allow_overlap определяет, разрешены ли перекрытия вхождений подстрок
function IndicesOf1(self, value: string; allow_overlap: boolean): List<integer>; extensionmethod;
begin
  
  {$region prefix inds}
  
  var val_inds := new integer[value.Length];
  // val_inds[0] никогда не заполняется и остаётся нулём
  // Примеры заполнения:
  
  // value   : abcab
  // знач. i : 01234
  // val_inds:  0012
  
  // value   : aabaabaaa
  // знач. i : 012345678
  // val_inds:  10123452
  
  var prev_val_ind := 0;
  for var i := 1 to value.Length-1 do
  begin
    
    while true do
    begin
      if value[prev_val_ind + 1] = value[i + 1] then
      begin
        prev_val_ind += 1;
        break;
      end;
      if prev_val_ind=0 then break;
      prev_val_ind := val_inds[prev_val_ind-1];
    end;
    
    val_inds[i] := prev_val_ind;
  end;
  
  {$endregion prefix inds}
  
  {$region Result}
  
  prev_val_ind := 0;
  var res_l := value.Length;
  
  var res := new List<integer>;
  for var i := 1 to self.Length do
  begin
    
    while true do
    begin
      if value[prev_val_ind + 1] = self[i] then
      begin
        prev_val_ind += 1;
        
        if prev_val_ind=res_l then
        begin
          res += i-res_l;
          prev_val_ind := allow_overlap ? val_inds[prev_val_ind-1] : 0;
        end;
        
        break;
      end;
      if prev_val_ind=0 then break;
      prev_val_ind := val_inds[prev_val_ind-1];
    end;
    
  end;
  
  Result := res;
  {$endregion Result}
  
end;

{$endregion Sun Serega 1}

procedure Otp(name: object; params ress: array of object);
begin
  name.ToString.PadRight(2).Print;
  foreach var res in ress do
    res.ToString.PadRight(20).Print;
  Println;
end;

begin
  var lc1 := 100;
  var lc2 := 10;
  
  Randomize(0);
  var s := new string(ArrRandom(100000, integer('а'),integer('д')).ConvertAll(i->char(i)));
  
  Otp('','RAlex','','Sun Serega','');
  Otp('аа','Да','Нет','Да','Нет');
  for var l := 1 to 20 do
  begin
    var val1 := new string(ArrFill(l, 'а')); // строка из одинаковых символов
    var val2 := new string(ArrGen(l, i->char(integer('а')+i))); // строка из всех разных символов
    
    var sw01 := new System.Diagnostics.Stopwatch;
    var sw02 := new System.Diagnostics.Stopwatch;
    var sw11 := new System.Diagnostics.Stopwatch;
    var sw12 := new System.Diagnostics.Stopwatch;
    
    for var i := 1 to lc1 do
    begin
      
      sw01.Start;
      loop lc2 do foreach var res in s.IndicesOf0(val1, true) do ;
      sw01.Stop;
      
      sw02.Start;
      loop lc2 do foreach var res in s.IndicesOf0(val2, true) do ;
      sw02.Stop;
      
      sw11.Start;
      loop lc2 do foreach var res in s.IndicesOf1(val1, true) do ;
      sw11.Stop;
      
      sw12.Start;
      loop lc2 do foreach var res in s.IndicesOf1(val2, true) do ;
      sw12.Stop;
      
      System.Console.Title := (i/lc1).ToString('P');
    end;
    
    Otp(l, sw01.Elapsed,sw02.Elapsed, sw11.Elapsed,sw12.Elapsed);
  end;
  
  Readln;
end.

Ничего кроме разделения поисковой строки по длине и повторению символов - не придумал. Но, если что, добавить ещё что-нибудь - легко.

Ну и время каждого теста сократил в 10 раз, раз их теперь 20. И ещё подправил пару мелочей в своём коде.

Вот результаты у меня:

   RAlex                                     Sun Serega
аа Да                   Нет                  Да                   Нет
1  00:00:01.9446194     00:00:01.8666370     00:00:01.0706198     00:00:01.0684475
2  00:00:01.0356399     00:00:01.0638883     00:00:00.6895404     00:00:00.7234651
3  00:00:00.8871421     00:00:00.9394501     00:00:00.6257238     00:00:00.6759779
4  00:00:00.8581729     00:00:00.9057806     00:00:00.6200921     00:00:00.6624243
5  00:00:00.8516302     00:00:00.8926988     00:00:00.6143702     00:00:00.6578825
6  00:00:00.8460627     00:00:00.8903962     00:00:00.6194775     00:00:00.6574362
7  00:00:00.8390505     00:00:00.8908841     00:00:00.6246286     00:00:00.6629505
8  00:00:00.8427880     00:00:00.8923011     00:00:00.6333484     00:00:00.6649371
9  00:00:00.8387939     00:00:00.8956879     00:00:00.6199796     00:00:00.6633562
10 00:00:00.8360664     00:00:00.8886074     00:00:00.6225067     00:00:00.6690005
11 00:00:00.8393986     00:00:00.8895964     00:00:00.6239060     00:00:00.6649108
12 00:00:00.8374107     00:00:00.8884744     00:00:00.6212659     00:00:00.6676432
13 00:00:00.8506487     00:00:00.8957254     00:00:00.6207370     00:00:00.6694316
14 00:00:00.8369340     00:00:00.8871961     00:00:00.6217399     00:00:00.6720364
15 00:00:00.8399927     00:00:00.8890604     00:00:00.6241068     00:00:00.6643618
16 00:00:00.8368528     00:00:00.8871635     00:00:00.6233056     00:00:00.6715905
17 00:00:00.8427014     00:00:00.8894616     00:00:00.6192097     00:00:00.6635785
18 00:00:00.8406117     00:00:00.8884087     00:00:00.6261769     00:00:00.6749089
19 00:00:00.8408545     00:00:00.8889903     00:00:00.6174124     00:00:00.6663618
20 00:00:00.8375089     00:00:00.8912862     00:00:00.6175829     00:00:00.6629983

Похоже, считать индекс результата когда результат найден - значительно лучше чем res_ind += 1 на каждой итерации))


#57

Однако, по моему у меня где то ошибка. Первые 2 результата:

   RAlex                                     
аа Да                   Нет                 
1  00:00:01.9446194     00:00:01.8666370    

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

P.S. Возможно, дело в JIT-компиляции. Сейчас попробую исправив это…

P.P.S. Нет, даже с этим в начале, перед тестами:

  foreach var res in s.IndicesOf0('ааа',true) do ;
  foreach var res in s.IndicesOf0('абв',true) do ;
  foreach var res in s.IndicesOf1('ааа',true) do ;
  foreach var res in s.IndicesOf1('абв',true) do ;

Тесты с val1 оказываются значительно медленнее тестов с val2, при том что val1=val2 на первой итерации.


#58

В общем, добавил это в цикл - теперь этот эффект менее заметен.
Ну и это всё равно влияет только на первую строчку:

program prog;

{$region RAlex 0}

function PrefixFunction0(s: string): array of integer;
// возвращает массив граней для строки-аргумента
begin
  var n := s.Length;
  Result := ArrFill(n + 1, 0);
  for var i := 1 to n - 1 do
  begin
    var temp := Result[i];
    while (temp > 0) and (s[i + 1] <> s[temp + 1]) do
      temp := Result[temp];
    Result[i + 1] := s[i + 1] = s[temp + 1] ? temp + 1 : 0
  end
end;

/// Возвращает массив индексов вхождений подстроки в основную строку 
///Параметр overlay определяет, разрешены ли перекрытия вхождений подстрок
function IndicesOf0(Self, SubS: string; overlay: boolean := False): array of integer; extensionmethod;
// Реализует КМП-алгоритм.
// Возвращает массив начальных позиций вхождений подстроки P в строку
// Параметр overlay определяет, разрешены ли перекрытия положений подстрок.
begin
  var L := new List<integer>;
  var (n, m) := (Self.Length, SubS.Length);
  var border := PrefixFunction0(SubS);
  var temp := 0;
  for var i := 1 to n do
  begin
    while (temp > 0) and (SubS[temp + 1] <> Self[i]) do
      temp := border[temp];
    if SubS[temp + 1] = Self[i] then
      temp += 1;
    if temp = m then
    begin
      var pos := i - m + 1;
      if overlay or (L.Count = 0) or (pos >= L[L.Count - 1] + m) then 
        L.Add(pos);
      temp := border[m]
    end;
  end;
  Result := L.Select(i -> i - 1).ToArray
end;

{$endregion RAlex 0}

{$region Sun Serega 1}

///Возвращает массив индексов вхождений подстроки в основную строку
///Использует алгоритм КМП
///Параметр allow_overlap определяет, разрешены ли перекрытия вхождений подстрок
function IndicesOf1(self, value: string; allow_overlap: boolean): List<integer>; extensionmethod;
begin
  
  {$region prefix inds}
  
  var val_inds := new integer[value.Length];
  // val_inds[0] никогда не заполняется и остаётся нулём
  // Примеры заполнения:
  
  // value   : abcab
  // знач. i : 01234
  // val_inds:  0012
  
  // value   : aabaabaaa
  // знач. i : 012345678
  // val_inds:  10123452
  
  var prev_val_ind := 0;
  for var i := 1 to value.Length-1 do
  begin
    
    while true do
    begin
      if value[prev_val_ind + 1] = value[i + 1] then
      begin
        prev_val_ind += 1;
        break;
      end;
      if prev_val_ind=0 then break;
      prev_val_ind := val_inds[prev_val_ind-1];
    end;
    
    val_inds[i] := prev_val_ind;
  end;
  
  {$endregion prefix inds}
  
  {$region Result}
  
  prev_val_ind := 0;
  var res_l := value.Length;
  
  var res := new List<integer>;
  for var i := 1 to self.Length do
  begin
    
    while true do
    begin
      if value[prev_val_ind + 1] = self[i] then
      begin
        prev_val_ind += 1;
        
        if prev_val_ind=res_l then
        begin
          res += i-res_l;
          prev_val_ind := allow_overlap ? val_inds[prev_val_ind-1] : 0;
        end;
        
        break;
      end;
      if prev_val_ind=0 then break;
      prev_val_ind := val_inds[prev_val_ind-1];
    end;
    
  end;
  
  Result := res;
  {$endregion Result}
  
end;

{$endregion Sun Serega 1}

procedure Otp(name: object; params ress: array of object);
begin
  name.ToString.PadRight(2).Print;
  foreach var res in ress do
    res.ToString.PadRight(20).Print;
  Println;
end;

begin
  var lc1 := 100;
  var lc2 := 10;
  
  Randomize(0);
  var s := new string(ArrRandom(100000, integer('а'),integer('д')).ConvertAll(i->char(i)));
  
  Otp('','RAlex','','Sun Serega','');
  Otp('аа','Да','Нет','Да','Нет');
  for var l := 1 to 20 do
  begin
    var val1 := new string(ArrFill(l, 'а')); // строка из одинаковых символов
    var val2 := new string(ArrGen(l, i->char(integer('а')+i))); // строка из всех разных символов
    
    foreach var res in s.IndicesOf0(val1,true) do ;
    foreach var res in s.IndicesOf0(val2,true) do ;
    foreach var res in s.IndicesOf1(val1,true) do ;
    foreach var res in s.IndicesOf1(val2,true) do ;
    
    var sw01 := new System.Diagnostics.Stopwatch;
    var sw02 := new System.Diagnostics.Stopwatch;
    var sw11 := new System.Diagnostics.Stopwatch;
    var sw12 := new System.Diagnostics.Stopwatch;
    
    for var i := 1 to lc1 do
    begin
      
      sw01.Start;
      loop lc2 do foreach var res in s.IndicesOf0(val1, true) do ;
      sw01.Stop;
      
      sw02.Start;
      loop lc2 do foreach var res in s.IndicesOf0(val2, true) do ;
      sw02.Stop;
      
      sw11.Start;
      loop lc2 do foreach var res in s.IndicesOf1(val1, true) do ;
      sw11.Stop;
      
      sw12.Start;
      loop lc2 do foreach var res in s.IndicesOf1(val2, true) do ;
      sw12.Stop;
      
      System.Console.Title := (i/lc1).ToString('P');
    end;
    
    Otp(l, sw01.Elapsed,sw02.Elapsed, sw11.Elapsed,sw12.Elapsed);
  end;
  
  Readln;
end.
   RAlex                                     Sun Serega
аа Да                   Нет                  Да                   Нет
1  00:00:02.1613328     00:00:02.1226676     00:00:01.2343959     00:00:01.2539556
2  00:00:01.1056546     00:00:01.1317227     00:00:00.7495506     00:00:00.7937824
3  00:00:00.9389310     00:00:01.0996203     00:00:00.6746335     00:00:00.7479461
4  00:00:00.9698502     00:00:00.9317670     00:00:00.6657472     00:00:00.7220512
5  00:00:00.8824940     00:00:01.0151487     00:00:00.6589880     00:00:00.7082633
6  00:00:00.8835938     00:00:01.0484990     00:00:00.6887829     00:00:00.7360015
7  00:00:00.8897178     00:00:00.9752191     00:00:00.7362631     00:00:00.7335173
8  00:00:00.9221126     00:00:01.0302711     00:00:00.7273062     00:00:00.7653563
9  00:00:00.8952018     00:00:00.9611237     00:00:00.6610599     00:00:00.7861346
10 00:00:00.9805772     00:00:00.9629134     00:00:00.6575169     00:00:00.7166497
11 00:00:00.8648718     00:00:00.9530304     00:00:00.6574951     00:00:00.7063142
12 00:00:00.8405118     00:00:00.8923351     00:00:00.6364620     00:00:00.6900514
13 00:00:00.8277424     00:00:00.8820249     00:00:00.6587564     00:00:00.6810963
14 00:00:00.8347925     00:00:00.8828806     00:00:00.6300331     00:00:00.6767473
15 00:00:00.8529276     00:00:00.9066059     00:00:00.6505163     00:00:00.6831164
16 00:00:00.8747458     00:00:00.9555723     00:00:00.6497714     00:00:00.7148019
17 00:00:00.8648588     00:00:00.8949987     00:00:00.6362897     00:00:00.6815480
18 00:00:00.9075164     00:00:00.9575830     00:00:00.6498875     00:00:00.7739918
19 00:00:00.9624533     00:00:00.9265848     00:00:00.6731339     00:00:00.7078776
20 00:00:00.9940469     00:00:00.9388618     00:00:00.6454581     00:00:00.7195870

Кстати, сравнивать имеет смысл только значения справа и слева друг от друга, потому что они тестировались одновременно.
Как можете видеть - в некоторых строчках времени тратиться неожиданно дольше предыдущих - это значит что у меня комп был ещё чем то занят в этот момент.

Но что можно сравнивать - так это, к примеру, то что с увеличением длины искомой строки становиться важнее, одинаковые ли в ней символы.


#59

Но и оттуда тоже - нельзя их не учитывать. Там тесты на огромных строках, возможно, каких-то вычурных даже, но это олимпиадные тесты и не надо их игнорировать: они сделаны специально, чтобы максимально загнать в тупик программу, т.е. это все же критерии стрессоустойчивости. Вы сами знаете, чего стоит отдельные задания там загнать в рамки.

Это видано и не раз. Первое вхождение искать всегда быстрее, чем все. Проверял и я, и @Admin, когда только обсуждалось, делать ли IndexOf вообще, и если делать, то как.

Например, когда надо обработать не все вхождения, а проанализировать отдельные.

А это-то тут причем? Речь не об изменении средств контроля время выполнении, а об изменении в реализации алгоритма.


#60

Вот только вы сами сказали, в расчёт времени берётся и запуск программы, и JIT-компиляция. Это - не относится к алгоритму. И, что важнее - это не стабильные результаты.

Да, разумеется. Но .IndexOf это не регулярки и даже не КМП. Это обычный поиск подстроки перебором всех позиций.

А регулярки это вот:

begin
  (new Regex('***')).Match(ReadString).Index
end.

И они никогда не могут быть даже сравнимыми по скорости с .IndexOf, потому что алгоритм на много сложнее.

А зачем для этого массив? Даже если сравнивать рядом стоящие индексы - это что то типа .Pariwise . Так а для какого типа анализа надо прям все индексы одновременно в памяти держать?

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


#61

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

Это была описка, мы проверяли IndicesOf.

Не обязательно все. Например, если надо сделать в строке замену не каждого вхождения. А только такого, которое идет после/перед каким-либо контекстом. Либо, обработать вхождения кроме первого. Или кроме первого и последнего. И т.п. Задачи самые разные бывают.


#62

Ну так а если не все - массив не нужен.

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