Искать здесь

в заметках в файлах в ссылках

Повышение эффективности циклов в алгоритме сжатия массива.

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

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

For I:= 0 To N Do
If A[I]=3 Then
Begin
For J:= I To N Do
A[I]:= A[I+1];
Dec(N);
End;

Принцип понятен и прост. При элементе, равном 3, запускается новый цикл, сдвигающий следующие за ним элементы ближе к первому элементу. Однако, как и большинство вложенных циклов, вышеприведенный можно оптимизировать. Проведя мелкий анализ можно заметить, что при двух удаляемых элементах, элементы, следовавшие за вторым удаляемым, перемещаются два раза на одну позицию (после третьего удаляемого - три раза, и т.д.). От этого можно избавиться следующим образом.

I:=0;
K:=0;
While I<N Do
Begin
If I<>3 then
A[I-K]:= A[I]
else
Inc(K);
Inc(I);
end;
Dec(N,K);

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