c++ - 如何最小化更新一系列收集数据的节点的成本？

Question

我有一个 k 节点序列 N1 , N2 , N3 , ... Nk每一个都被连续击中(可能会跳过)。

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

一种方法是在每个节点中保留两个量:x 和 y。当我们跳节点时，我们 += values 到 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...

Answer 1

您可以在每个节点中维护两个累加器 (accum_[2])，以及一个全局的 1 位计数器 (k_counter)，它在第 k 个时递增节点到达。然后维护 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];