// 100만개 Record 처리하는데 6초 걸림.
unit Unit5;

interface

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

type
  // Record 선언하기 
  PDataA = ^TDataA;

  TDataA = Record
    admn_no: integer;
    name: string;
  end;

  TForm5 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form5: TForm5;

implementation

{$R *.dfm}

// sort(admn_no) 
function Sort_Item_admn_no(item1, item2: Pointer): integer;
begin
  Result := PDataA(item1)^.admn_no - PDataA(item2)^.admn_no;
end;

// sort(name) 
function Sort_Item_name(item1, item2: Pointer): integer;
begin
  Result := AnsiCompareText(PDataA(item1)^.name, PDataA(item2)^.name);
end;

// sort(name, admn_no)
function Sort_Item_name_no(item1, item2: Pointer): integer;
begin
  Result := AnsiCompareText(PDataA(item1)^.name, PDataA(item2)^.name);
  if Result = 0 then
    Result := PDataA(item1)^.admn_no - PDataA(item2)^.admn_no;
end;

function QuickFind(List: TList; var Index: integer; pt: Pointer; Compare: TListSortCompare): boolean;
var
  L, h, i, C: integer; // 첫번째 항목을 찾도록 함. 
begin
  Result := false;
  L := 0;
  h := List.Count - 1;
  if (Index >= L) and (Index <= h) and (Compare(List[Index], pt) = 0) then
  begin
    Result := true;
    exit;
  end;

  while L <= h do
  begin
    i := (L + h) shr 1;
    C := Compare(List[i], pt);
    if C < 0 then
      L := i + 1
    else
    begin
      h := i - 1;
      if C = 0 then
      begin
        Index := i;
        Result := true;
      end;
    end;
  end;
end;

procedure TForm5.Button1Click(Sender: TObject);
var
  List: TList;
  i, n, nCnt, index: integer;
  aP, cP: PDataA;
begin
  List := TList.create;
  New(cP); // 찾기용 Record 생성함. 
  try
    Memo1.Lines.Clear;
    Memo1.Lines.BeginUpdate;
    nCnt := 1000000; // 100만개 데이터
    // Sample data 만들기 // Test용 - 실제 데이터 넣으면 됨. 
    for i := 0 to nCnt - 1 do
    begin
      New(aP); // 새로운 데이터 
      List.Add(aP); // List에 넣기 
      aP^.admn_no := i; // 실제 데이터 값 
      aP^.name := inttostr(i);
    end;

    // 순서 섞기 
    Randomize;
    for i := nCnt-1 downto nCnt div 2 do
    begin
      n := Random(i);
      if n <> i then
        List.Exchange(n, i);
    end;

    // Sort 전 
    // Memo1.Lines.Add('Sort 전'); 
    for i := 0 to List.Count - 1 do
      with PDataA(List[i])^ do
      begin
        // Memo1.Lines.Add(name); // name으로 Sort 순서를 볼수 있음. 
      end;

    List.Sort(Sort_Item_name); // Sort(name) 

    // Memo1.Lines.Add('Sort 후'); 
    for i := 0 to List.Count - 1 do
      with PDataA(List[i])^ do
      begin
        // Memo1.Lines.Add(name);  // name으로 Sort 순서를 볼수 있음. 
      end;

    // Sort 후 찾기 
    Memo1.Lines.Add(''); //
    cP^.name := inttostr(Random(nCnt)); // 찾을 값 넣기 
    if QuickFind(List, Index, cP, Sort_Item_name) then // Sort 후 찾기 (log2 N) 
    begin
      aP := List[index]; // Index 순번, aP 찾은  record; 
      Memo1.Lines.Add(aP^.name);
    end;

//    List.Sort(Sort_Item_name_no); // sort(name, admn_no) //항목은 원하는 데로 늘리수 있음.
                                  // 해당 비교구문을 만들어 줘야 함.

    List.Sort(Sort_Item_admn_no); // Sort(admn_no)

    for i := 0 to List.Count - 1 do
      with PDataA(List[i])^ do
      begin
        // Memo1.Lines.Add(inttostr(admn_no));  // name으로 Sort 순서를 볼수 있음. 
      end;

    // Sort 후 찾기 
    cP^.admn_no := Random(nCnt); // 찾을 값 넣기 
    if QuickFind(List, Index, cP, Sort_Item_admn_no) then // Sort 후 찾기 (log2 N) 
    begin
      aP := List[index]; // Index 순번, aP 찾은  record; 
      Memo1.Lines.Add(aP^.Name);
    end;

  finally
    Memo1.Lines.EndUpdate;
    for i := 0 to List.Count - 1 do
    begin
      PDataA(List[i])^.name := ''; // String경우 reset 
      Dispose(List[i]); // 메모리 해제 
    end;

    List.Free;
    Dispose(cP);
  end;
end;

end.