Обсуждение "Многократного удаления из строки", Разделено Опции

[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 привести, или сам найдешь? Поверь, мгновенной телепортации всего блока с места на место там точно нет - обычный цикл (хотя нет, не обычный, а очень замороченный).

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

[TarasBer]

> А move - уже не в счет? Хотя, видимо, тоже долго работает...

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

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

Я видел реализацию через возможность сопроцессора загружать и выгружать по 8 байт.

[Lapp]

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

Мне кажется, установление всяких специальных правил на этот счет излишне. Ведь никто же не ограничивает - если кто-то хочет сначала обсудить, он откроет тему и обсудит. Или тема сначала не предназначается для FAQ, но дозревает до этого. Бывают случаи, когда обсуждать особо нечего, и тема сразу готова для FAQ (как в нынешнем). Но это не значит, что это нельзя - пожалуйста, создаете тему в подходящем разделе и вперед.. Кто мешает? Конечно, отвечать/спрашивать ПРЯМО в FAQ - это неправильно и приводит к тому, что админ должен переносить. Но это же вопрос грамотности наших пользователей, и не более того. Совершенно не секрет, что даже постоянные пользователи Форума не знают его Правил, а также часто плюют на правила разделов. И это - объективная оценка ситуации. Так оно было, есть и будет, и тут ничего поделать нельзя. И если мы даже введем специальную процедуру для наполнения FAQ, это будет всего лишь еще одно правило, которое будет нарушатся ничем не хуже остальных, я готов спорить. И на фига оно нам тогда? и так уже у меня крыша едет от нарушений - как новичками, так и старичками.

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

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

[Lapp]

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

Client, а с каких пор для оценки времени выполнения нужны исходники? простое профилирование или даже обычный замер исполнения в цикле - не катят? То есть, я понимаю, что там будут ошибки, но эти "ошибки" вполне реальны и их тоже следует учитывать..

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

[Client]

Проясняю ситуацию...
я как бы "за" move тут выступил. НО! я не знаю (точнее не знал) как она работает и которая как раз используется в процедуре Delete. Вот

какую-никакую оценку.

Я не говорю что тема с ошибками или еще что-то. У меня же нету этого самого теста, чтобы сравнить с move. И результаты сравнения я видел.

Конечно, отвечать/спрашивать ПРЯМО в FAQ - это неправильно и приводит к тому, что админ должен переносить

Все ответы в FAQ проходят проверку, я это знал и ответил туда, т.к. посчитал это наилучшим вариантом

[Lapp]

я как бы "за" 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);

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

[TarasBer]

значит, надо так:
LS := j - 1;

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

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

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

Исправил этот нюанс в статье.

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

[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.