itemの検索を高速にしたいのですが。
解決質問させていただきます。Del6Personal使用です。
ListBoxに大量のitem（数千〜数万）がありまして、
その中からItemを検索するときに、Indexofを使っているのですが、
時間がかかるので、検索時間を縮めたいのですが。
Indexofのほかになにかよい方法は無いでしょうか。
itemは
あいうえお1
aaa
ABCDEF
名前１
名前２
のように適当につけた名前が入力されている状態で、
大小文字全角半角混在、文字数不定です。
よろしくお願いします。
基本的にString型変数を使うと、遅くなると思います。
(Windows上でやる以上、どうしても最終的には、内部でも外部でも、PChar型で処理することになると思うので。一部例外はありますけど)
なので、特に高速に何度もString型を使うときだけは、PChar型でやるようにしたほうがいいと思います。
わたしならStringsの文字列をPCharにして、
AnsiStrPosなどで、改行文字を含めて操作(最後の要素のあとには、改行がつくはず)を試してみると思います。
そして、改行の数で調べるとか。
改行の数を調べる処理のせいで、遅くなることも考えられますけど。
あとは、IndexOfを別スレッドでやらせてしまうとか、
そてをいくつかのTStringListに分けて、複数のスレッドに同時にやらせるとか。
方法はあります。
(そういえばエクスプローラの検索とかは、こんなことしてないと思いますけど、
いざやってみると、結構早くなりそうだなぁ…)
ちなみに、PCharのメモリは、使用を終えても開放されないようなことが、ボーランドのサイトに書いてありますけど、
いつのころからか、PCharのメモリは自動的に開放されるようになってるようです。
なので、Delphi6で、ボーランドのFAQにあるような、
New(P1)
・・・
Dispose(P1)
のような処理は不要みたいです。(やろうとすると、Disposeで"無効なポインタ操作"エラーが起こります)
何回も検索をするんですよね。
Indexofは、通常、頭から順になめて検索しますので、1万件なら、
最大１万回の比較が必要です。
item を並び替えてもいいのなら、Sorted を True にしておくと、
２分探索法で検索しますので、最大でも、14回（2^14=16384）で
すみます。
itemの順は変えられないという場合は、TStringListにコピーして、
そちらで、Sort して、IndexOf するようにすればどうでしょうか。
検索数がすくないと、ソートにかかる時間だけ遅くなりますけど、
回数は多いほど効果はでてきます。
サンプル
var
i, FindIndex: integer;
sl: TStringList;
begin
sl := TStringList.Create;
try
sl.Assign(ListBox1.Items);
for i := 0 to sl.Count - 1 do
begin
sl.Objects[i] := Pointer(i);
//Objects に、元のIndexを格納しておく。
end;
sl.CaseSensitive := True;//大文字小文字を区別する。
sl.Sort;
FindIndex := Integer(sl.Objects[(sl.IndexOf(Edit1.Text))]);
//探索したItemからObjects格納したインデックスを取り出す。
ListBox1.ItemIndex := FindIndex;
finally
sl.Free;
end;
もっと高速化が必要というなら、検索用のインデックスを持たせるとか、
固定長にするとか、データ構造からかんがえ直す必要があると思います。
あるでしょう。
hatenaさんの方法で少々速くなりました。
ありがとうございます。（サンプル付だと大変助かります）
Pchar型のほうは、扱い方がよくわからないので、
もう少し勉強してからにします。
こんばんは。
なかなかおもしろそうな問題なので、
どのくらい速くなるのか、実験してみました。
ListBox1 の２万件のデータを、ListBox2の１００個のデータで１００回
検索して、インデックスを配列に格納。
ListBox2の１００個のデータは、均等にばらけるように作成。
(1) ListBox の Items.IndexOf
for i := 0 to 99 do
Idx[i] := ListBox1.Items.IndexOf(ListBox2.Items[i]);
(2) 上で書いた方法（StringList にコピーして、Sort してから検索）
sl := TStringList.Create;
try
sl.Assign(ListBox1.Items);
for i := 0 to sl.Count - 1 do
begin
sl.Objects[i] := Pointer(i);
end;
sl.CaseSensitive := True;
sl.Sort;
for i := 0 to 99 do
Idx[i] := Integer(sl.Objects[(sl.IndexOf(ListBox2.Items[i]))]);
finally
sl.Free;
end;
結果
前処理 検索
(1) 0ms 4098ms
(2) 2686ms 2532ms
StringListへのコピー、インデックス格納、ソート、などの前処理
で３秒弱かかるのはしょうがないとして、２分探索法の理屈からいけば、
もっと速くなるはずだけど、以外とのびない。Objects から取り出す処理が
オーバーヘッドになっているのかな。
他に方法がないか考えて、ハッシュ法を使ったらと思って、いろいろ捜して
みたら、なんと、Delphi6 から、THashedStringList などというピッタリの
クラスがあるではないですか。で、それを試してみました。
長くなったので次に続く。
上の続きです。
(3)THashedStringList にコピーして、IndexOf
sl := THashedStringList.Create;
try
sl.Assign(ListBox1.Items);
for i := 0 to 99 do
Idx[i] := sl.IndexOf(ListBox2.Items[i]);
finally
sl.Free;
end;
(4) (2)の方法で THashedStringList に置き換えた物。
sl := THashedStringList.Create;
try
sl.Assign(ListBox1.Items);
for i := 0 to sl.Count - 1 do
begin
sl.Objects[i] := Pointer(i);
end;
sl.CaseSensitive := True;
sl.Sort;
for i := 0 to 99 do
Idx[i] := Integer(sl.Objects[(sl.IndexOf(ListBox2.Items[i]))]);
finally
sl.Free;
end;
結果 前処理 検索
(1) 0ms 4098ms
(2) 2686ms 2532ms
(3) 1179ms 343ms
(4) 2549ms 53ms
これは効果がありました。検索は桁が違ってきました。
(4)は前処理に時間がかかるので100回の検索だと、(3)の
方がトータルでは成績がいいですが、回数が増えれば増え
るほど効果がでてきそうですね。
※注
THashedStringList を使うには、Uses に、IniFiles を追加する。
この結果はあくまで私の環境で私が作ったサンプルでの結果なので、
参考程度にして、後は各自で検証して下さい。
| ツイート |  |