Форум: "Основная";
Текущий архив: 2003.02.10;
Скачать: [xml.tar.bz2];
Вниз
Заменя пробелов Найти похожие ветки
← →
Digitman (2003-01-29 14:51) [40]
> Johnmen
Чего то я тебя не понял)
> После первого же вызова .. строка Srс уже не та,
> что раньше: все слова в Src разделены одним пробелом.
Разумеется ! На то и in-place-алгоритм...
Убирает лишние (ведущие/терминирующие/межсловные) пробелы в указанном блоке памяти со строковыми данными, терминированными #0
> Все последующие итерации цикла просто ничего не делают.
Какие итерации-то ? Вызов уже сделан, Result указывает на тот же блок данных (либо nil, если Src-строка пуста)
← →
Johnmen (2003-01-29 15:57) [41]>Digitman © (29.01.03 14:51)
>> Johnmen
>Чего то я тебя не понял)
Да, не понял ! Имелась в виду процедура тестирования от Юрий Зотов ©.
← →
Digitman (2003-01-29 16:02) [42]а-а-а ... я не обратил внимания ...
а чего вхолостую однократно обработанную уже строку гонять в цикле ? если уж на то пошло, нужно было в цикле по десятку тысяч раз прогнать несколько строк с заранее оговоренным содержимым ...
← →
Johnmen (2003-01-29 16:09) [43]>Digitman © (29.01.03 16:02)
И я про то же ! Тестирование твоего варианта не совсем корректно...
← →
mate (2003-01-29 16:24) [44]Ну ВЫ тут и написали , а надо всего лишь
while pos(" "+" ",s)<>0 do
delete(s,pos(" "+" ",s),1);
и всё ;)
а что касается " "+" " - это что бы было видно что их два
← →
Digitman (2003-01-29 16:36) [45]
> mate
На тему лаконичности исх.текста, решающего задачу - давно уже проехали, сударь)
Здесь уже бой на тему "кто шустрей")
← →
mate (2003-01-29 16:44) [46]ну для шустрости можно мой код в поток загнать и приоритет Haigest у потока.
← →
Digitman (2003-01-29 16:48) [47]
> mate
Чушь ты городишь, сударь.
Доп.код.поток никакой "шустрости" не добавляет алгоритму).. Хоть ты ему SuperHighest-приоритет дажк умудришься установить)
← →
mate (2003-01-29 16:52) [48]этим самым ты хочешь сказать , что время выполнения задачи не зависит от выделяемого процессорного времени? Так?
← →
Андрей Сенченко (2003-01-29 17:00) [49]Специально не вникал чужие варианты :-)) Возможно, это уже было - но я бы делал так :
procedure TForm1.Button1Click(Sender: TObject);
var
s: string;
i: integer;
begin
s := "q wer t y u";
for i := 0 to length(s) do
if s[i] = " " then
while s[i+1] = " " do delete(s,i+1,1);
ShowMessage(s);
end;
Скорее всего Digitman-a не обгоню :-)) , но интесно насколько медленнее.
← →
Андрей Сенченко (2003-01-29 17:02) [50]Ведущие и терминирующие пробелы не рассматривал.
← →
Sectey (2003-01-29 17:04) [51]>mate ©
Во первых твой вариант уже предлогоался.
Во вторых ТВОЯ ФУНКЦИЯ - 23002 > Q_SpaceCompress - 688
Получается в 30 раз медленее самого быстрого
← →
Digitman (2003-01-29 17:06) [52]
> mate
> этим самым ты хочешь сказать , что время выполнения задачи
> не зависит от выделяемого процессорного времени? Так?
зависит ! оч даже зависит) .. и организуя доп.код.поток ты даже меньше квантов получишь на выполнение своего кода, ежели если бы был только один осн.код.поток и в его контексте выполнялся тот же твой код.
А приоритет код.потока относителен и квантование времени, выделяемого код.потоку, расчитывается ядром относительно приоритета процесса в целом
← →
Sectey (2003-01-29 17:08) [53]>Андрей Сенченко ©
Твой алгоритм на 4 месте он дал - 4265
← →
Digitman (2003-01-29 17:14) [54]
> Андрей Сенченко
И не обгонишь)
In-place-алгоритм при всех его видимых недостатках все же в любом случае эффективней будет из-за отсутствия необходимости итеративно перераспределять память с использованием далеко не оптимизированного для таких задач встр.менеджера памяти от Борланда
← →
Johnmen (2003-01-29 17:17) [55]>Sectey © (29.01.03 17:08)
Огласите весь список, пжалуста....
← →
Юрий Зотов (2003-01-29 17:28) [56]> Андрей Сенченко © (29.01.03 17:00)
Дык... у Вас же будет гарантированный выход за пределы строки. Причем даже в двух местах.
← →
Андрей Сенченко (2003-01-29 17:43) [57]Юрий Зотов © (29.01.03 17:28)
В одном вижу - граница цикла должна быть length(s)-1.
А второе ?
← →
Johnmen (2003-01-29 17:46) [58]Юрий, приведите, пожалуйста, последние результаты тестирования быстродействия предложенных алгоритмов...
← →
Mystic (2003-01-29 17:47) [59]Еще один вариант замены строки по месту. ;)
К преимуществам следует отнести тот факт, что поддерживается несколько пробельных и конечных символов.
var
TBL: array[Byte] of Integer;
// Инициализация массива символов, 0 - символы, 1 - разделители, 2 - терминаторы
procedure InitTBL;
var
I: Integer;
begin
for I := 0 to 255 do
TBL[I] := 0;
TBL[32] := 1;
TBL[9] := 1;
TBL[0] := 2;
end;
// Напрямую к соответсвующей функции из System.pas обратиться не удалось
procedure _LStrSetLength(var St: string; Len: Integer);
begin
SetLength(St, Len);
end;
procedure Mystic(var St: string);
asm
PUSH ESI
PUSH EDI
PUSH EAX
CALL UniqueString
POP EDX
MOV ESI, [EDX]
MOV EDI, ESI
XOR EAX, EAX
INC EAX
CLD
DEC ESI //JMP @@Loop;
@@SkipSpace:
INC ESI
@@Loop:
MOV ECX, EAX
MOVZX EAX, [ESI]
MOV EAX, [OFFSET TBL].[4*EAX]
TEST EAX, ECX
JNZ @@SkipSpace
MOVSB
CMP EAX, 1
JLE @@Loop
@@Exit:
SUB EDI, ECX
MOV EAX, EDX
DEC EDI
MOV EDX, [EAX]
SUB EDI, EDX
MOV EDX, EDI
POP EDI
POP ESI
JMP _LStrSetLength
end;
initialization
InitTBL;
← →
Digitman (2003-01-29 17:51) [60]А тема-то, однако - животрепещущая !
Наверняка DB-developer"ы здесь упражняются в "остроумии")..
Угадал ?
← →
Андрей Сенченко (2003-01-29 17:54) [61]вот измененный вариант
procedure TForm1.Button1Click(Sender: TObject);
var
s: string;
i: integer;
begin
s := "q wer t y u";
i := 1;
While s[i] > #0 do
begin
if s[i] = #32 then while s[i+1] = #32 do delete(s,i+1,1);
inc(i);
end;
ShowMessage(s);
end;
← →
danilka (2003-01-29 17:57) [62]так у нас тут битва за скорость?
тогда может стоит уточнить правила: убивать только лишние пробелы или пробелы и непечатные символы, использовать функции или inplace процедуры, определиться с тестированием, у меня, например, вариант Юрия Зотова (28.01.03 10:04) не совсем катит - слишком все быстро, надо текст побольше и сам цикл побольше.
← →
uw (2003-01-29 17:58) [63]Почему никто не использует goto?
← →
Sectey (2003-01-29 18:04) [64]>Mystic ©
ругается на MOVZX EAX, [ESI]
← →
Sectey (2003-01-29 18:18) [65]>Digitman
ну коль перешли на inplace тогда вот немного подумов я кое что нашкрябал.
procedure Sectey(p:PChar);
var
i : integer;
j : integer;
c : char;
begin
i := 0;
j := 0;
c := #0;
while p[i] <> #0 do
begin
p[j] := p[i];
if (c <> #32) or (p[i] <> #32) then
inc(j);
c := p[i];
inc(i);
end;
p[j] := #0;
end;
Процедура тестирования:
procedure TForm1.Button1Click(Sender: TObject);
const
s = "ssd sd sd s s sds d s d sd sd s sd s ";
var
p : PChar;
t : DWORD;
i : integer;
begin
t := GetTickCount;
GetMem(p,StrLen(s));
for i:= 0 to 1000000 do
begin
StrCopy(p, s);
ReduceSpaces(p);
end;
ShowMessage(StrPas(p) + #13#10 + IntToStr(GetTickCount - t));
FreeMem(p);
end;
Не знаю как по поводу варианта Mystic на этот вариант быстрее даже Q_SpaceCompress по моим тестам - 578, а твой - 875, вот так.
← →
Mystic (2003-01-29 18:20) [66]> Sectey © (29.01.03 18:04)
Странно, у меня все нормально.
Можешь заменить на
DB 00h, 46h, 58h, 71h
или на
XOR EAX, EAX
MOV AL, [ESI]
← →
Sectey (2003-01-29 18:24) [67]> Mystic
Да протестил - 1078
← →
Sectey (2003-01-29 18:39) [68]На 29.01.09 18:26
Top - лист по скорости:
-----------------------
Sectey - 578;
Q_SpaceCompress - 688
sha - 797
Mystic - 1078
Romkin - 1468
Андрей Сенченко - 4265
Separator - 13219
Antosya - 20250
mate - 23002
OneSpace - 29845
Song - 389937
StrDelSpace - умер
Не в одном(кроме своего) алгоритме не разбирался брал как есть и тестировал.
Тестировал для себя. Если кто не согласен с моей оценкой прошу провести собственный тест.
← →
Novice (2003-01-29 18:45) [69]Inplace - это нечестно.
2 Юрий Зотов ©
Нельзя ли привести текст программы тестирования с результатами?
Интересно, как вы совмещаете тестирование двух разных видов алгоритмов и оцениваете результаты их работы?
← →
Андрей Сенченко (2003-01-29 18:52) [70]>> Sectey © (29.01.03 18:39)
Я там второй вариант предлагал - его глянь пожалуйста
← →
Novice (2003-01-29 18:54) [71]2 Sectey © (29.01.03 18:18)
Инплэйс инплэйсом, а кто будет возвращать результат в виде строки в цикле тестирования? Хитроват, батенька :)
← →
MAN-In-RED (2003-01-29 20:04) [72]Дурдом, хе-хе...
← →
Mystic (2003-01-29 21:24) [73]Зачем совершенствовать алгоритм, когда можно придумать новый тест, который бы вывел мою процедуру на первое место?! ;)
Поскольку я оптимизил свой код главным образом на длинные входные последовательности (а не на многократный запуск коротких), то решил придумать свой тест - дать на вход каждой функции весь source-код Delphi. Вот результаты (пять испытаний, *10^3):
Mystic 183, 183, 228, 199, 181
Sectey 212, 195, 193, 191, 193
Q_Strings 211, 206, 206, 205, 231
Digitman 273, 290, 294, 319, 272
Sha 305, 296, 270, 286, 269
Romkin 452, 453, 487, 489, 449
Вариант от ManInRed тестировался лишь однократно 21 079
Остальные варианты поумирали (есть там файлик Internet\MSHTML.pas размером 1.5 Мб, вот его не сумели одолеть многие алгоритмы).
Код, использовавшийся для тестирования:
function ProcessFile(const FileName: string): Int64;
var
S: TStream;
St: string;
Tick1, Tick2: Int64;
begin
S := TFileStream.Create(FileName, fmOpenRead);
try
SetLength(St, S.Size);
S.Read(St[1], S.Size);
QueryPerformanceCounter(Tick1);
//Mystic(St);
//Senchenko(St);
//Sectey(PChar(St));
//Q_SpaceCompress(St);
//ReduceSpaces(PChar(St));
//Sha(St);
//Romkin(St);
QueryPerformanceCounter(Tick2);
Result := Tick2 - Tick1;
finally
S.Free;
end;
end;
function ProcessDir(const DirName: string): Int64;
var
sr: TSearchRec;
begin
Result := 0;
if FindFirst(DirName + "\*.pas", faAnyFile and (not faDirectory), sr) = 0 then
begin
repeat
Result := Result + ProcessFile(DirName + "\" + sr.Name);
until FindNext(sr) <> 0;
FindClose(sr);
end;
if FindFirst(DirName + "\*.*", faDirectory, sr) = 0 then
begin
repeat
if (sr.Name <> ".") and (sr.Name <> "..") then
Result := Result + ProcessDir(DirName + "\" + sr.Name);
until FindNext(sr) <> 0;
FindClose(sr);
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
ShowMessage(IntToStr(ProcessDir("C:\Program Files\Borland\Delphi6\Source")));
end;
← →
Sha (2003-01-29 23:26) [74]2 Mystic © (29.01.03 21:24)
Проверь вот это:
function Sha2(const s: string): string;
var
p, q: pchar;
ch: char;
label
ret;
begin;
p:=pointer(s);
SetLength(Result,Length(s));
q:=pchar(pointer(Result))-1;
while true do begin;
repeat;
ch:=p^;
inc(p);
until ch<>" ";
repeat;
if ch=#0 then goto ret;
inc(q);
q^:=ch;
ch:=p^;
inc(p);
until ch=" ";
inc(q);
q^:=ch;
end;
ret:
SetLength(Result,(q-pointer(Result)));
end;
← →
gsu (2003-01-29 23:39) [75]>> Дурдом, хе-хе...
угу
>> Top - лист по скорости:
>> Я там второй вариант предлагал - его глянь пожалуйста
>> Проверь вот это:
красавцы (-:|~
← →
MAN-In-RED (2003-01-29 23:43) [76]Итак, ваш окончательный выбор?
Предлагаю сделать три первых места…
← →
gsu (2003-01-29 23:50) [77]вот мастеров то набежало ...
← →
Secety (2003-01-30 02:45) [78]>Mystic ©
Ну согласись сравнивать программы написанную на асме и на делфях скажем не совсе чесно, так чтобы уровнять их шансы вот второй вариант.
Тестю на другой машине, поэтому цифры могут немного не совпадать с предыдущимы.
Sectey (test) Mystic (test)
SecteyAsm 531 ~26000
Mystic 771 ~28500
И наконец сама программа:
procedure SecteyAsm(p : PChar);
asm
PUSH ESI
PUSH EAX
PUSH EBX
MOV BL, 32
MOV ESI, EAX
MOV EDX, EAX
CLD
XOR EAX, EAX
@@LOOP:
LODSB
MOV [EDX], AL
CMP AH, AL
JNE @@THENCMP
CMP AL, BL
JE @@ENDCMP
@@THENCMP:
INC EDX
@@ENDCMP:
MOV AH, AL
TEST AL, AL
JNZ @@LOOP
@@EXIT:
POP EBX
POP EAX
POP ESI
end;
← →
Sha (2003-01-30 07:00) [79]Sha © (29.01.03 23:26)
2 Mystic © (29.01.03 21:24)
Sorry. Проверь только скорость, правильность работы можно не проверять :)
Видно, вчера перед сном голова глючила. И продолжает до сих пор - никак не соображу как переставить строчки.
Если кто-нибудь подскажет, поделюсь авторством :) Требования к кандидату:
1. количество inc(q); в цикле = 2,
2. только один оператор if ch=#0 then ...
Все, еду на работу. Там посмотрим.
← →
Sha (2003-01-30 07:15) [80]> Secety (30.01.03 02:45)
> Ну согласись сравнивать программы написанную на асме и на делфях скажем не совсе чесно.
Важнее даже другое: все программы (или их обертка в цикле тестирования) должны брать const string и возвращать string - иначе вообще невозможно говорить ни о каком сравнении результатов.
А насчет asm - мне даже интересно на сколько процентов будет эффективнее. Думаю, что для моей Sha2 - не больше чем на 10. (Правда она пока еще работает неправильно, зато уже быстро :)
А это как раз и докажет, что не так важно, на чем писать.
Страницы: 1 2 3 вся ветка
Форум: "Основная";
Текущий архив: 2003.02.10;
Скачать: [xml.tar.bz2];
Память: 0.62 MB
Время: 0.014 c
