TDictionaryをフィルタリング＆ソートする

ども、Norimakiです。

久しぶりにDelphiのお話です。

Delphiでデータを扱う際にTDictionaryとかTListなどをよく使います。
で、TDictionaryは検索が効率的だということで、そっちを使いたいんですが、
ソートが出来ないという問題にぶち当たります。

そもそもTDictionaryはソートするもんじゃないぜ。

と言われそうですが、それでもソートしたい時ってのがあるわけで。

じゃあどうするか？

データをTDictionaryに持たせて、順番をTListに持たせる。

という方法でどうだと。

「順番をTListに持たせる」というのは何か気持ち悪い表現ですが、
それはおいておいて、まず、TDictionayのキーをTListに保存するわけですね。
for-in-doを使ってキーを抜き出してTListに保存します。

ここで、必要に応じてフィルタリングをするのも良いでしょう。

で、TListはソートできますから、ソートの際にはTListのソートをつかうと。

TDictionayのキーはどういう型であれ一意ですから、
TListとTDictionaryは１対１で対応しています。

ということで、サンプルがこちら。

procedure TForm1.TDictionaryFilterSort;

 procedure DispStatus(Str:string);
 begin
  StatusBar1.SimpleText:=Str;
  StatusBar1.Update;
 end;

 function TimerStart:Cardinal;
 begin
  timeBeginPeriod(1);
  Result:=timeGetTime;
 end;

 function TimerEnd(st:cardinal):Cardinal;
 begin
  Result:=timeGetTime-st;
  timeEndPeriod(1);
 end;

 function GetTimerMemo(t:cardinal;str:string):string;
 begin
  Result:=Str+' '+FormatFloat('#,##0 msec',t)+#13#10;
 end;


type
 TNYSampleRec=record
  Number:integer;
 end;


var Dic:TDictionary&lt;integer,TNYSampleRec&gt;;
    MyList:TList&lt;integer&gt;;
    i,id:integer;
    Rt:TNYSampleRec;
    s,u:string;
    t:Cardinal;

    LoopCnt :integer;
    JudgeCnt:integer;
begin

 LoopCnt :=SpinEdit2.Value;
 JudgeCnt:=SpinEdit3.Value;

 u:='';

 Dic   :=TDictionary&lt;integer,TNYSampleRec&gt;.Create;
 MyList:=TList&lt;integer&gt;.Create;

 try
  DispStatus('ダミーデータ作成');
  t:=TimerStart;
  for i:=1 to LoopCnt do begin
   Rt.Number:=Random(100);
   Dic.Add(i,Rt);
  end;
  t:=TimerEnd(t);
  u:=u+GetTimerMemo(t,'ダミーデータ作成');


  DispStatus('フィルタリング');
  t:=TimerStart;
  for i in Dic.Keys do begin
   if Dic[i].Number&gt;JudgeCnt then continue;
   MyList.Add(i);
  end;
  t:=TimerEnd(t);
  u:=u+GetTimerMemo(t,'フィルタリング');


  DispStatus('ソート');
  t:=TimerStart;
  MyList.Sort(
   TComparer&lt;integer&gt;.Construct(
    function(const ID1,ID2:integer):integer
    begin
     Result:=Dic[ID1].Number-Dic[ID2].Number;
     if Result=0 then Result:=ID1-ID2;
    end
   )
  );
  t:=TimerEnd(t);
  u:=u+GetTimerMemo(t,'ソート');

  DispStatus('表示データ作成');
  t:=TimerStart;
  Memo2.Clear;
  Memo2.Lines.BeginUpdate;
  s:='';
  try
   for i:=0 to MyList.Count-1 do begin
    id:=MyList[i];
    //Memo2.Lines.Add(IntToStr(id)+' '+IntToStr(Dic[id].Number));
    s:=s+IntToStr(id)+' '+IntToStr(Dic[id].Number)+#13#10;

    if (i mod 10000)=0 then DispStatus('表示データ作成 '
                             +IntToStr(i)+'/'+IntToStr(MyList.Count));
   end;
   t:=TimerEnd(t);
   u:=u+GetTimerMemo(t,'表示データ作成');


   DispStatus('表示データ転送');
   t:=TimerStart;
   Memo2.Lines.Text:=s;
   t:=TimerEnd(t);
   u:=u+GetTimerMemo(t,'表示データ転送');

   Memo2.Lines.Add(#13#10+u);

  finally Memo2.Lines.EndUpdate;
  end;


 finally FreeAndNil(Dic);
         FreeAndNil(MyList);
 end;

 DispStatus('');
end;

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

procedure TForm1.TDictionaryFilterSort;

procedure DispStatus(Str:string);

begin

StatusBar1.SimpleText:=Str;

StatusBar1.Update;

end;

function TimerStart:Cardinal;

begin

timeBeginPeriod(1);

Result:=timeGetTime;

end;

function TimerEnd(st:cardinal):Cardinal;

begin

Result:=timeGetTime-st;

timeEndPeriod(1);

end;

function GetTimerMemo(t:cardinal;str:string):string;

begin

Result:=Str+' '+FormatFloat('#,##0 msec',t)+#13#10;

end;

type

TNYSampleRec=record

Number:integer;

end;

var Dic:TDictionary<integer,TNYSampleRec>;

MyList:TList<integer>;

i,id:integer;

Rt:TNYSampleRec;

s,u:string;

t:Cardinal;

LoopCnt :integer;

JudgeCnt:integer;

begin

LoopCnt :=SpinEdit2.Value;

JudgeCnt:=SpinEdit3.Value;

u:='';

Dic :=TDictionary<integer,TNYSampleRec>.Create;

MyList:=TList<integer>.Create;

try

DispStatus('ダミーデータ作成');

t:=TimerStart;

for i:=1 to LoopCnt do begin

Rt.Number:=Random(100);

Dic.Add(i,Rt);

end;

t:=TimerEnd(t);

u:=u+GetTimerMemo(t,'ダミーデータ作成');

DispStatus('フィルタリング');

t:=TimerStart;

for i in Dic.Keys do begin

if Dic[i].Number>JudgeCnt then continue;

MyList.Add(i);

end;

t:=TimerEnd(t);

u:=u+GetTimerMemo(t,'フィルタリング');

DispStatus('ソート');

t:=TimerStart;

MyList.Sort(

TComparer<integer>.Construct(

function(const ID1,ID2:integer):integer

begin

Result:=Dic[ID1].Number-Dic[ID2].Number;

if Result=0 then Result:=ID1-ID2;

end

)

);

t:=TimerEnd(t);

u:=u+GetTimerMemo(t,'ソート');

DispStatus('表示データ作成');

t:=TimerStart;

Memo2.Clear;

Memo2.Lines.BeginUpdate;

s:='';

try

for i:=0 to MyList.Count-1 do begin

id:=MyList[i];

//Memo2.Lines.Add(IntToStr(id)+' '+IntToStr(Dic[id].Number));

s:=s+IntToStr(id)+' '+IntToStr(Dic[id].Number)+#13#10;

if (i mod 10000)=0 then DispStatus('表示データ作成 '

+IntToStr(i)+'/'+IntToStr(MyList.Count));

end;

t:=TimerEnd(t);

u:=u+GetTimerMemo(t,'表示データ作成');

DispStatus('表示データ転送');

t:=TimerStart;

Memo2.Lines.Text:=s;

t:=TimerEnd(t);

u:=u+GetTimerMemo(t,'表示データ転送');

Memo2.Lines.Add(#13#10+u);

finally Memo2.Lines.EndUpdate;

end;

finally FreeAndNil(Dic);

FreeAndNil(MyList);

end;

DispStatus('');

end;

こんな感じで。

usesに、Generics.Collections,Generics.Defaults,MMSystem
を追加して下さい。

フォームには、

・SpinEdit2
・SpinEdit3
・StatusBar1
・Memo2

コンポーネントを設置して下さい。
StatusBar1のSimplePanelプロパティはTrueに設定。

SpinEdit2にダミーデータの個数。
SpinEdit3にフィルタリングの数。

を設定します。

フィルタリングについては、
ダミーデータとしてランダムに0から99までの数字が設定され、
設定数以下の数字を抽出する。という仕組みになっています。

面倒なら、ソース中の

LoopCnt :=SpinEdit2.Value;
JudgeCnt:=SpinEdit3.Value;

に適当な数字を入れて下さい。

テスト的には、
LoopCntに1000000、JudgeCntに50をいれてみるといいのではないかと。

うちの環境では、上記設定で

ダミーデータ作成 282 msec
フィルタリング 128 msec
ソート 2,893 msec
表示データ作成 169 msec
表示データ転送 1,965 msec

という感じになりました（詳しい環境状況はよくわかりません）。

あとは、ジェネリクスを使ったり、ソート・フィルタリング部を
分離したりして一般化して使いやすくするとどうかなと。

これが使えるかどうか、意味があるかどうかはわかりませんが、
こういうやり方もありかなと。

ではでは。
Norimakiでした。