Помощь - Поиск - Пользователи - Календарь
Полная версия: Обсуждение "Многократного удаления из строки"
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Client
[вставка]
Я (Lapp) вклинился сюда, чтоб привести ссылку на ту тему в FAQ, о которой идет речь:
Многократное удаление символов из строки
[конец вставки]


Цитата
Дело в том, что Delete - это не мгновенная операция
Эм... я вот не нашел исходник этой процедуры и не знаю насколько она "не мгновенная". А move - уже не в счет? Хотя, видимо, тоже долго работает...
volvo
Цитата
я вот не нашел исходник этой процедуры и не знаю насколько она "не мгновенная"
Не нашел, говоришь? Ну, вот реализация Delete из FPC:

procedure delete(var s : shortstring;index : SizeInt;count : SizeInt);
begin
if index<=0 then
exit;
if (Index<=Length(s)) and (Count>0) then
begin
if Count>length(s)-Index then
Count:=length(s)-Index+1;
s[0]:=Chr(length(s)-Count);
if Index<=Length(s) then
Move(s[Index+Count],s[Index],Length(s)-Index+1);
end;
end;
, а сам Move - еще краше:
procedure Move(const source;var dest;count:SizeInt);[public, alias: 'FPC_MOVE'];assembler;nostackframe;
asm
cmp ecx,SMALLMOVESIZE
ja @Large
cmp eax,edx
lea eax,[eax+ecx]
jle @SmallCheck
@SmallForward:
add edx,ecx
jmp SmallForwardMove_3
@SmallCheck:
je @Done {For Compatibility with Delphi's move for Source = Dest}
sub eax,ecx
jmp SmallBackwardMove_3
@Large:
jng @Done {For Compatibility with Delphi's move for Count < 0}
cmp eax,edx
jg @moveforward
je @Done {For Compatibility with Delphi's move for Source = Dest}
push eax
add eax,ecx
cmp eax,edx
pop eax
jg @movebackward
@moveforward:
jmp dword ptr fastmoveproc_forward
@movebackward:
jmp dword ptr fastmoveproc_backward {Source/Dest Overlap}
@Done:
end;
Реализацию fastmoveproc_forward и fastmoveproc_backward привести, или сам найдешь? smile.gif Поверь, мгновенной телепортации всего блока с места на место там точно нет - обычный цикл (хотя нет, не обычный, а очень замороченный).

P.S. Давайте все-таки не постить темы сразу в FAQ, а для начала выкладывать в общем разделе, с пометкой "Материал для FAQ", чтобы все могли принять участие в обсуждении/дополнении материала, а потом уже, когда автор решит, что больше корректировать ничего не надо, тема разделится, и уйдет в FAQ, а обсуждение останется в общем разделе (ну, или будет удалено).
TarasBer
> А move - уже не в счет? Хотя, видимо, тоже долго работает...

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

> , а сам Move - еще краше:

Я видел реализацию через возможность сопроцессора загружать и выгружать по 8 байт.
Lapp
Цитата(volvo @ 5.11.2010 13:59) *
P.S. Давайте все-таки не постить темы сразу в FAQ, а для начала выкладывать в общем разделе, с пометкой "Материал для FAQ", чтобы все могли принять участие в обсуждении/дополнении материала, а потом уже, когда автор решит, что больше корректировать ничего не надо, тема разделится, и уйдет в FAQ, а обсуждение останется в общем разделе (ну, или будет удалено).
Мне кажется, установление всяких специальных правил на этот счет излишне. Ведь никто же не ограничивает - если кто-то хочет сначала обсудить, он откроет тему и обсудит. Или тема сначала не предназначается для FAQ, но дозревает до этого. Бывают случаи, когда обсуждать особо нечего, и тема сразу готова для FAQ (как в нынешнем). Но это не значит, что это нельзя - пожалуйста, создаете тему в подходящем разделе и вперед.. Кто мешает? Конечно, отвечать/спрашивать ПРЯМО в FAQ - это неправильно и приводит к тому, что админ должен переносить. Но это же вопрос грамотности наших пользователей, и не более того. Совершенно не секрет, что даже постоянные пользователи Форума не знают его Правил, а также часто плюют на правила разделов. И это - объективная оценка ситуации. Так оно было, есть и будет, и тут ничего поделать нельзя. И если мы даже введем специальную процедуру для наполнения FAQ, это будет всего лишь еще одно правило, которое будет нарушатся ничем не хуже остальных, я готов спорить. И на фига оно нам тогда? и так уже у меня крыша едет от нарушений - как новичками, так и старичками.

А, с другой стороны, процесс наполнения FAQ нужно поддерживать. Любая заорганизованность будет препятствием. Если бы у нас статьи в FAQ сыпались бы одна за другой, как из рога изобилия - я был бы ЗА. А так - мой голос ПРОТИВ.

К тому же, вопросы по содержимому FAQ могут возникать на любом этапе, даже к старой статье. Так что определить, когда тема "созрела" не всегда возможно. И если возникла ситуация как сегодня - ну, ничего страшного, мне кажется..
Lapp
Цитата(Client @ 5.11.2010 9:21) *
Эм... я вот не нашел исходник этой процедуры и не знаю насколько она "не мгновенная". А move - уже не в счет? Хотя, видимо, тоже долго работает...
Client, а с каких пор для оценки времени выполнения нужны исходники? простое профилирование или даже обычный замер исполнения в цикле - не катят? То есть, я понимаю, что там будут ошибки, но эти "ошибки" вполне реальны и их тоже следует учитывать..

Честно, меня немного удивляет, когда человек лезет в дебри, не попытавшись сделать простую вещь.. Кстати, в конце обсуждаемого сообщения Тарас приводит какую-никакую оценку.
Client
Проясняю ситуацию...
я как бы "за" move тут выступил. НО! я не знаю (точнее не знал) как она работает и которая как раз используется в процедуре Delete. Вот smile.gif
Цитата
какую-никакую оценку.
Я не говорю что тема с ошибками или еще что-то. У меня же нету этого самого теста, чтобы сравнить с move. И результаты сравнения я видел.
Цитата
Конечно, отвечать/спрашивать ПРЯМО в FAQ - это неправильно и приводит к тому, что админ должен переносить
Все ответы в FAQ проходят проверку, я это знал и ответил туда, т.к. посчитал это наилучшим вариантом
Lapp
Цитата(Client @ 6.11.2010 11:06) *
я как бы "за" move тут выступил. НО! я не знаю (точнее не знал) как она работает и которая как раз используется в процедуре Delete.
Я согласен, что от этого немало зависит. Но в любом случае приведенный способ лучше (т.е. даже если Delete реализована наилучшим из возможных способов). И - всегда есть возможность настучать пару строк и потестить )).

Цитата
Все ответы в FAQ проходят проверку, я это знал и ответил туда, т.к. посчитал это наилучшим вариантом
Так или иначе, если есть вопросы - лучше все же начать отдельную тему с обсуждением ))
volvo
TarasBer, насколько я вижу,
Цитата
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;

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

может привести к неправильному результату:

procedure print_arr(const arr: array of integer; n: integer);
var i: integer;
begin
write('<', n:2, '> ');
for i := 0 to pred(n) do write(arr[i]:3);
writeln;
end;

const
size = 10;

var
arr: array[1 .. size] of integer;
real_size: integer;

i, j: integer;
b: boolean;

begin
real_size := size;
for i := 1 to size do
begin
arr[i] := i mod 2;
end;

print_arr(arr, real_size);

j := Low(arr);
for i := Low(arr) to real_size do
if arr[i] <> 0 then { Good(X) => (X <> 0) }
begin
arr[j] := arr[i];
Inc(j);
end;
real_size := j;

print_arr(arr, real_size);
end.




Running "f:\programs\pascal\tst_fq.exe "
<10> 1 0 1 0 1 0 1 0 1 0
< 6> 1 1 1 1 1 0



Казалось бы чего проще, LS := j - Low(S)? Но только это не решит проблемы. Массивы могут индексироваться не только с 1, 2, и так далее. А и с 0, и с (-1). А при первом отрицательном индексе (при цикле до LS) будет Range-Check Error. Я бы предложил:
j := Low(S); 
for i := Low(S) to High(S) do
if Good(S[i]) then begin
S[j] := S[i];
Inc(j);
end;
LS := j - Low(S);
TarasBer
значит, надо так:
LS := j - 1;

> for i := Low(S) to High(S) do

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

У меня LS означает номер последнего индекса.

Исправил этот нюанс в статье.
volvo
Цитата
значит, надо так:
LS := j - 1;
Значит, индексировать с (-N) - таки нельзя. Ясно. На фиг такой код.
TarasBer
Как нельзя?!


procedure print_arr(const arr: array of integer; n: integer);
var i: integer;
begin
write('<', n:2, '> ');
for i := 0 to pred(n) do write(arr[i]:3);
writeln;
end;

const
size = 10;
s = -56;

var
arr: array[s .. s+size-1] of integer;
real_size: integer;

i, j: integer;
b: boolean;

begin
randomize;

real_size := size+s-1;
for i := s to real_size do
begin
arr[i] := random(3);
end;

print_arr(arr, real_size-s+1);

j := Low(arr);
for i := Low(arr) to real_size do
if arr[i] <> 0 then { Good(X) => (X <> 0) }
begin
arr[j] := arr[i];
Inc(j);
end;
real_size := j - 1;

print_arr(arr, real_size-s+1);
end.

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.