3

我需要一个类为原始元素中的每个元素HidingList实现一个List位置的视图，有点说它是否应该包含在视图中。简单的解决方案是使用 a ，但是如果列表变大BitSet，我看不到如何实现的简单有效的方法。hidingList.get(int index)就像是

public T get(int index) {
    int realIndex = bitSet.nextSetBit(0);
    for (int i=0; i<index; ++i) {
        realIndex = bitSet.nextSetBit(realIndex+1);
    }
    return delegate.get(realIndex);
}

看起来效率不高，我看不到像bitSet.cardinality(int from, int to). 也许在番石榴或其他地方已经有我需要的东西了？

4

3 回答 3

0

如果您想get(int)提高效率（即平均优于 O(N)），可以将位图替换为整数数组，其中索引表示视图列表的索引，索引处的值表示原始列表中的元素。

但是，除非您想set(int, T)写入原始列表（或类似的东西），否则您最好创建一个新列表而不是视图。

于 2012-09-20T13:36:19.060 回答
0

您可以使用二进制搜索并Integer.bitCount至少在位数上实现对数时间复杂度（而您的解决方案在 O(n) 中）。首先，所有位的一半为 0。用于Integer.bitCount检索 1 的数量（此操作通常映射到机器指令，因此非常快）。如果检索到的数字大于您的索引，则仅将一半字节归为 0，如果较小，则将更多字节归零（通常的二进制搜索）。这将允许您以对数步数找到位置。

例如，我们在两个字节数中寻找索引 4（即第 5 个元素）0010 1010 1110 1001

第一步： 0010 1010 1110 1001b = 8 > 5，清空所有字节的一半

第二步：0010 1010 0000 0000b = 3 < 5，仅空出 4 个字节

第三步：0010 1010 1110 0000b = 6 > 5，再清空两个字节

第四步：0010 1010 1100 0000b = 5 == 5，所以答案肯定在剩下的两个字节中。再空出一个 -> b = 4 -> 搜索到的位置必须是第 10 个字节。

尽管如此，维护索引列表会更快，但需要更多内存。除非您处于嵌入式设置中，否则内存不是一个太大的问题，您应该使用此解决方案。

于 2012-09-20T13:45:13.337 回答
0

不同结构的效率很大程度上取决于您的访问模式。例如，相对于可见性更改的次数，隐藏列表的索引读取频率如何？

平均而言（假设可见性更改相对不频繁或可以批量更改） - 我的建议是创建一个新列表，该列表是原始列表的副本，其中隐藏元素已删除。原因：

  • 您可以在 O(n) 时间内构建整个事物，每个项目只需 O(1)。
  • 您可以保持 O(1) 访问，因为新列表将支持直接索引访问。扫描一个位集是 O(n)，这对于大型列表上的索引访问来说将是可怕的！
  • 你可以让它不可变。不变的东西是好的。

否则，如果您希望能够在任意时间打开或关闭每个列表项的可见性，您可能需要实现自定义数据结构。使用二叉树可以获得 O(log n) 的隐藏、取消隐藏和索引查找性能。然而，我不知道有任何现有的实现 - 这是一个不寻常的要求！

于 2012-09-20T14:25:03.997 回答