델파이 하위 문자열 카운트 성능

Question

내가 공백으로 구분 된 문자열에 문자열 계산하는 몇 가지 기능을 가지고 있습니다 :

program Project2; 

{$APPTYPE CONSOLE} 

{$R *.res} 

uses System.SysUtils,windows; 

//s=string to search in 
//t=string to search for 
//cs=delimiters 

function f0(const s,t:string;const cs:tsyscharset):integer; 
var 
    p,q:pchar; 
    u:string; 
begin 
    result:=0; 
    p:=pointer(s); 
    if p<>nil then 
    while p^<>#0 do 
    begin 
     while (p^<>#0) and charinset(p^,cs) do inc(p); 
     q:=p; 
     while (p^<>#0) and not charinset(p^,cs) do inc(p); 
     if p>q then 
     begin 
     setstring(u,q,p-q); 
     //writeln('[',u,']'); 
     if u=t then inc(result); 
     end; 
    end; 
end; 

function f1(const s,t:string;const cs:tsyscharset):integer; 
var 
    i,j,l:integer; 
    u:string; 
begin 
    result:=0; 
    l:=length(s); 
    i:=1; 
    while i<=l do 
    begin 
    while (i<=l) and charinset(s[i],cs) do inc(i); 
    j:=i; 
    while (i<=l) and not charinset(s[i],cs) do inc(i); 
    if i>j then 
    begin 
     u:=copy(s,j,i-j); 
     //writeln('[',u,']'); 
     if u=t then inc(result); 
    end; 
    end; 
end; 

function f2(const s,t:string;const cs:tsyscharset):integer; 
var 
    i,j,l:integer; 
    u:string; 
begin 
    result:=0; 
    l:=length(s); 
    i:=1; 
    while i<=l do 
    begin 
    while (i<=l) and charinset(s[i],cs) do inc(i); 
    j:=i; 
    while (i<=l) and not charinset(s[i],cs) do inc(i); 
    if i>j then 
    begin 
     setlength(u,i-j); 
     move(s[j],pointer(u)^,(i-j)*2); 
     //writeln('[',u,']'); 
     if u=t then inc(result); 
    end; 
    end; 
end; 

type 
    tfunc=function(const s,t:string;const cs:tsyscharset):integer; 

const 
    s=' de foo de'+#13+' baz blah de de blah'+#10+' asd de qwe rtz un f'+#9+' t de ds w de '; 
    t='de'; 
    cs=[' ',#13,#10,#9];//CR,LF,TAB 
    n=5000000; 

procedure time(i:integer;f:tfunc); 
var 
    j,k:integer; 
    start,finish,freq:int64; 
begin 
    QueryPerformanceCounter(start); 
    for j := 1 to n do k:=f(s,t,cs); 
    QueryPerformanceCounter(finish); 
    QueryPerformanceFrequency(freq); 
    Writeln(Format('f%u:%u:%.3fs',[i,k,(finish-start)/freq])); 
end; 

const 
    funcs:array[0..2] of tfunc=(f0,f1,f2); 
var 
    i:integer; 
begin 
    setpriorityclass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS); 
    for i := low(funcs) to high(funcs) do time(i,funcs[i]); 
    readln 
end. 

속도 결과

f0:7:7,624s 
f1:7:8,066s 
f2:7:6,454s 

내 첫 번째 질문입니다 것은 :보다 빠른 F2 이유 f0?

두 번째 질문은 다음과 같습니다. 인라인 어셈블러없이이 방법을 훨씬 더 최적화 할 수있는 아이디어가 있습니까?

IDE : Delphi XE2 (유니 코드)

Answer 1

왜 더 빠릅니까? 프로파일 러 없이는 추측 할 수 없습니다. 그리고 실행중인 CPU에 따라 다릅니다. 나는 빨리 생각

는 SetString()가 항상 할당하기 전에 메모리를 해제하는 반면, 대부분의 시간을 재 할당을 피할 수 SetLength() 이후 f2에 의해 처리됩니다. 그것은 당신의 사건에 달려 있습니다. 더 빠른 프로세스를위한

, 같은 알고리즘으로 (당신이 훨씬 더 최적화 된 무언가를 찾을 수 있습니다), 나는 시도를하려는 :

const 
    cs = [32,13,10,9]; 

function f2(const s,t:string):integer; 
var 
    i,j,l:integer; 
begin 
    result := 0; 
    l := length(s); 
    i := 1; 
    while i<=l do 
    begin 
    while (i<=l) and (ord(s[i]) in cs) do inc(i); 
    j:=i; 
    while (i<=l) and not(ord(s[i]) in cs) do inc(i); 
    if (i>j) and CompareMem(pointer(s[j]),pointer(t),(i-j)*sizeof(char)) then 
     inc(result); 
    end; 
end; 

즉 :

• CharInSet는 가치가 없다 제어 문자 용;
• 정적 세트를 사용하면 매개 변수를 전달하는 것보다 빠르게 IMHO가됩니다 (그러나 원하는 경우 매개 변수를 사용할 수 있습니다).
• 임시 변수를 사용하지 마십시오 (알고리즘의 느린 부분이라고 생각합니다). 그러나 좋은 이전 CompareMem - 여기서도 개선의 여지가 있습니다.

당신은 쓰기를 시도 할 수 있습니다 : 첫 번째 버전은 비교의 목록을 사용하는 반면 생성 된 ASM 코드, 빠른 비트보고 명령이 될 것이기 때문에 조금 더 빨리, 될 수

const 
    cs: set of 0..32 = [32,13,10,9]; 

. 그러나 나는 이것이 큰 차이를 만들지 않을 것이라고 생각합니다. 모든 경우에

, 나는 당신이 더 나은해야 같아요

이

• 너무 일찍 최적화되지 않음 - 느리고 재 작성 가치가 무엇인지 추측 먼저 프로파일 러를 사용;
• 실제 데이터으로 최적화하십시오. 벤치 마크에서와 같이 단순화 된 고정 세트가 아닙니다. 실제 데이터에서는 사실 일 필요는 없지만 한 가지 종류의 데이터에 최적화되어 있습니다.