すぐにサブアレイを返すことができるソートされた時系列データの最良のデータ構造ですか？

Question

私は基本的にデータポイントのリストであるデータ構造が必要です。各データポイントにはタイムスタンプとデータ値のdouble []があります。特定のタイムスタンプに最も近いポイント、または指定されたタイムスタンプの範囲内のすべてのポイントを取得できるようにします。

私はC＃を使用しています。私の思考は、 "datapoint"がタイムスタンプと二重の[]フィールドを含むクラスである、通常のリストを使用することでした。挿入するには、組み込みのbinarysearch（）を使用して新しいデータを挿入する場所を探し、範囲検索の開始/終了インデックスを再度検索することができます。

ソートリストを最初に試しましたが、インデックスのi = 0,1,2、...、nをキーだけで繰り返すことはできないようですので、範囲検索を行う方法がわかりませんでした何らかの複雑な機能を持たない。

しかし、私はそのリスト<のインサート（）がo（n）であることを知りました。他の場所で犠牲にすることなくそれ以上のことはできませんでしたか？

代わりに、私は1行ですべてのことを行う素晴らしいlinqクエリがありますか？

Answer 1

BCL以外のライブラリを使用したい場合は、C5.SortedArray<T>は常に私にとってはうまく機能しています。

これは、この種の問題で非常にうまくいく、素晴らしい方法RangeFromToを持っています。

Answer 2

お客様は、挿入、取り出し、または取り外しの際の費用を選択できます。これらの各ケースに対して最適化された様々なデータ構造が存在する。 1つを決定する前に、構造の合計サイズ、生成されるデータポイントの数（および頻度）、さらに頻繁に使用される挿入や取り込みを見積もります。

頻繁に新しいデータポイントを挿入すると、LinkedList <>を見ることをお勧めします。より頻繁に取得する場合は、挿入時間が遅いにもかかわらず、リスト<>を使用します。

もちろん、LINQクエリでこれを行うことができますが、これは砂糖コーティングのみであることを覚えておいてください。クエリは毎回実行されるたびに実行され、データポイント全体が一致するものを検索します。これは、まず最初にジョブのための適切なコレクションを使用するよりも高価かもしれません。

Answer 3

実際のデータベースを使用してデータを保存し、それに対してクエリを実行する方法についてはどうですか？ 次に、LINQ-to-SQLを使用できます。

Answer 4

静的データがの場合、IListを実装している構造体は問題ありません。一度ソートし、BinarySearchを使用してクエリを実行します。これは、挿入されたタイムスタンプが常に増加している場合にも有効です。次に、O（1）でList.Add（）を実行するだけで、それでもソートされます。

List<int> x = new List<int>(); 
    x.Add(5); 
    x.Add(7); 
    x.Add(3); 

    x.Sort(); 

    //want to find all elements between 4 and 6 
    int rangeStart = x.BinarySearch(4); 

    //since there is no element equal to 4, we'll get the binary complement of an index, where 4 could have possibly been found 
    //see MSDN for List<T>.BinarySearch 
    if (rangeStart < 0) 
     rangeStart = ~rangeStart; 

    while (x[rangeStart] < 6) 
    { 
     //do you business 
     rangeStart++; 
    } 

あなたの構造にランダムな点で挿入データに必要がある場合、それはソート続けると高速範囲を照会することができ、あなたはB+ treeと呼ばれる構造を必要としています。それはフレームワークに実装されていないので、自分でどこかで取得する必要があります。

レコードを挿入すると、最悪の場合にはO（Nログ）操作を必要

レコードを見つける最悪の場合

の動作は、（先に位置する）レコードを削除する（ログn）Oを必要と必要最悪の場合のO（log n）演算

範囲内でk個の要素が発生する範囲クエリを実行するには、最悪の場合にO（（log n）+ k）回の演算が必要です。

P.S.

私は