delphi子串计数性能

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(Unicode)

Answer 1

为什么它更快？没有探查器就无法猜测.它取决于您运行的CPU.

我想更快将被处理f2因为SetLength()将避免在大多数时间重新分配,而SetString()在分配它之前将始终释放内存.这取决于你的情况.

对于更快的过程,使用相同的算法(您可能会发现更优化的东西),我会尝试:

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不值得控制字符;
• 使用静态集是恕我直言,比传递参数更快(但如果你愿意,你可以使用一个参数);
• 不要使用临时变量(我认为这是算法的慢速部分),但是一个好老CompareMem- 这里仍有改进的余地.

你可以尝试写:

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

这可能会快一点,因为生成的ASM代码将是一个快速的位寻指令,而第一个版本将使用比较列表.但我认为这不会产生很大的影响.

在所有情况下,我想你应该更好:

• 没有过早优化 - 首先使用分析器来猜测什么是缓慢的,值得重写;
• 使用真实数据进行优化,而不是基准测试中的简化固定集:您将针对一种数据进行优化,而对于实际数据则不一定如此.