IPB
ЛогинПароль:

> Внимание! Действует предмодерация

Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.

 
 Ответить  Открыть новую тему 
> Многократное удаление символов из строки, а также элементов элементов из массива
сообщение
Сообщение #1


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Часто встречается такая задача: дана строка 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 -


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 19.01.2018 18:21
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"