在Java（1.5或更高版本）中，从Set中获取（任何）元素的最佳性能方式是什么？

Question

在下面的代码中，我需要从toSearch中获取一个元素，任何元素。我无法找到Set接口定义中有用的方法来仅返回集合中的单个（随机的，但不要求是随机的）成员。因此，我使用了toArray（）[0]技术（在下面的代码中出现）。

private Set<Coordinate> floodFill(Value value, Coordinate coordinateStart)
{
    Set<Coordinate> result = new LinkedHashSet<Coordinate>();

    Set<Coordinate> toSearch = new LinkedHashSet<Coordinate>();
    toSearch.add(coordinateStart);
    while (toSearch.size() > 0)
    {
        Coordinate coordinate = (Coordinate)toSearch.toArray()[0];
        result.add(coordinate);
        toSearch.remove(coordinate);
        for (Coordinate coordinateAdjacent: getAdjacentCoordinates(coordinate))
        {
            if (this.query.getCoordinateValue(coordinateAdjacent) == value)
            {
                if (!result.contains(coordinateAdjacent))
                {
                    toSearch.add(coordinateAdjacent);
                }
            }
        }
    }

    return result;
}

我看到的另一种技巧是将"(Coordinate)toSearch.toArray()[0]"替换为"toSearch.iterator().next()"。使用toArray()还是iterator()，哪个技术最可能以最快的速度执行并对GC（Garbage Collection）影响最小？

我的直觉（在撰写本问题后）是使用迭代器的第二种技术在执行速度和GC开销方面都更快。鉴于我不知道传递的Set的实现（假设为HashSet或LinkedHashSet最有可能），在toArray()方法和iterator()方法中分别会产生多少开销？任何相关见解都将不胜感激。

问题（从上面重复）：

1.使用toArray()还是iterator()，哪个技术最可能以最快的速度执行并对GC（Garbage Collection）影响最小？ 2.鉴于我不知道传递的Set的实现（假设为HashSet或LinkedHashSet最有可能），在toArray()方法和iterator()方法中分别会产生多少开销？

- chaotic3quilibrium

Answer 1

toSearch.iterator().next() 会更快、更省内存，因为它不需要复制任何数据，而 toArray 则需要分配并复制集合中的内容到数组中。这与实际的实现无关：无论如何，toArray 都必须复制数据。

- Cameron Skinner

---

这对我来说很有道理。进一步准确地假设，当toArray()生成数组时，它很可能使用完全相同的迭代器实现来填充它，这是否更加准确？如果是这样，那么迭代器方法显然是首选。 - chaotic3quilibrium

它可能会或可能不会使用迭代器来填充数组。ArrayList 可能不会 - 它可以使用 System.arrayCopy 进行快速复制。无论如何，如果可以避免复制数据，就不要复制。 - Cameron Skinner

对我来说很难相信我是第一个遇到这个困境的人。如果Set接口定义了一个方法，例如iteratorFirstElement()，它的默认实现为iterator().next()，那就太好了。但事实上，我不得不在我的代码库中到处放置这个片段。呸！ - chaotic3quilibrium

你不是第一个遇到这个问题的人 :) 不过在你的情况下，@Petro说得对：你可以用一个Queue替换Set来避免这个问题。你可以使用一个Set来保存已访问的节点以避免循环，并使用一个Queue来保存打开的节点集合。 - Cameron Skinner

Answer 2

从我所看到的，你正在进行广度优先搜索。

以下是一个示例，演示如何在不使用toArray的情况下实现它：

    private Set<Coordinate> floodFill(Value value, Coordinate coordinateStart) {
    final Set<Coordinate> visitedCoordinates = new LinkedHashSet<Coordinate>();
    final Deque<Coordinate> deque = new ArrayDeque<Coordinate>();

    deque.push(coordinateStart);

    while (!deque.isEmpty()) {
        final Coordinate currentVertex = deque.poll();
        visitedCoordinates.add(currentVertex);
        for (Coordinate coordinateAdjacent : getAdjacentCoordinates(currentVertex)) {
            if (this.query.getCoordinateValue(coordinateAdjacent) == value) {
                if (!visitedCoordinates.contains(coordinateAdjacent)) {
                    deque.add(coordinateAdjacent);
                }
            }
        }
    }

    return visitedCoordinates;
}

实现说明：

我现在担心 LinkedList 上的 contains() 方法的实现可能会在返回答案之前对内容进行全面扫描。

你对全面扫描（又称线性搜索）是正确的。尽管如此，在你的情况下，可以有一个额外的集合来跟踪已经访问过的顶点（顺便说一下，这实际上就是你的结果！），这将在 O(1) 的时间内解决 contains 方法的问题。

干杯

- Petro Semeniuk

---

我只是复制了这个方法，并使用Queue<Coordinate>重新实现了它：toSearch = new LinkedList<Coordinate>(); 然而，通过这样做，我失去了add()自动进行的“重复消除”功能，当成员已经存在时。因此，我不得不添加一个额外的if(!toSearch.contains(coordinateAdjacent))语句，以防止元素在队列中重复出现。没有测试，感觉我使这个方法更加昂贵了（LinkedList上contains()方法的速度有多快（我多年前的记忆是非常差的）。 - chaotic3quilibrium

我将使用队列重新实现，并作为答案发布。 - chaotic3quilibrium

不错的实现。问题是：为什么你使用Deque而不是Queue？我没有理解到微妙的优势吗？ - chaotic3quilibrium

好问题。我认为在这种特殊情况下没有优势。Deque支持在两端插入和删除元素（与队列相反）。当我需要堆栈/队列时，我通常使用这个通用接口。你可以安全地在这里使用队列。干杯。 - Petro Semeniuk

Petro，再问一个问题 - 为什么频繁使用 final 关键字？我记得在其他地方看到过，现在被认为这样做是“不良实践”，因为 JVM 可以通过路径分析推断出大部分的假设。我准备测试不同版本的重写（我刚刚将重写发布为一个名为 floodFind3 的方法的答案）。所以，如果你认为我添加 final 会影响性能，那我会把它加入到我的实证测试中。 - chaotic3quilibrium

我认为我无法在路径分析方面比JVM更聪明，final关键字不是为了JVM而存在的，而是为了我自己 :-）。我喜欢拥有不可变对象的想法。如果你感兴趣，可以查看我借鉴的演示文稿，其中包括尽可能多地使用不可变性的想法。## 持久化数据结构和管理引用。http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey ## Google Collections Library for Java（1/2）。http://www.youtube.com/watch?v=ZeO_J2OcHYM。## Google Collections Library for Java（2/2）。http://www.youtube.com/watch?v=9ni_KEkHfto## - Petro Semeniuk

Answer 3

这是我如何实现它的：

private Set<Coordinate> floodFill(Value value, Coordinate start) {
    Set<Coordinate> result = new LinkedHashSet<Coordinate>();
    LinkedList<Coordinate> toSearch = new LinkedList<Coordinate>();
    toSearch.add(start);
    do {
        Coordinate coordinate = toSearch.removeFirst();
        if (result.add(coordinate)) {
            for (Coordinate ajacent: getAdjacentCoordinates(coordinate)) {
                if (this.query.getCoordinateValue(adjacent) == value) {
                    toSearch.add(adjacent);
                }
            }
        }
    } while (!toSearch.isEmpty());
    return result;
}

注意：

1. 如果你思考一下，toSearch 数据结构不需要包含独特的元素。
2. 使用 LinkedList 作为 toSearch，意味着有一个简单的方法可以一次性获取并删除一个元素。
3. 我们可以利用 Set.add(...) 返回一个布尔值的事实来对比使用 Set.contains() 在 result 集合中进行查找的次数。
4. 最好使用 HashSet 而不是 LinkedHashSet 来存储结果...除非您需要知道填充时添加坐标的顺序。
5. 使用 == 比较 Value 实例有潜在的问题。

- Stephen C

---

不错！关于第5点“使用==比较值可能有些危险。”- 值是一个枚举。我可以将其转换为equals()，只要HotSpot内联了代码，它应该会得出相同的比较结果（根据我对枚举如何实现的理解）。 - chaotic3quilibrium

关于第四点，我使用LinkedHashSet以便实现“可重现性”。HashSet的iterator()没有排序约束，这使得在发现问题时重新创建精确上下文非常困难。 - chaotic3quilibrium

1. 如果只是使用 ==，那么对 Value.equals(...) 的调用将被内联。
2. HashSet 迭代器不可重现的事实表明 Coordinate 没有重载 equals 和 hashCode。这意味着 getAdjacentCoordinates 对于给定的坐标必须始终返回相同的坐标对象实例。

- Stephen C

我想看一些示例代码。此外，接受的答案确认我的理解……HashMap 本身并没有任何非确定性因素。 - Stephen C

@chaotic3equalibrium - 确保这些测试使用具有相同哈希码的对象在不同运行中（例如，没有可能在不同运行中不同的identityHashCode），并且它们按照相同的初始大小/负载因子的顺序添加到/从干净的哈希集中。 在这些条件下，迭代顺序应该是可重复的，并且理论上是可预测的。（或者，阅读并理解HashMap / HashSet的源代码。） - Stephen C

Answer 4

在 Petro 的回复后，我按照他的建议复制了这个方法并重新实现了它。它现在看起来是这样的：

private Set<Coordinate> floodFind2(Value value, Coordinate coordinateStart)
{
    Set<Coordinate> result = new LinkedHashSet<Coordinate>();

    Queue<Coordinate> toSearch = new LinkedList<Coordinate>();
    toSearch.add(coordinateStart);
    while (!toSearch.isEmpty())
    {
        Coordinate coordinate = toSearch.remove();
        result.add(coordinate);
        for (Coordinate coordinateAdjacent: getAdjacentCoordinates(coordinate))
        {
            if (getCoordinateValue(coordinateAdjacent).equals(value))
            {
                if (!result.contains(coordinateAdjacent))
                {
                    if (!toSearch.contains(coordinateAdjacent))
                    {
                        toSearch.add(coordinateAdjacent);
                    }
                }
            }
        }
    }

    return result;
}

通过从Set到Queue的转换，我的效率问题转移到了我必须添加的新条件检查：“if (!toSearch.contains(coordinateAdjacent))”。使用Set接口，它会默默地阻止我添加重复项。使用Queue接口，我必须检查以确保我没有添加重复项。

现在我担心LinkedList上contains()方法的实现可能会在返回答案之前扫描整个内容。因此，在进行经验测试之前，将这种方法与我最初发布的方法进行比较，哪种方法更有效？

- chaotic3quilibrium

---

看起来这个问题可能比我最初想象的要常见一些：https://dev59.com/OXE95IYBdhLWcg3watQ3 - chaotic3quilibrium

在没有经验的情况下，很难说哪种变体会更快。首先，这取决于数据分布的方式。toSearch.contains()是否可以快速找到项目，还是更经常地搜索列表？ - Andrew Eisenberg

这是一个答案吗？在我看来，它不像一个答案。 - Stephen C

我建议您还应该维护一个已探索节点的“Set”。如果您有4个节点A、B、C和D，它们形成一个正方形（即A->B、B->C、C->D、D->A以及反向边），那么您当前的实现将进入无限循环。您可以在访问每个节点时将其添加到已探索集合中，并检查新邻居是否已经被探索。这两个操作都是使用“HashSet”常数时间完成的。 - Cameron Skinner

哦！我刚注意到 if (!result.contains(...)) 那一段。忽略上一个评论。 - Cameron Skinner

Answer 5

好的，以下是我的最新实现，包括来自Stephen、Cameron和Petro的反馈（主要是消除toArray()[]与interator().next()之间的冲突）。我已经添加了注释以更准确地区分正在发生的事情以及原因。为了更好地阐明为什么我具体实施了Petro的原始“使用跟踪集”建议（由Cameron提出）。在代码片段之后，我将与其他提出的解决方案进行对比。

private Set<Coordinate> floodFind3(Coordinate coordinate)
{
    Set<Coordinate> area = new LinkedHashSet<Coordinate>(); //includes only area of value (which is the same as at coordinate)

    area.add(coordinate);
    Value value = getCoordinateValue(coordinate); //value upon which to expand area
    Set<Coordinate> checked = new LinkedHashSet<Coordinate>(); //every coordinate evaluated regardless of value
    checked.add(coordinate);
    Queue<Coordinate> candidates = new LinkedList<Coordinate>(); //coordinates evaluated, were of value, and are queued to iterate through their adjacents
    candidates.add(nordinate);
    while (!candidates.isEmpty())
    {
        for (Nordinate coordinateAdjacent: this.query.getNordinates().getAdjacent(candidates.remove()).getOrthogonal())
        {
            if (checked.add(coordinateAdjacent)) //only expands containing value and !value
            {
                if (getCoordinateValue(coordinateAdjacent) == value)
                {
                    area.add(coordinateAdjacent); //only expands containing value
                    candidates.add(coordinateAdjacent); //expands and contracts containing value
                }
            }
        }
    }

    return area;
}

我已经对这个方法进行了几个重要的更新：

1. 少了一个方法参数：我删除了一个参数，因为它可以从搜索中推导出来，并消除了可能存在的逻辑问题，即起始坐标指向包含!value的位置。
2. 三个集合跟踪搜索；区域（Set）、已检查（Set）和候选人（Queue）。代码注释澄清了每个集合的具体用途。在追踪错误和性能问题时使用LinkedHashSet以保证可靠的再现性（https://dev59.com/Z3E85IYBdhLWcg3wl0nF）。一旦稳定，我可能会恢复到更快的HashSet实现。
3. 将“检查是否已评估”测试重新排序到“是值”测试之前，以仅访问每个坐标一次。这避免了多次重新访问!value相邻坐标。还采用了Stephen聪明的双重使用Set add()方法。随着洪水泛滥的区域变得更加迷宫化（像蛇/蜘蛛），这变得非常重要。
4. 保留“==”用于检查值，强制引用比较。Value被定义为Java 1.5枚举，我不想依赖HotSpot同时内联.equals()方法调用并将其减少为引用比较。如果Value从枚举中更改，这个选择可能会让我后悔。感谢Stephen指出这一点。

Petro和Stephan的解决方案只访问包含值的坐标一次，但需要多次重新访问包含!value的坐标，这可能会导致由长迷宫般的隧道组成的区域出现相当多的重复获取/值检查。虽然“长迷宫般的隧道”可能被认为是一种病态情况，但它更典型于我需要这种方法的特定领域。而我的“第二个”尝试的解决方案（其中包含了性能较差的LinkedList contains()调用）在实际答案中是有问题的（{nod}向Stephen表示感谢）。

感谢您所有的反馈。

接下来，进行大量的经验测试，对数亿次调用进行单一变化/更改。我将在本周末更新此答案的详细信息。

- chaotic3quilibrium

---

由于您从图形开始构建树，我建议使用TreeSet来进行排序。顺序得到保证。 - Petro Semeniuk

Petro，有趣。我会去看看它对性能的影响如何。 - chaotic3quilibrium

通常在搜索/检查/插入操作中，您将获得O(log(N))。 HashSet更便宜，并且对于所有这些操作都具有O(1)。 N越大，性能差异越小。 - Petro Semeniuk

经过多种不同的配置测试，结果表明Stephen C的实现比其他任何解决方案的变体都快4-12％。 - chaotic3quilibrium