通过 "顺序查找" 与 "二分查找" 说明算法的重要性

减小字体 增大字体 作者:万一  来源:万一的博客  发布时间:2010-11-13 13:04:28

代码如下:
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

{ 顺序查找函数 }
function SeqSearch(List: TStringList; const str: string): Integer;
var
  i: Integer;
begin
  for i := 0 to List.Count - 1 do
    if CompareText(List[i], str) = 0 then
    begin
      Result := i;
      Exit;
    end;
  Result := -1;
end;

{ 二分查找函数; 二分查找只能针对有序列表 }
function BinarySearch(List: TStringList; const str: string): Integer;
var
  L, R, M: Integer;
  CompareResult: Integer;
begin
  Result := -1;
  L := 0;
  R := List.Count - 1;

  while L <= R do
  begin
    M := (L + R) div 2;
    CompareResult := CompareText(List[M], str);
    if CompareResult < 0 then
      L := M + 1
    else if CompareResult > 0 then
      R := M - 1
    else
    begin
      Result := M;
      Exit;
    end;
  end;
end;

{ 对比测试 }
procedure TForm1.Button1Click(Sender: TObject);
var
  TestList: TStringList;
  i: Integer;
  n1, n2: Int64;
  Count1, Count2: Integer;
  s: string;
const
  num = 1000000; { 准备测试百万个数据 }
begin
  TestList := TStringList.Create;
  for i := 0 to num - 1 do
    TestList.Add(IntToHex(i, 8)); { 准备有序的测试值列表 }

  Memo1.Clear;
  Count1 := 0;
  Count2 := 0;

  { 搞 10 实验 }
  for i := 0 to 9 do
  begin
    { 产生范围内的随机字串 }
    Randomize;
    s := IntToHex(Random(num), 8);

    { 顺序查找 }
    QueryPerformanceCounter(n1);
    SeqSearch(TestList, s);
    QueryPerformanceCounter(n2);
    Memo1.Lines.Add(IntToStr(n2 - n1) + #9);
    Count1 := Count1 + (n2 - n1);

    { 二分查找 }
    QueryPerformanceCounter(n1);
    BinarySearch(TestList, s);
    QueryPerformanceCounter(n2);
    Memo1.Lines[i] := Memo1.Lines[i] + IntToStr(n2 - n1);
    Count2 := Count2 + (n2 - n1);
  end;

  Memo1.Lines.Add('----------------');
  Memo1.Lines.Add('平均值:');
  Memo1.Lines.Add(IntToStr(Count1 div 10) + #9 + IntToStr(Count2 div 10));
  Memo1.Lines.Add('----------------');
  Memo1.Lines.Insert(0, '顺序'#9'二分');

  TestList.Free;
end;

end.

测试效果图如下:

二分查找太快了, 用 GetTickCount 测试不出来, 只好使用 QueryPerformanceCounter;
另外 TStringList.Find 方法也是使用了 "二分查找" 的办法.

Tags:

作者:万一
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论