0

我有一些函数可以计算由空格分隔的字符串中的子字符串：

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：德尔福 XE2（Unicode）

4

1 回答 1

5

为什么更快？没有探查器是不可能猜到的。这将取决于您运行的 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 代码将是一个快速的位查找指令，而第一个版本将使用比较列表。但我认为这不会有很大的不同。

在所有情况下，我想你应该更好：

  • 不要过早优化——首先使用分析器来猜测什么是慢的和值得重写的；
  • 使用真实数据进行优化，而不是像您的基准测试中那样简化的固定集：您将针对一种数据进行优化，而对于真实数据则不必如此。
于 2012-05-30T17:50:27.507 回答