2

2つの配列を含むオブジェクトがあります。最初の配列は勾配配列です。

double[] Slopes = new double[capacity];

次は、さまざまな勾配のカウントを含む配列です。

int[] Counts = new int[capacity];

配列は関連しており、オブジェクトに勾配を追加すると、勾配配列に入力された最後の要素が新しいアイテムとして追加するのではなく、新しいアイテムと同じ勾配である場合、カウントが増加します。

つまり、勾配が15 15 15 12 4 15 15の場合、次のようになります。

Slopes = { 15, 12, 4, 15 }
Counts = {  3,  1, 1,  2 }

Countsインデックスで反復して対応するインデックスを見つけるよりも、スロープでi_thアイテムを見つけるためのより良い方法はありSlopesますか？

編集：多分私の質問が明確でなかったかどうかわからない。発生したi_thスロープにアクセスできる必要があるため、発生するゼロインデックスのi = 3スロープは12です。問題は、新しい構造で対応するスロープを見つけるためのより効率的なソリューションが存在するかどうかです。

たぶん、これは質問をよりよく理解するのに役立つでしょう：これが私が今i_th要素を取得する方法です：

public double GetSlope(int index)
        int countIndex = 0;
        int countAccum = 0;
        foreach (int count in Counts)
        {
            countAccum += count;
            if (index - countAccum < 0)
            {
                return Slopes[countIndex];
            }
            else
            {
                countIndex++;
            }
        }
        return Slopes[Index];
}

もっと効率的な方法があるのだろうか？

4

6 に答える 6

1

一度にスロープをロードし、これらの「i番目のアイテム」ルックアップの多くを実行する場合は、合計を含む3番目の（または使用目的によってはCountsの代わりに）配列を作成すると役立つ場合があります。これは{ 0, 3, 4, 5 }あなたの例です。次に、ルックアップごとにそれらを合計する必要はありません。「Totals[x]とTotals[x+1]の間にあるi」の問題です。スロープバケットが少ないと予想される場合、処理中にスロープが追加される場合、またはこれらのルックアップの多くを実行しない場合は、おそらく何も購入しません。基本的に、これはこれらすべての追加を一度に実行するだけです。

于 2012-02-02T16:52:26.250 に答える
1

繰り返される勾配の最初のインデックスを格納するために、3番目の配列を使用できます

double[] Slopes = new double[capacity];
int[] Counts = new int[capacity]; 
int[] Indexes = new int[capacity];

と

Slopes  = { 15, 12, 4, 15 }
Counts  = {  3,  1, 1,  2 } 
Indexes = {  0,  3, 4,  5 }

Indexesこれで、探しているインデックス以下のインデックスを検索するために、バイナリ検索を適用できます。

O（n）検索パフォーマンスを使用する代わりに、O（log（n））を使用できるようになりました。

于 2012-02-02T16:54:25.700 に答える
1

既存の配列と別の配列（これを呼び出すOriginalSlopes）をいつでもクラスにラップできます。に追加するときは、通常の配列と同じように追加します（つまり、常に追加します）Slopes。スロープOriginalSlopesが必要な場合は、で調べてください。O（1）操作はいたるところにあります。i_thOriginalSlopes

サンプルデータの追加を編集します。

Slopes = { 15, 12, 4, 15 }
Counts = {  3,  1, 1,  2 }
OriginalSlopes = { 15, 15, 15, 12, 4, 15, 15 }
于 2012-02-02T16:54:56.993 に答える
1

countsオブジェクト（またはベース内の配列）で、cumulative countこれまでに見つけたものを持つ変数を追加します。

comparator比較する方法で二分探索を使用するとcumulative count、O（log N）時間の傾きを見つけることができます。

編集

`Data = 15 15 15 12 4 15 15`
Slopes = { 15, 12, 4, 15 }
Counts = {  3,  1, 1,  2 }
Cumulative count = { 3, 4, 5, 7}

たとえば、6番目の位置にある要素を探している場合、Cumulative countデータセットを検索して値5を見つけ、次の値が7であることがわかっている場合、そのインデックスの要素にも6番目の位置の要素があることを確認できます。

二分探索を使用して、log（N）時間で要素を見つけます。

于 2012-02-02T16:56:47.650 に答える
0

編集：キーが勾配であり、各キーの値が対応するインデックスとカウントのリストである辞書を使用できます。何かのようなもの：

class IndexCount
{
    public int Index { get; set; }
    public int Count { get; set; }
}

コレクション宣言は次のようになります。

var slopes = new Dictionary<double, List<IndexCount>>();

次に、値で辞書を検索し、関連するコレクションから各インデックスでのカウントを確認できます。しかし、これはあなたのコードをかなり面白くするかもしれません。パフォーマンスが主な関心事でない場合は、以下のリストアプローチを使用します。

次のように、勾配とカウントを関連付けるタイプの単一のリスト<>を使用できます。

class SlopeCount
{
    public int Slope { get; set; }
    public int Count { get; set; }
}

それから：

var slopeCounts = new List<SlopeCount>();

// fill the list
于 2012-02-02T16:29:27.887 に答える
0

スロープであり、カウントされているDictionary<double, double>のはなぜですか？keyvalue

うーん、ダブルダブル？今、私はコーヒーが必要です...

于 2012-02-02T16:32:34.247 に答える