1

私はk個のノードのシーケンスを持っています、、、N1...N2それぞれN3がNk連続してヒットします（スキップの可能性があります）。

これらのノードの1つにアクセスするたびに、前のノードからそこに到達するのにかかった時間を+=する必要があります。トリッキーな部分は、に到達N1 せずに戻った場合Nk、これらの+=更新を削除する必要があることです。

1つの方法は、各ノードにxとyの2つの量を保持することです。ノードをホップすると、+=値がyになります。到達した場合N1はyを0にリセットしますが、到達Nkした場合はx += y各ノードに対してリセットします。

問題は、ヒットするたびにNkO（n）操作が必要になることです。たとえ、シーケンスがN1ヒットせずに戻るのは一般的なケースではない場合でもですNk。すべての反復が最後に到達するたびにO（n）「コミット」せずに、これをより効率的に行うためのよりスマートな方法はありますか？

3つのノードを持つこの例を考えてみましょう：N_1、、：N_2N_3

左側は反復でヒットしたノードのサブシーケンスを示し、右側は累積カウンターに含まれるべきものを示しています。

(N_1, 2)(N_2, 3)(N_3, 7) ---> (N_1, 2)(N_2, 3)(N_3, 7)
(N_1, 4)(N_3, 2)         ---> (N_1, 6)(N_2, 3)(N_3, 9)
(N_1, 6)(N_2, 3)         ---> (N_1, 4)(N_2, 3)(N_3, 2) //nothing changes as this was an "invalid" op because we never hit the end node
etc...
4

1 に答える 1

2

各ノードに2つのアキュムレータ（）を維持し、k番目のノードに到達するとインクリメントされるaccum_[2]グローバル1ビットカウンタ（ ）を維持できます。次に、各ノードに対して常に正しい累積値を持つk_counter不変量を維持します。accum_[k_counter]このスキームでは、ノードをスキップすると、ノードにアクセスして実行する必要がありnode[i] += 0ます。その要件は、訪問カウンターを使用して最適化することができます。これは演習として残しておきます:-)。

enum { K = 100 };
struct Node *node;
struct Node {
    static bool k_counter;
    unsigned accum_[2];
    unsigned id_;
    Node () : accum_(), id_(this - node + 1) {}
    void operator += (unsigned time_data) {
        accum_[!k_counter] = accum_[k_counter] + time_data;
        if (id_ == K) k_counter = !k_counter;
    }
    operator unsigned () const { return accum_[k_counter]; }
};
bool Node::k_counter;

node = new Node[K];
于 2012-06-27T05:22:25.997 に答える