Почему итератор downto менее предпочтителен чем while при итерации по модифицируемой строке?

Question

Недавно встретился вот такой код с фильтрацией строки:

s := 'Some text 123 and more text.';
for I := 1 to length(s) do
  if not (s[i] in ['0'..'9','.']) then
    Delete(s, i, 1);

В комментариях справедливо замечено:

Кроме того, нельзя итерироваться по строке и в то же время модифицировать её. В крайнем случае можно использовать downto для итерации с конца строки, но лучше заменить for цикл на while.

Почему нельзя итерироваться по строке и в то же время модифицировать её - очевидно. Однако почему downto тоже считается чем-то "крайним" и менее предпочтительным, чем while? Всегда казалось, что downto это простой валидный способ итерации. В идеале, хотелось бы увидеть конкретный пример когда downto приводит к ошибкам, а while отрабатывает корректно.

Answer 1

Никакой основательной причины выбирать while в данном случае нету. Данный вариант совершенно безопасен:

s := 'Some text 123 and more text.';
for I := length(s) downto 1 do
  if not (s[i] in ['0'..'9','.']) then
    Delete(s, i, 1);

Использование while следует предпочесть, если удаление идет не с текущей позиции.

Answer 2

Применительно к Pascal

разница заключается в невозможности изменить счетчик внутри цикла for.

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

В данном случае проблема решается проходом с конца коллекции.

Однако, в случае если следующее значение счетчика определяется каким-то алгоритмом - цикл for можно будет применить, только если заранее известно количество шагов

Answer 3

Оба подхода рабочие, downto даёт несколько более быстрый код.

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

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

var
  t: DWord;
  i, j, n: Integer;
  s: string;
begin
  n := 1000000;

  s := '';
  for i := 1 to n do
    s := s + 'ab1';
  t := GetTickCount;
  for i :=  length(s) downto 1 do
      if s[i] in ['0'..'9'] then
          Delete(s, i, 1);
  Memo1.Lines.Add(Format('downto %d',[GetTickCount - t]));

  s := '';
  for i := 1 to n do
    s := s + 'ab1';
  t := GetTickCount;
  i := 1;
  while i <= length(s) do begin
      if s[i] in ['0'..'9'] then
          Delete(s, i, 1)
      else
          inc(i);
  end;
  Memo1.Lines.Add(Format('while %d',[GetTickCount - t]));

  s := '';
  for i := 1 to n do
    s := s + 'ab1';
  t := GetTickCount;
  j := 0;
  for i := 1 to Length(s) do
      if s[i] in ['0'..'9'] then
         Inc(j)
      else
         s[i-j] := s[i];
  SetLength(s, Length(s) - j);
  Memo1.Lines.Add(Format('inplace %d',[GetTickCount - t]));

Результаты

n = 100 000    
downto 656
while 1012
inplace 0

n = 1 000 000
downto 76391
while 115610
inplace 16

БЛОГ НА HUSL

Почему итератор downto менее предпочтителен чем while при итерации по модифицируемой строке?

Ответы (3 шт):