C＃の巨大なリストをフィルタリングする最もパフォーマンスの良い方法は？

Question

エンティティフレームワーク経由でSQL Server DBに接続されているASP.NET MVC Webアプリケーションがあります。このアプリケーションの主なタスクの1つは、ユーザーがアーカイブ値を保持する巨大なデータベーステーブルをすばやく検索およびフィルタリングできるようにすることです。

テーブル構造は非常に単純です：タイムスタンプ（DateTime）、StationId（int）、DatapointId（int）、Value（double）。この表には、10億〜1億行の間のものがあります。私はDBテーブルをカバリングインデックスなどで最適化しましたが、DatapointId、StationId、Time、Skippingでフィルタリングして、ページに表示したい部分だけを取ると、ユーザーエクスペリエンスはまだかなり遅いです。

私はサーバーに多くのRAMがあるため、Webアプリケーションの起動時にアーカイブテーブル全体をList<ArchiveRow>にロードするだけで、このリストから直接データを取得することができますデータベースへの往復をする代わりに。これは非常にうまくいきます。アーカイブテーブル全体（現在は約1,000万エントリ）をリストにロードするのに約9秒かかります。

public class ArchiveResponse { 
    public int Length { get; set; } 
    public int numShown { get; set; } 
    public int numFound { get; set; } 
    public int numTotal { get; set; } 
    public List<ArchiveRow> Rows { get; set; } 
} 

し、それに応じて：

public class ArchiveRow { 
    public int s { get; set; } 
    public int d { get; set; } 
    public DateTime t { get; set; } 
    public double v { get; set; } 
}  

私は今、LINQクエリをリストから目的のデータを取得しようとすると、それはすでに高速ですArchiveRowは、次のようになります単純なオブジェクトでありますDBにクエリを実行していますが、複数の条件でフィルタリングすると、まだかなり遅いです。たとえば、1つのStationIdと12のDatapointIdsでフィルタすると、25行のウィンドウを取得するのに約5秒かかります。私はすでにWhereのフィルタリングから結合を使用するように切り替えましたが、まだ改良の余地があると思います。メモリ消費量を可能な限り低く抑えながらキャッシュメカニズムを実装する方が良いでしょうか？この目的に適した他のコレクションタイプがありますか？

// Total number of entries in archive cache 
var numTotal = ArchiveCache.Count(); 

// Initial Linq query 
ParallelQuery<ArchiveCacheValue> query = ArchiveCache.AsParallel(); 

// The request may contain StationIds that the user is interested in, 
// so here's the filtering by StationIds with a join: 
if (request.StationIds.Count > 0) 
{ 
    query = from a in ArchiveCache.AsParallel() 
      join b in request.StationIds.AsParallel() 
      on a.StationId equals b 
      select a; 
} 

// The request may contain DatapointIds that the user is interested in, 
// so here's the filtering by DatapointIds with a join: 
if (request.DatapointIds.Count > 0) 
{ 
    query = from a in query.AsParallel() 
      join b in request.DatapointIds.AsParallel() 
      on a.DataPointId equals b 
      select a; 
} 

// Number of matching entries after filtering and before windowing 
int numFound = query.Count(); 

// Pagination: Select only the current window that needs to be shown on the page 
var result = query.Skip(request.Start == 0 ? 0 : request.Start - 1).Take(request.Length); 

// Number of entries on the current page that will be shown 
int numShown = result.Count(); 

// Build a response object, serialize it to Json and return to client 
// Note: The projection with the Rows is not a bottleneck, it is only done to 
// shorten 'StationId' to 's' etc. At this point there are only 25 to 50 rows, 
// so that is no problem and happens in way less than 1 ms 
ArchiveResponse myResponse = new ArchiveResponse(); 
myResponse.Length = request.Length; 
myResponse.numShown = numShown; 
myResponse.numFound = numFound; 
myResponse.numTotal = numTotal; 
myResponse.Rows = result.Select(x => new archRow() { s = x.StationId, d = x.DataPointId, t = x.DateValue, v = x.Value }).ToList(); 

return JsonSerializer.ToJsonString(myResponse); 

いくつかの詳細：局数が50から5の間に通常の何かが、まれ以上50.ある

だからここには、フィルタリングし、ArchiveCacheリストから該当するデータをフェッチコードですデータポイントの数は< 7000です。Webアプリケーションは、web.configに<gcAllowVeryLargeObjects enabled="true" />を設定して64ビットに設定されています。

私は本当にさらなる改善と推奨をお待ちしております。たぶん、配列やそれに類するものをベースにした全く異なるアプローチがありますが、より良い方法を実行しますなし linq？

Answer 1

この特定のクエリタイプにストレージを調整することができます。まず、あなたのインメモリアーカイブから辞書を作成します。

ArchiveCacheByDatapoint = ArchiveCache.GroupBy(c => c.DataPointId) 
      .ToDictionary(c => c.Key, c => c.ToList()); 
ArchiveCacheByStation = ArchiveCache.GroupBy(c => c.StationId) 
      .ToDictionary(c => c.Key, c => c.ToList()); 

次に、あなたのクエリでこれらの辞書を使用します。

bool hasStations = request.StationIds.Length > 0; 
bool hasDatapoints = request.DatapointIds.Length > 0;    
int numFound = 0; 
List<ArchiveCacheValue> result; 
if (hasDatapoints && hasStations) { 
    // special case - filter by both 
    result = new List<ArchiveCacheValue>(); 
    // store station filter in hash set 
    var stationsFilter = new HashSet<int>(request.StationIds); 
    // first filter by datapoints, because you have more different datapoints than stations 
    foreach (var datapointId in request.DatapointIds.OrderBy(c => c)) {      
     foreach (var item in ArchiveCacheByDatapoint[datapointId]) {       
      if (stationsFilter.Contains(item.StationId)) { 
       // both datapoint and station matches filter - found item 
       numFound++; 
       if (numFound >= request.Start && result.Count < request.Length) { 
        // add to result list if matches paging criteria 
        result.Add(item); 
       } 
      } 
     } 
    } 
} 
else if (hasDatapoints) {     
    var query = Enumerable.Empty<ArchiveCacheValue>();     
    foreach (var datapoint in request.DatapointIds.OrderBy(c => c)) 
    { 
     var list = ArchiveCacheByDatapoint[datapoint]; 
     numFound += list.Count; 
     query = query.Concat(list); 
    } 
    // execute query just once 
    result = query.Skip(request.Start).Take(request.Length).ToList(); 
} 
else if (hasStations) {     
    var query = Enumerable.Empty<ArchiveCacheValue>(); 
    foreach (var station in request.StationIds.OrderBy(c => c)) 
    { 
     var list = ArchiveCacheByStation[station]; 
     numFound += list.Count; 
     query = query.Concat(list); 
    } 
    // execute query just once 
    result = query.Skip(request.Start).Take(request.Length).ToList(); 
} 
else { 
    // no need to do Count() 
    numFound = ArchiveCache.Count; 
    // no need to Skip\Take here really, ArchiveCache is list\array 
    // so you can use indexes which will be faster 
    result = ArchiveCache.Skip(request.Start).Take(request.Length).ToList(); 
} 

// Number of entries on the current page that will be shown 
int numShown = result.Count; 

私はそれを測定してきましたし、私のマシン上で、それは（時々まで1msの中で実行されます私が試したすべてのタイプのクエリー（セクションだけで、データポイントでのみ、セクションとデータポイントで）、10億アイテム。

Answer 2

arrayまたはvectorの値を少なくともstruct ArchiveRowに保存して、すべてのデータが連続したメモリに保存されていることを確認します。このようにして、locality of reference（L1キャッシュを効率的に使用する）のメリットが大きく得られます。また、list（ポインタ/参照）のオーバーヘッドを避けることもできます。 （更新：List）はすなわち配列（C++ vectorと同じであり、かつC# LinkedListはC++ listと同じ..です少し混乱のように、私はC# Listの迅速な検索をしたが見える - IOW、C# List<>のためここにはポインタのオーバーヘッド。）

構造体をできるだけ小さくするようにしてください。 （自分の価値観に依存する）の代わりにdoubleのdatetime多分floatため、多分32ビット、uint32あるいはuint16可能な場合に使用します。また、最も広い値を構造体の最初に配置してください（整列性を高めるため）。

てもよく、1秒未満で完了しなければならない（全体のアレイ、連続したメモリの数百メガバイトをスキャン）ブルートフォース手法。あなたはバイナリ検索を行うことができ、また、一緒に近い結果セットの値を保持しますた（それがデータベースから選別取得、またはより良い）は、データを並べ替えることができ、さらに最適化するには

。たとえば、sort on StationId、DataPointIdです。

データが大きくなった場合、あなたは（バイナリファイルで）ディスク上の同じ構造を保存し、メモリマッピング経由でアクセスすることができました。

また、あなただけの最初の25の項目をスキャンする必要があります。最後にチェックされた位置（そのセッション/クエリの場合）を保存し、次のページに尋ねられたら、そこから次の25項目まで開始します。これはまた、完全な結果セットを格納するのに必要なメモリを節約するでしょう。

局数が少なく、データがStationIdにソートされている場合、あなたはまた、各StationIdの開始位置と小さなリストまたはジャンプテーブルを（インポート中）維持し、直接データポイントをスキャンするためにそこにジャンプすることができその駅の

---

それがリストに（ 現在約10 100万エントリで）全体のアーカイブ表をロードするのに約9秒かかります。

これをまだ実行していない場合は、リストに最初にCapacityを設定して、複数の再割り当てを避けてください。

Answer 3

EVKの答えはいくつかの良い最適化を持って、私は多分すでにそれをスピードアップするでしょう、それらを取り除く、あなたの元のコードでいくつかの非常に最適化されていない事を指摘したいと思います：

あなたは、メモリ内のクエリを実行します3回！

// execute query first time 
int numFound = query.Count(); 

var result = query.Skip(request.Start == 0 ? 0 : request.Start - 1).Take(request.Length); 

// executing query second time! 
int numShown = result.Count(); 

// executing query third time!  
// result.Select [...] .ToList() 

あなたは本当に一度それを行うと、その結果を集計し、改ページを行う必要があります。

Answer 4

別の最適化。 Linq joinをメモリに使用することは効率的ではありません。

したがって、request.StationIdsとrequest.DatapointIdsに参加する代わりに、それらからハッシュセットを作成し、ハッシュセットを介して単純なcontainsを使用します。このようなもの。両方とも、MaxDegreeOfParallelism = 2と平行バージョンについては250ミリ秒

- アウト、9Mレコード30のステーションIDのsequental方法でそれを実行

if (request.StationIds.Count > 0) 
{ 
    var stationIdSet = new HashSet<int>(request.StationIds); 
    query = (from a in ArchiveCache 
      stationIdSet.Contains(a.StationId) 
      select a); 
       // .AsParallel() 
       // .MaxDegreeOfParallelism(...); 
} 

はおおよそ150と結合行います（結合とハッシュセット）は悪化していました。

：AsParallelは、単純な操作のために最適なオプションではない可能性があるオーバーヘッドを入れています。