1

短縮版：

値の変更の実行が点在する重複値の実行に存在する多数の重複値（double）を含むListオブジェクトがあります。インデックスと値の関連付けを損なうことなく、このListオブジェクトが占めるメモリ内のスペースを減らしたいと思います。また、インデックスをルックアップとして使用して、O（1）アルゴリズムのルックアップ時間をできるだけ近く維持したいと思います。たとえば、要素{0、0.1、0.1、0.1、0.2}を含むリストがある場合、インデックス1、2、または3を指定すると、新しいオブジェクト/エンティティは常に0.1を返します。独自のオブジェクトを作成する（おそらくIListを実装する）か、既存のオブジェクトを使用します。アルゴリズムをO（log（m））にするこれを実装する方法についてのアイデアがあります。ここで、mは同じ値の実行数です（私の例では、実行は1回だけです）。しかし、私は可能であれば自分自身を転がしたくありません。

そのようなオブジェクトはC＃用に存在しますか、それとも自分でロールする必要がありますか？

モチベーション/ロングバージョン：

私はいくつかの重い科学的計算を行っているデスクトップアプリケーションを持っています。計算により大量のデータが生成され、そのデータは時間に基づいて編成されます。つまり、時間50の場合、変数x、y、およびzの値があります。時間51の場合、変数x、y、およびzの別の値があります。計算が実行されたすべての時間を含むリストがあります。各変数にはリストがあり、そのインデックスはタイムズリストのインデックスと同じです。つまり、時間配列のインデックス234を見ると、46（秒）の時間が得られる可能性があります。時間46（秒）での各変数の計算は、その変数のリストのインデックス234で見つかります。

そのような変数は約100,000個（したがって100,000個のリスト）ありますが、リストは1回だけです。さらに多くの変数を追加することも期待しています。これは明らかにメモリの問題です。（現時点では少なくとも約200 MBのrawスペース:-)）。これは、特定の時間に特定の変数の値を見つける方法としてインデックスを使用したい理由も説明する必要があります。

変数の最初のx個のスロットに0しか含まれないのはかなり一般的です。または、インデックスyの後、変数は最後まで一定に保たれます。値が一定である期間数の最悪のケースは、単一のリストでは約30ですが、より一般的には2〜5です。各配列の合計値の数は通常約250です。

編集：

100,000を超える変数を追加することを期待しているため、これは200MBよりも大きな問題であることに注意してください。この動機の詳細を説明するために、私のアプリは現在約1 GB以上で実行されており、200MBはメモリ使用量を削減するための手間のかからない成果であると考えました。

EDIT2：

説明の非常に重要な編集に気づきました。上記で編集し、ここでも説明しました。リストには実行が含まれている場合がありますが、値がインデックスごとに変化するセクションもあります。だから私が持っているかもしれないリストのより良い例は次のとおりです：

0 0 0 0 0 0 ....（50個の重複する0）... 0.1 0.2 0.4 0.5 0.6 ...（50個の重複する値）... 200.45 200.45 200.45 200.55 ...（50個の重複する値）.. ..など

4

2 に答える 2

5

O（log（m））のアイデアは、基本的に、インデックス範囲を使用して結果を並べ替えて、バイナリ検索ツリーを作成することだと思います。

私は絶対にその解決策を採用します。リストごとに最大約30回の実行しかない場合は、特に大きくなることはないためm、スケーリングの方法について心配する必要はありません。m検索ツリーアプローチよりも実際のケース。

実際、私はおそらく最初に実行の単純なリスト（各実行はインデックス範囲と値）とO（m）ルックアップを探します...通常のサイズが2〜5の場合、それは特に悪いことであり、実装が簡単になります。簡単なアプローチが機能するようになったら、最適化できます。

実際、私はこの「実行」バージョンを最初からまったく実行せずに開始します。特に限られた携帯電話でこれを実行する必要がない限り、200MB程度は実際にはそれほど大きなデータセットではありません。アプリケーションは実際にどのマシンで実行されますか？たとえば、アプリケーションに0.5ギガバイトの余裕がないと信じる理由はありますか？

また、バイナリ検索ツリーまたは実行リストのオーバーヘッドは、とにかく期待するほど節約できないことを意味する可能性があることも覚えておく価値があります。

基本的に、私はこの順序で実装します：

  • 配列
  • 実行のリスト
  • 二分探索木

各ステップでパフォーマンス（時間とスペース）をベンチマークし、何が十分に良いかについて具体的な目標があることを確認します。

編集：編集されたバージョンでは、次のようなインターフェイスが必要になる場合がありますIPortion。

int MinIndexInclusive { get; }
int MaxIndexExclusive { get; }
double FindValue(int index);

2つの実装で：ArrayPortionとTreePortion。の各ノードにはTreePortion左側と右側があり、それぞれが別のものでした。たとえば、内に埋め込むIPortionことができます。ArrayPortionTreePortion

または、もう少し簡単に、フラットに保ち、List<IPortion>それぞれが単一の値とそのインデックス境界についてのみ知っている、またはのIPortionいずれかである場所を設定することもできます。次に、リストでバイナリ検索を実行して適切な部分を見つけ、インデックスの値を尋ねることができます。ArrayPortionRunPortionRunPortion

于 2013-03-25T19:35:11.427 に答える
1

List<T>とバイナリ検索でこれを行うことができるように私には思えます。実行のリストを保存する必要はありません。本当に保存する必要があるのは、時間が変化したときのインデックスと値だけです。

したがって、単純な構造体があります。

struct ValueChange
{
    public int TimeIndex;  // or whatever type you use for the index
    public double Value;
    // Add constructor here
}

（はい、構造体の可変値が悪いことを知っています。簡潔にするために、このようにコーディングしました。実際のコードでは、これらはプライベートバッキングフィールドを持つ読み取り専用プロパティになります。）

次に、がありList<ValueChange>ます。値が変更されるたびに、それらの1つをリストに追加します。値が簡単に変更されたかどうかを確認できます。

if (currentValue != theList[theList.Count-1].Value)
{
    theList.Add(new ValueChange(timeIndex, currentValue));
}

また、特定の時間インデックスでの値を知りたい場合は、時間インデックスの二分探索を行います。探しているインデックスがない場合、の戻り値は、List.BinarySearch探している値を含むアイテムのインデックスを示します。

もちろん、あらゆる種類のランレングス圧縮の欠点は、短期間の実行ではコンプレッサーではなくデータエクスパンダーに変わることです。この特定のケースでは、損益分岐点を達成するために、全体のランレングス平均が2である必要があります。つまり、N期間の値を表す場合、ValueChange構造はのサイズの2倍であるため、N/2を超える値の変更を行うことはできませんdouble。

于 2013-03-25T20:28:50.403 に答える