大きなテキストの巨大なリストを検索する最速の方法

Question

私はC＃で書かれたWindowsアプリケーションをデータベースから読み込み、250,000行の読み込みが必要な「検索時に入力」機能を提供しています。アプリケーションは、likeを使用して250,000レコード（btw、各行が1000文字の単一列）を検索し、見つかったレコードを表示する必要があります。

私が続くアプローチがされた：

1 - アプリケーションの負荷のすべてのレコードTextChangedイベントで入力List<EmployeeData>

while (objSQLReader.Read()) 
{ 
    lstEmployees.Add(new EmployeesData(
     Convert.ToInt32(objSQLReader.GetString(0)), 
     objSQLReader.GetString(1), 
     objSQLReader.GetString(2))); 
} 

2 - に、LINQを使用して、私は正規表現の組み合わせで（検索）、仮想モードのListViewにIEnumerable<EmployeesData>を添付します。

String strPattern = "(?=.*wood*)(?=.*james*)"; 
    IEnumerable<EmployeesData> lstFoundItems = from objEmployee in lstEmployees 
    where Regex.IsMatch(Employee.SearchStr, strPattern, RegexOptions.IgnoreCase) 
    select objEmployee; 
    lstFoundEmployees = lstFoundItems; 

3- RetrieveVirtualItemイベントは、アイテムを表示するためにアイテムをListViewに表示するために処理されます。 lstEmployeesものの

e.Item = new ListViewItem(new String[] { 
    lstFoundEmployees.ElementAt(e.ItemIndex).DateProjectTaskClient, 
    e.ItemIndex.ToString() }); 

がTextChangedに検索するには、SQL Serverからリストをロードするための比較的高速（1.5秒）にロードされ、それは、LINQを使用して検索するために7分以上かかります。 LIKE検索を実行してSQL Serverを直接検索するのにかかる時間は7秒未満です。

私はここで間違っていますか？この検索をより速くするにはどうすればいいですか（2秒以下）？これは私のクライアントからの要件です。だから、どんな助けも高く評価されます。助けてください...

Answer 1

this questionへの私の答えを参照してください。インスタントレスポンスが必要な場合（つまり、ユーザータイプと同じ速さで）、データをメモリにロードすることは非常に魅力的な選択肢になります。それは少しのメモリを使用するかもしれませんが、非常に高速です。

多くの文字（250Kレコード* 1000）があるにもかかわらず、個数が一意であるという値がありますか？それらのキーと一致するレコードへのポインタを持つキーに基づいたメモリ内構造は、実際にそのキーの順列を考慮しても、それほど大きくなくてもかまいません。

データが本当にメモリに格納されない、または頻繁に変更されない場合は、データベースに保存して、SQL Serverのフルテキストインデックス処理を使用します。このような検索はLIKEよりもはるかに優れています。これは、アプリケーションからデータベースへの高速接続を前提としています。

フルテキストインデックス作成は、検索をよりインテリジェントにするために使用できる強力な演算子/式のセットを提供します。これは、最大10GBのデータを処理する無料のSQL Expression Editionで利用できます。

Answer 2

レコードをソートすることができれば、大量のデータセットの方がはるかに高速なバイナリ検索が必要な場合があります。 .NETコレクションには、List<T>とArrayのような実装がいくつかあります。あなたは物事をプリロードし、自分自身のデータ構造を構築したいことだろう

Answer 3

は、それは、メモリを大量に消費だtrie

と呼ばれるが、それは医師が、この場合には注文したものです。

Answer 4

テキストデータを格納するデータベース列にインデックスがありますか？もしそうなら、Nicholasが記述したtrie structureと同様のものが既に使用されています。 SQL Serverのインデックスは、B+ treesを使用して実装されています。平均検索時間は、ログベース2のn（nはツリーの高さ）のオーダーです。これは、テーブルに250,000レコードがある場合、検索に必要な操作の数はログベース2（250,000）または約18の操作であることを意味します。

すべての情報をデータ・リーダーにロードし、LINQ式を使用すると、線形演算（O）n（nはリストの長さ）です。最悪の場合、25万回の操作になるでしょう。 DataViewを使用している場合は、索引が検索に役立つため、パフォーマンスが大幅に向上します。

データベースサーバーに対して送信されるリクエストが多すぎない場合は、クエリオプティマイザを活用してこれを実行します。 LIKE操作が文字列の前にワイルドカード（つまりLIKE %some_string）を使用して実行されていない限り（インデックスの使用は無効になります）、テーブルにインデックスがある場合、非常に高速なパフォーマンスが得られます。データベースサーバーに送信されるリクエストが多すぎる場合は、インデックスを使用できるように、すべての情報をDataViewに入れてください。また、上記で提案したTimのように辞書を使用してください。検索時間はO（1 ）（1のオーダー）、辞書がハッシュテーブルを使用して実装されていると仮定します。