TStringListで、特定の文字列から開始する行を高速で抜き出す方法

解決

mb 2011-01-18 06:18:30 No: 39837

いつもお世話になります。1点質問させてください。

1  前提条件
  ●StringListに、10000行程度のデータが入っている。
  ●StringListはソート済み。
  ●この内容は、半角英数の文字データのみです。
    (単語補完用の辞書ファイルのデータです。)

2  行いたいこと
  ●このStringListの中で、特定の文字列から始まる行を抽出したい。
    (大/小文字は区別しない)

例えば、aaa, aab, abcというリストがあったとして、検索文字列が
aaである場合は、aaaとaabを抜き出すという動作になります。

    ※参考までに書いておくと、現在開発中のテキストエディタの単語補完
    機能の一部として組み込みます。カーソル位置が変わるごとに頻繁に
    抽出処理を行うため、ちょっともっさりするだけでも体感速度に大きな
    影響が出てしまいます。

3  これまでに試したこと
  ●単純に上からAnsiPos (〜) = 0  で判定した処理を組み込みました。
    ですが、これだともっさりします。

  ●StringListの各行の頭1文字を基準として、二分法(？)的な処理を試しました。
    例：検索文字列を「cde」とする。
        →StringListの5000行目の頭1文字がHだったとしたら、
          検索文字列の頭1文字のcはHよりも前なので、1行目から5000行目
          までを処理の対象とする。
        →この処理を延々と続けて、範囲を確定する。

多少検索速度は改善したが、もし同じ文字で始まる単語が非常に
多くなった場合、検索速度があまり改善しないケースが出てしまう。

どうすれば抽出処理が早くなるでしょうか。何か、よい手順等をご存知の方
がいらっしゃいましたら、ご助言をいただければと思います。

igy 2011-01-18 09:25:58 No: 39838

前提条件として、TStringList が挙げられていますが、
データベースを使うのはダメですか？

ちなみに、
> ●単純に上からAnsiPos (〜) = 0 で判定した処理を組み込みました。
> ●StringListの各行の頭1文字を基準として、二分法(？)的な処理を試しました。
の２つは、速度は具体的には、何秒かかりますか？

KHE00221 2011-01-18 10:41:54 No: 39839

ソートした後にＡ−Ｚの INDEX を作る

monaa 2011-01-18 18:40:38 No: 39840

StringList.find(str,var index)を使ってみましたか？
二分探索にmdさんの挙げられるようなデメリットはありませんよ。
VCLで既にこのアルゴリズムは実装されてますので、それを使うのがよろしいかと。

monaa 2011-01-18 19:17:15 No: 39841

補足ですが、この場合ソート方法もStringListのソートに準拠擦る必要があります。
文字の比較にkernel32のCompareStringを使用しているため。
独自ソートならFindのソースをコピーしてCompareStringを書き換えてください
って余計なお世話ですね。

au 2011-01-18 20:00:51 No: 39842

trie木ってのが使えるんじゃないでしょうか。
ちょろっと見ただけなんで外してるかもですが

mb 2011-01-19 06:08:28 No: 39843

igy様
ご提案ありがとうございます。
ただ、手軽に使えるソフトを目指したいので、DBの使用は最後の方の手段に
したいと思っています。

KHE00221
このスレとは無関係ですが、あなたの発言はいつも参考にさせていただいています。ありがとうございます。
あの後、Indexを付けるというアイデアを漠然と考えていましたが、確かにこの方式はよいかもしれませんね。ちょっと考えさせてください。

monaa様
以前、別ハンドルを使っていたとき、あなたから助言をいただいて問題が単純明快に解決したことがありました。改めて御礼を申し上げます。
ただ、Findは、「特定の文字列から始まる」ではなく、「特定の文字列に完全一致する」行を探すものだと思います。IndexOfと、Findはヘルプで見ていたのですが、今回の検索には使えないのでは？と考えています。

au様
Trie木というのは知りませんでした。検索してみたところ、イメージとしては近そうなのですが、今回の件に適用できるのかどうか、調べてみたいと思います。ちょっとだけ難しそうですが…

monaa 2011-01-19 07:36:55 No: 39844

大した違いはないですよ、一応例を上げておきますね。
開始と終わりのインデックスを探して、その間をズラズラ引き抜きます。
抜き出し箇所は手抜きしてますので、改善の余地ありです。

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Button1: TButton;
    ListBox1: TListBox;
    Edit1: TEdit;
    ListBox2: TListBox;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private 宣言 }
    fStrList:TStringList;
  public
    { Public 宣言 }
  end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure FindNearMin(aStrList:TStringList; S: string; var Index: Integer);
var
  L, H, I, C: Integer;
begin
  L := 0;
  H := aStrList.Count - 1;
  while L <= H do
  begin
    I := (L + H) shr 1;
    C := AnsiCompareStr(Copy(aStrList.Strings[I],1,Length(S)), S);
    if C < 0 then
    begin
      L := I + 1;
    end else begin
      H := I - 1;
    end;
  end;
  Index := L;
end;

procedure FindNearMax(aStrList:TStringList; S: string; var Index: Integer);
var
  L, H, I, C: Integer;
begin
  L := 0;
  H := aStrList.Count - 1;
  while L <= H do
  begin
    I := (L + H) shr 1;
    C := AnsiCompareStr(Copy(aStrList.Strings[I],1,Length(S)), S);
    if C <= 0 then
    begin
      L := I + 1;
    end else begin
      H := I - 1;
    end;
  end;
  Index := H;
end;

function ExtractStr(aStrList:TStringList; S:string):string;
var
  aBegin,aEnd:Integer;
  i: Integer;
begin
  FindNearMin(aStrList,S,aBegin);
  FindNearMax(aStrList,S,aEnd);
  for i := aBegin to aEnd do
    Result := Result + aStrList.Strings[i] + #$D#$A;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
ListBox2.Items.Text := ExtractStr(fStrList,Edit1.Text);
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  i: Integer;
begin
  fStrList := TStringList.Create;
  for i := 0 to 1000 do
    fStrList.Add(IntToStr(i));
  fStrList.Sort;
  ListBox1.Items.Text := fStrList.Text;
end;

end.

deldel 2011-01-19 19:33:58 No: 39845

視点を変えて・・・
StringListを１つにするのではなく、例えば、
aから始まるものだけをStringListAに、
bから始まるものだけをStringListBに・・・
などとしておけば、検索対象がかなり少なくなると思います。
どう振り分けるかが難しいとは思いますが・・・

monaa 2011-01-19 22:34:00 No: 39846

ちょっと気づいたのですが、10000個程度の文字検索なら
今のパソコンならそれこそ全文検索でも10ms以下で完了しませんか？
もっさり動くのは恐らく、候補のリストアップの方だと思います。
となると、候補をリストビューに表示する際、いわゆるバーチャルモードでリストアップして、全ての候補は読み込まない技術に力を入れた方がいいと思いますよ。

procedure TForm1.Button1Click(Sender: TObject);
var
  c: Cardinal;
  i,p: Integer;
  str1,str2:string;
  aStrList:TStringList;
begin
  aStrList := TStringList.Create;
  for i := 0 to 10000 do
    aStrList.Add(IntToStr(i));
  c:= GetTickCount;
  str1 := '111';
  for i := 0 to aStrList.Count - 1 do
  begin
    str2 := aStrList.Strings[i];
    if CompareStr(Copy(str2,1,Length(str1)),str1)=0 then
      inc(p);
  end;
  Caption := IntToStr(GetTickCount-c) + '-' + IntToStr(p);
  aStrList.Free;
end;

mb 2011-01-21 06:22:16 No: 39847

monaa様

出張で家を空けておりまして、返答が遅れてしまいました。
今、実際にやってみました。おっしゃるとおり、抽出時間ではなく、
どちらかというとリストボックスに表示する際に時間がかかっている様子でした。

抽出処理ばかりに眼が行っていて、こちらはノーチェックでした。
的確なご助言、本当にありがとうございます。

しばらく前、ListViewのOnDataイベントで処理を軽量化したことがあります
ので、それを応用して適用してみます。

今はちょっとこれに取り掛かれる時間が取れないので、土日に家で試して
みたいと思います。結果は報告したいと思いますので、ちょっとお時間を
いただければと思います。

deldel様
アイデア、どうもありがとうございます。
実は、最初の頃、それもちょっとだけ考えていました。ただ、今回は上記の
とおり別方向から攻めてみた方がよさそうなので、ちょっとだけ表題の件は
寝かさせてください。

mb 2011-02-04 06:20:15 No: 39848

報告が遅れました。申し訳ありません。

それで、結局原因は表示時の処理速度の問題であって、
抽出時の問題ではありませんでした。確認不足で申し訳
ありませんでした。

結論としまして、TListViewの仮想リストビューを使用した
ところ、処理速度が向上し、実使用に耐えうるスピードと
なりました。そのため、これで解決といたします。

見当違いの質問をしてしまい、大変申し訳ありませんでした。
それとともに、親切にご助言いただいた皆様には、深く御礼
を申し上げます。ありがとうございました。

mb 2011-02-04 06:21:28 No: 39849

チェックをつけます。