Форум «Всё о Паскале» _ Задачи _ Обсуждение "Многократного удаления из строки"
Автор: Client 5.11.2010 13:21
[вставка] Я (Lapp) вклинился сюда, чтоб привести ссылку на ту тему в FAQ, о которой идет речь: http://forum.pascal.net.ru/index.php?showtopic=26642 [конец вставки]
Цитата
Дело в том, что Delete - это не мгновенная операция
Эм... я вот не нашел исходник этой процедуры и не знаю насколько она "не мгновенная". А move - уже не в счет? Хотя, видимо, тоже долго работает...
Автор: volvo 5.11.2010 17:59
Цитата
я вот не нашел исходник этой процедуры и не знаю насколько она "не мгновенная"
Не нашел, говоришь? Ну, вот реализация 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 5.11.2010 19:17
> А move - уже не в счет? Хотя, видимо, тоже долго работает...
Пропускная способность памяти очень ограничена, поэтому копирование блока, особенно, когда его размер выходит за 100 килобайт, занимает некоторое время, пропорциональное длине блока.
> , а сам Move - еще краше:
Я видел реализацию через возможность сопроцессора загружать и выгружать по 8 байт.
Автор: Lapp 6.11.2010 6:05
Цитата(volvo @ 5.11.2010 13:59)
P.S. Давайте все-таки не постить темы сразу в FAQ, а для начала выкладывать в общем разделе, с пометкой "Материал для FAQ", чтобы все могли принять участие в обсуждении/дополнении материала, а потом уже, когда автор решит, что больше корректировать ничего не надо, тема разделится, и уйдет в FAQ, а обсуждение останется в общем разделе (ну, или будет удалено).
Мне кажется, установление всяких специальных правил на этот счет излишне. Ведь никто же не ограничивает - если кто-то хочет сначала обсудить, он откроет тему и обсудит. Или тема сначала не предназначается для FAQ, но дозревает до этого. Бывают случаи, когда обсуждать особо нечего, и тема сразу готова для FAQ (как в нынешнем). Но это не значит, что это нельзя - пожалуйста, создаете тему в подходящем разделе и вперед.. Кто мешает? Конечно, отвечать/спрашивать ПРЯМО в FAQ - это неправильно и приводит к тому, что админ должен переносить. Но это же вопрос грамотности наших пользователей, и не более того. Совершенно не секрет, что даже постоянные пользователи Форума не знают его Правил, а также часто плюют на правила разделов. И это - объективная оценка ситуации. Так оно было, есть и будет, и тут ничего поделать нельзя. И если мы даже введем специальную процедуру для наполнения FAQ, это будет всего лишь еще одно правило, которое будет нарушатся ничем не хуже остальных, я готов спорить. И на фига оно нам тогда? и так уже у меня крыша едет от нарушений - как новичками, так и старичками.
А, с другой стороны, процесс наполнения FAQ нужно поддерживать. Любая заорганизованность будет препятствием. Если бы у нас статьи в FAQ сыпались бы одна за другой, как из рога изобилия - я был бы ЗА. А так - мой голос ПРОТИВ.
К тому же, вопросы по содержимому FAQ могут возникать на любом этапе, даже к старой статье. Так что определить, когда тема "созрела" не всегда возможно. И если возникла ситуация как сегодня - ну, ничего страшного, мне кажется..
Автор: Lapp 6.11.2010 7:20
Цитата(Client @ 5.11.2010 9:21)
Эм... я вот не нашел исходник этой процедуры и не знаю насколько она "не мгновенная". А move - уже не в счет? Хотя, видимо, тоже долго работает...
Client, а с каких пор для оценки времени выполнения нужны исходники? простое профилирование или даже обычный замер исполнения в цикле - не катят? То есть, я понимаю, что там будут ошибки, но эти "ошибки" вполне реальны и их тоже следует учитывать..
Честно, меня немного удивляет, когда человек лезет в дебри, не попытавшись сделать простую вещь.. Кстати, в конце обсуждаемого сообщения Тарас приводит какую-никакую оценку.
Автор: Client 6.11.2010 15:06
Проясняю ситуацию... я как бы "за" move тут выступил. НО! я не знаю (точнее не знал) как она работает и которая как раз используется в процедуре Delete. Вот
Цитата
какую-никакую оценку.
Я не говорю что тема с ошибками или еще что-то. У меня же нету этого самого теста, чтобы сравнить с move. И результаты сравнения я видел.
Цитата
Конечно, отвечать/спрашивать ПРЯМО в FAQ - это неправильно и приводит к тому, что админ должен переносить
Все ответы в FAQ проходят проверку, я это знал и ответил туда, т.к. посчитал это наилучшим вариантом
Автор: Lapp 6.11.2010 16:14
Цитата(Client @ 6.11.2010 11:06)
я как бы "за" move тут выступил. НО! я не знаю (точнее не знал) как она работает и которая как раз используется в процедуре Delete.
Я согласен, что от этого немало зависит. Но в любом случае приведенный способ лучше (т.е. даже если Delete реализована наилучшим из возможных способов). И - всегда есть возможность настучать пару строк и потестить )).
Цитата
Все ответы в FAQ проходят проверку, я это знал и ответил туда, т.к. посчитал это наилучшим вариантом
Так или иначе, если есть вопросы - лучше все же начать отдельную тему с обсуждением ))
Автор: volvo 6.11.2010 17:07
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;
Казалось бы чего проще, 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 6.11.2010 17:36
значит, надо так: LS := j - 1;
> for i := Low(S) to High(S) do
Для статического массива так не катит. Ведь их заводят с большим запасом, и большая часть статического массива, как правило, не используется.
У меня LS означает номер последнего индекса.
Исправил этот нюанс в статье.
Автор: volvo 6.11.2010 17:42
Цитата
значит, надо так: LS := j - 1;
Значит, индексировать с (-N) - таки нельзя. Ясно. На фиг такой код.
Автор: TarasBer 6.11.2010 17:44
Как нельзя?!
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;