1

我有一系列 k 节点N1, N2, N3, ...Nk每个节点都被连续命中（可能会跳过）。

每次我访问其中一个节点时，我都需要 += 从前一个节点到达那里所花费的时间。棘手的部分是，如果我在N1 没有到达的情况下返回Nk，那么应该删除这些 += 更新。

一种方法是在每个节点中保留两个量：x 和 y。当我们跳节点时，我们 += 值到 y 中。如果我们到达，N1我们将 y 重置为 0。而如果我们到达Nk，我们x += y对每个节点都这样做。

问题是每次我们击中Nk它都需要一个 O(n) 操作——即使序列返回N1而不击中它可能不是常见的情况Nk。有没有更聪明的方法可以更有效地做到这一点，而无需在每次迭代结束时都“提交”O(n)？

考虑这个有 3 个节点的例子：N_1, N_2, N_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

您可以在每个节点中维护两个累加器 ( )，以及一个在到达第 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 回答