java - Java 中最快的变量集

Question

对于这种情况，我需要非常快的结构(Arraylist、LinkedList 等):虽然结构不为空，但我在结构中搜索满足条件的元素，比如说 k，删除满足 k 的元素并重新开始另一个条件，比如 k+1。

例如:

for (int i = 1 ; i <= 1000000; i++) {
  structure.add(i);
}

d = 2;

while (!structure.isEmpty()) {
  for(int boom : structure.clone) {
    if (boom % d == 2) {
      structure.remove(boom);
    }

    d++;
  }
}

Answer 1

如果元素是基元，那么最快的结构很可能是一个专门的基元集合(例如，trove)。遵循盒装原语的引用几乎肯定会导致缓存未命中，这可能会影响成本。

出于同样的原因，我不建议使用 LinkedList:由于缓存未命中，它非常慢。

如果顺序不重要，那么 ArrayList 是完美的。不是删除一个元素，而是用最后一个元素替换它并删除最后一个数组元素。这是一个 O(1) 操作，不会受到空间局部性差的影响。

如果顺序很重要，您可以构建自己的类似 ArrayList 的结构。您不是删除元素，而是将其标记为删除，例如在 BitSet 或 boolean[] 中。最后，您通过将所有元素移动到正确的位置并调整长度来一次性执行删除操作。优化后的循环很可能类似于 CharMatcher.removeFrom loop。 .

一个更简单的解决方案是使用 ArrayList 并将所有幸存的元素复制到另一个元素。我敢打赌它会轻而易举地击败 LinkedList。作为次要的 GC-friedly 优化，您可以使用两个列表。