6

項目の説明フィールド内に特定の文字列 (エンド ユーザーによって提供される) を含む項目テーブルからすべての項目を取得できる必要がある Windows Mobile 6 で実行されるアプリケーションに取り組んでいます。問題は、テーブルに約 170,000 の項目があることです。説明内の任意の場所に文字列を含むすべてのアイテムを返す必要があるため、LIKE %string% を使用する必要があり、インデックスを使用する機会がなくなります。データとテーブルの構造は、もともと Progress データベースに基づいており、単語インデックスのフィールドに素晴らしい contains 演算子があります。SQL Server Compact 3.5 を使用しているため、このモバイル アプリケーションには当てはまりません。

基本的に、私の DAL はクエリを実行し、SqlCeDataReader を取得してから、ItemFactory を使用して、一致した項目のみを含む List オブジェクトを作成します。これにより、明らかに、ドメイン/ビジネス オブジェクトをデータ アクセス層から切り離すことができます。

説明に「ゴルフ」のようなものを含むすべてのアイテムを検索するときにアイテムを取得するのにかかる8mと42秒を除いて、素晴らしくダンディです. 明らかに、これはエンド ユーザーにとって許容できる時間枠ではありません。

私の最初の試みは、代わりに SELECT * FROM Item を使用してデータベースからすべてのアイテムを取得することでした (メインのインデックス付きフィールドの 1 つに order by 句を使用)。この時点で、SqlCeDataReader を実行したときに IndexOf チェックを実行しましたItemFactory は、要求された説明テキストが含まれている場合にのみ List オブジェクトにアイテムを追加します. これにより、速度が 1 分 46 秒に改善されました. 粗末ではありませんが、それでも遅すぎます.

次に、約束を示した別のアプローチを試しました...ほとんど...アプリケーションの起動中に、データベース内のすべてのアイテムオブジェクトを含むリストを作成しようとしました(クエリを実行してリスト全体にデータを入力するのに約2分かかりますが、少なくとも、アプリの初期化中は 1 回だけです... まだ... うーん）。リストが完成したら、そのリストに対して次のようなことを行うクエリを簡単に実行できます (私の構文が正しいことを願っています... 私は今仕事をしておらず、PC に Visual Studio を持っていません)に座っています):

List<Item> specificItems = 
    AllItems.FindAll(i => i.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0);

このアプローチにより、21 秒に短縮されました。とてもいいです（物事の壮大な計画ではまだ遅いですが）。ただし、問題は、データベースからすべてのアイテムをロードすると、メモリの使用量が多すぎることです。OutOfMemoryException がスローされていたため、最初のロード中に最後の 20,000 アイテムを実際にカットする必要がありました (つまり、21 秒の時間枠はおそらく 25 秒のようでした)。エミュレーターのメモリ マネージャーによると、まだ約 20 MB の空き RAM がありましたが、プロセスに関連付けられるのは 32 MB または RAM のみであると聞いています (WM 6 に当てはまるかどうかはわかりませんが、それで）。

List オブジェクトを使用してすべてのアイテムを保持していたためではないことを確認するために (動的なサイズ変更を避けるために、コンストラクターで必要な容量でインスタンス化していました)、これも読んだときに余分なメモリ使用量が発生する可能性があります。暗黙的にEnsureCapacityを呼び出します.Item[]配列を使用してみました（事前にサイズ調整されています）。これにはまだメモリの問題があり、サイズの違いはごくわずかでした。

わかりました。データリーダーによってデータベースから返されるレコードを（異なるタイプのフィールドでのインデックス付き検索を通じて）どのように制限する必要があるかを知っており、最大のパフォーマンスを得るために、アイテムの小さなサブセットで indexOf を使用する可能性があります(したがって、Like 演算子をすべてスキップします)。ただし、これにより、エンド ユーザーは説明検索以上のものを入力する必要があります (おそらく、検索するアイテムの種類を制限するためのアイテム階層情報)。

何か案は？私はこれについて間違った方法で進んでいますか？

聞いてくれてありがとう（この投稿は長くてすみません、私は大声で考えているようなものです）.

ああ、私が使用しているものを（要約して）追加する必要があります：

  • Windows モバイル 6
  • SQL Server コンパクト エディション 3.5
  • C# 3.5

更新: 以下で説明するブルーム フィルターのアプローチは興味深いように見えましたが、1 つの要件 (上記で実際には指定していません) を満たすことができませんでした。他の単語の中に含まれている単語と一致させることはできません (たとえば、"club" は "clubs" を返しません)。このため、私はまったく別のアプローチを使用することを余儀なくされました (Kent Fredric ... 指摘してくれてありがとう)。彼のアプローチが最も多くの要件を満たすものだったので、私はケントの答えを正しいものとしてマークしました（ミッチ、あなたはJaunderが提案したブルームフィルターと同様の問題を抱えていました）。しかし、私は彼の方法とは異なるアプローチを (今のところ...) 行ってきました。

私が行ったことは、アイテム番号と説明のみを使用して、すべてのアイテムオブジェクトをメモリにプルすることです（これにより、メモリの制限の下に保持されますが、それでも初期化に時間がかかります...マルチスレッドと舞台裏でその情報をロードしますアプリケーションの実行中にそれを処理できます）。検索を実行するために、独自の contains ルーチンを作成しました。ルーチンはアンマネージ C# コードで記述されており、2 つのポインターといくつかのループを使用して、説明と必要な一致テキストを実行します。説明のどこかに一致するものが見つかった場合は、項目番号を配列に追加します。すべてのアイテムが検索されると、新しいクエリがデータベースに戻り、一致するアイテム番号のみを取得します (整数フィールドのインデックスにより非常に高速です)。次に、それらのアイテムがすべての情報 (アイテム番号と説明だけでなく) を含むリストに作成されます。全体の操作には約 5 ～ 10 秒かかりますが (説明によって異なります)、今のところはこれで十分です。

これをさらに最適化することを検討します（検索語の文字数を追跡できる可能性があります...必要なテキストよりもアイテムの説明に残っている文字が少ない場合、ループは次のアイテムにまっすぐ続く可能性があります） .

どんな提案でも大歓迎です。今のところ、ケントの答えを私の質問に対して「最も正しい」とマークしました。

contains ルーチンの作成を手伝ってくれた Dolch に感謝します。

4

3 に答える 3

5

項目テーブルを (1 回) 前処理して (それに追加された新しいエントリごとに処理する必要があります)、次の単語出現テーブルを作成するのはどうでしょうか

CREATE TABLE WordItemOccurance
(
    [Word] varchar(50) not null,

    ItemId int not null
        constraint FK_Items references ItemTable(ID)
)

すべてのアイテムを反復処理し、個別の単語に分割し、見つかったエントリをオカレンス テーブルに追加します。

[Word] でクラスター化インデックスを作成し、ItemId でアイテム テーブルに結合するのは高速です。

于 2008-12-31T01:27:07.377 に答える
4

私はMitch Wheat の回答に投票しましたが、有効性をテストするいくつかのトリックもあります。

[char],[int] でいっぱいのテーブルを持つことについての私の大きな心配は、特にこの新しいテーブルで %word% を使用する場合、無意味な文字列比較を大量に実行していることに気付く可能性があることです。(重複しているが一致しない検索エントリ)。

私はおそらくで実験することを選ぶだろう

Words
-----
chars  | word_id 

WordsToEntry
------------
word_id | entry_id

データベースのオーバーヘッドがこの潜在的な問題を軽減する価値があるかどうかを確認します (テストできません、申し訳ありません)。

于 2008-12-31T01:44:39.650 に答える
1

ブルームフィルターを使ってみることができます。

  1. ウィキペディア
  2. ブルームフィルターの使用
于 2008-12-31T02:23:12.163 に答える