10

別の言語から C# に変換するプロセスを継承しています。プロセスの多くのステップは、計算を行うために、大量のレコード (100K ～ 200K) になる可能性があるものをループします。これらのプロセスの一部として、通常、別のリストを検索して値を取得します。私は通常、この種のものを SQL ステートメントに移動します (そして、私たちができる場所があります) が、これらの場合、それを行う簡単な方法はありません。いくつかの場所で、コードをストアド プロシージャに変換しようとしましたが、期待したほどうまく機能していないと判断しました。

事実上、コードはこれを行います:

var match = cost.Where(r => r.ryp.StartsWith(record.form.TrimEnd()) && 
                       r.year == record.year && 
                       r.period == record.period).FirstOrDefault();

cost はローカルの List タイプです。1 つのフィールドだけを検索する場合は、おそらくこれを Dictionary に移動します。レコードも常に一意であるとは限りません。

明らかに、これは本当に遅いです。

インデックスを作成できるオープン ソース ライブラリI4Oに出くわしましたが、さまざまなクエリで失敗しました (ソース コードをデバッグする時間がありません)。また、.StartsWith または .Contains では機能しません (元のクエリの多くは、"A" を検索すると "ABC" で一致が見つかるという事実を利用しているため、StartsWith ははるかに重要です)。

この種のことを行う他のプロジェクト (オープンソースまたは商用) はありますか?

編集：

フィードバックに基づいて検索を行ったところ、一意ではないキーを持つ辞書をサポートするPower Collectionsが見つかりました。

私は ToLookup() をテストしましたが、うまく機能しました。元のコードほど高速ではありませんが、少なくとも許容範囲内です。45 秒から 3 ～ 4 秒に短縮されました。他のルックアップのトライ構造を見てみましょう。

ありがとう。

4

2 に答える 2

14

100K から 200K のアイテムのリストをループするのにそれほど時間はかかりません。ネストされたループ (n^2) を使用してリスト内の一致する項目を見つけるには時間がかかります。これがあなたがしていることだと思います（ローカルマッチ変数への割り当てがあるため）。

アイテムをすばやく一致させたい場合は、 を使用します.ToLookup。

var lookup = cost.ToLookup(r => new {r.year, r.period, form = r.ryp});

foreach(var group in lookup)
{
  // do something with items in group.
}

あなたの startswith 基準は、キーベースのマッチングにとって厄介です。この問題に対処する 1 つの方法は、キーを生成するときに無視することです。

var lookup = cost.ToLookup(r => new {r.year, r.period });
var key = new {record.year, record.period};
string lookForThis = record.form.TrimEnd();
var match = lookup[key].FirstOrDefault(r => r.ryp.StartsWith(lookForThis))

理想的には、一度ルックアップを作成し、それを多くのクエリで再利用します。そうしなくても... 毎回ルックアップを作成したとしても、n^2 よりも高速です。

于 2012-04-11T16:30:32.237 に答える
13

確かに、これよりもうまくいくことができます。辞書は、1 つのフィールドに対してクエリを実行する場合にのみ役立つわけではないことを考慮することから始めましょう。キーが多くのフィールドを集約する不変の値である辞書を非常に簡単に作成できます。したがって、この特定のクエリの場合、すぐに改善できるのはキー タイプを作成することです。

// should be immutable, GetHashCode and Equals should be implemented, etc etc
struct Key
{
    public int year;
    public int period;
}

次に、現在のリストのタイプであるIDictionary<Key, ICollection<T>>または同様の場所にデータをパッケージ化します。Tこのようにして、各反復で考慮される行数を大幅に削減できます。

次のステップはICollection<T>、値の型としてan ではなくtrieを使用することです(これは有望に見えます)。これは、指定されたプレフィックスを持つ文字列を見つけるように調整されたデータ構造です。

最後に、無料のマイクロ最適化はTrimEnd、ループから抜け出すことです。

確かに、これはすべて与えられた特定の例にのみ適用され、状況の他の詳細のために再検討する必要があるかもしれませんが、いずれにせよ、これまたは類似のものから実際的な利益を引き出すことができるはずです.

于 2012-04-11T16:15:37.017 に答える