algorithm - 有效地聚合删除和插入索引

Question

我有一个用于更新 UI 的类型。这是它的伪代码。

{
  Item[] AllItems;
  long[] ItemsRemovedFromPreviousUpdateByIndex;
  long[] ItemsAddedToPreviousUpdateByIndex;
}

这些更新相当频繁，并且包含大量数据。我们希望聚合这些实例并每 200 毫秒向 UI 提供一次更新。每 200 毫秒窗口可能有 20 或 30 次更新。

我的问题是是否有聚合指数的好方法。我想不出不分配大量内存的方法。

Answer 1

我会尝试将该数据存储在一对 int 中小号，long s，或 BigInteger s，取决于你有多少索引。

首先考虑做这样的事情:

boolean[] added = new boolean[allItems.length];
boolean[] removed = new boolean[allItems.length];

当且仅当未添加/删除相应索引处的项目时， bool 值才为真。

但是我不会这样做，而是尝试将 bool 数组表示为 long，或者如果需要的话，一个 BigInteger。因为，tttfftfftf --> 1110010010 --> 914。

您可以研究将单个位从 0 翻转到 1 的方法，如果它已经是 1，则不要管它。你需要在你的 init 案例中聪明一点，因为你从全 0(即 0)开始并且第一个索引可能很大，所以你需要从 0 开始。至 10...0一步，就是1 << n .如果您需要在 j > n 处翻转位，则从那里您只需翻转单个位，并可能进行移位。其中 n来自上面提到的初始化案例。

请记住，您始终需要知道 allItems 的长度每次重置时的数组，因为 00001001与1001相同，所以如果长度是 8，你应该解释 1001作为00001001 .