Многократное удаление символов из строки, а также элементов элементов из массива Опции

[TarasBer]

Часто встречается такая задача: дана строка S, удалить из неё все символы, равные данному символу c. Первое, что приходит на ум - это воспользоваться стандратной функцией Delete:

for i := 1 to Length(S) do 
  if S[i] = c then
    Delete(S, i, 1);

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

Если идти с конца, то мы получим уже как бы рабочий код:

for i := Length(S) downto 1 do 
  if S[i] = c then
    Delete(S, i, 1);

Тем не менее, такой код для разбора больших текстовых документов (100КБ и больше) не годится по причине алгоритмической сложности, приводящей к существенным потерям времени. Дело в том, что Delete - это не мгновенная операция. При удалении символа надо сдвинуть весь остаток строки на одну позицию, то есть Delete работает за O(n). И тогда весь алгоритм работает за O(m*n), где m- количество удаляемых символов в тексте. Оно, как правило, тоже пропорционально длине текста.

Но существует алгоритм получше. Пусть перед нами поставили такую задачу: дана строка S1, получить строку S2, которая отличается от первой только отсутствием символа c. Наличие второй строки двигает мысль в другую сторону, в голове появляется алгоритм последовательного построения второй строки с нуля путём добавления в неё всех "хороших" символов из первой строки:

S2 := '';
for i := 1 to Length(S1) do
  if S1[i] <> c then 
    S2 := S2 + S1[i];

Уже лучше! Добавление символа в конец строки не влечет за собой сдвига хвоста, как вставка/удаление символа в середине. А если переписать эту же процедуру для массива произвольного типа? Тогда нам придётся отказаться от оператора + (или перезагрузить его). Также, придётся хранить длину в отдельной переменной.

j := Low(S2); // минимальный индекс для S2 
for i := Low(S1) to LS1 do // до максимального индекса в S1, он храниться в отдельной переменной и не равен High(S1)
  if Good(S1[i]) then begin // если i-тый элемент массива S1 хороший, вместо Good может быть написана явная проверка
    S2[j] := S1[i];   // записываем новый элемент в массив S2
    Inc(j); // увеличиваем номер места для нового элемента
  end;
LS2 := j - 1; // устанавливаем номер максимального элемента для S2

Такой код уже работает за один проход массива, выполняя всю работу за положенное время O(n).
А теперь посмотрим внимательно на этот код и зададимся вопросом: а что нам мешает вместо S2 написать S1? Что нам мешает строить новый массив прямо на месте старого? Ведь запись может только отставать от текущего проверяемого элемента, но не опережать его - следовательно, она не портит непроверенные элементы. Тогда получается, что ничего не мешает написать так:

j := Low(S); 
for i := Low(S) to LS do
  if Good(S[i]) then begin 
    S[j] := S[i];  
    Inc(j);
  end;
LS := j-1;

Это для статического массива, у которого номер последнего используемого элемента хранится в отдельной переменной.
Для строк код будет такой:

j := 1; 
for i := 1 to Length(S) do
  if Good(S[i]) then begin 
    S[j] := S[i];  
    Inc(j);
  end;
SetLength(S, j - 1);

Для динамических массивов - такой:

j := 0; 
for i := 0 to Length(A) - 1 do
  if Good(A[i]) then begin 
    A[j] := A[i];  
    Inc(j);
  end;
SetLength(A, j);

Осталось заметить, что на (обычном) тексте в 440 кб удаление пробелов отработало:
- наивный код: за 15 секунд,
- обсужденный в этой статье алгоритм: меньше 10 миллисекунд.

Сообщение отредактировано: TarasBer - 6.11.2010 13:37