8

在下面的代码中，我需要从 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（垃圾收集）影响最快速地执行？

我的直觉（在撰写这个问题之后）是使用 Iterator 的第二种技术执行速度更快，GC 开销更低。鉴于我不知道传递的 Set 的实现（假设最有可能是 HashSet 或 LinkedHashSet），每个 toArray() 或 iterator() 方法会产生多少开销？对此的任何见解将不胜感激。

问题（从上面重复）：

  1. 哪种技术，toArray() 或 iterator()，最有可能以最小的 GC（垃圾收集）影响最快速地执行？
  2. 鉴于我不知道传递的 Set 的实现（假设最有可能是 HashSet 或 LinkedHashSet），每个 toArray() 和 iterator() 方法会产生多少开销？
4

5 回答 5

9

toSearch.iterator().next()因为它不需要复制任何数据，所以会更快且内存占用更少，而toArray会将集合的内容分配并复制到数组中。这与实际实现无关：toArray将始终必须复制数据。

于 2010-12-04T23:57:19.467 回答
1

据我所知，您正在做广度优先搜索

下面是如何在不使用 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) 时间内的问题。

干杯

于 2010-12-05T00:11:01.893 回答
1

这是我如何实现的：

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. 使用LinkedListfortoSearch意味着有一种简单的方法可以一次性获取元素并删除它。
  3. Set.add(...)我们可以使用返回 a的事实boolean来获得集合中的查找次数result...与 using 相比Set.contains()。
  4. 最好使用HashSet而不是LinkedHashSet结果......除非您需要知道填充添加坐标的顺序。
  5. ==用于比较Value实例可能有点狡猾。
于 2010-12-05T13:28:06.757 回答
0

在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() 方法的实现可能会在返回答案之前对内容进行全面扫描。那么，将此方法与我最初发布的方法进行比较，这可能更有效（在我去花大量时间进行实证测试之前）？

于 2010-12-05T01:10:56.917 回答
0

好的，下面是我最新的实现，其中包含反馈（主要来自 Stephen、Cameron 和 Petro），其中包括完全消除 toArray()[]-vs-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 获得可靠的可重复性，同时解决错误和性能问题 (http://stackoverflow.com/questions/2704597/iteration-order-of-hashset)。一旦稳定，我可能会恢复到更快的 HashSet 实现。
  3. 在“是值”测试之前重新排序“检查是否已评估”测试，以仅访问每个坐标一次。这避免了多次重新访问 !value 相邻坐标。还结合了斯蒂芬对 Set add() 方法的巧妙双重使用。这变得非常重要，因为洪水区域变得更像迷宫（蛇/蜘蛛）。
  4. 保留“==”以检查强制参考比较的值。值被定义为 Java 1.5 枚举，我不想依赖 HotSpot 来内联 .equals() 方法调用并将其简化为参考比较。如果 Value 从 Enum 改变，这个选择可能会回来咬我。Tyvm 感谢 Stephen 指出这一点。

Petro 和 Stephan 的解决方案只访问一次包含 value 的坐标，但需要多次重新访问包含 !value 的坐标，这可能导致对由长迷宫般的隧道组成的区域进行大量重复的提取/值检查。虽然“长迷宫般的隧道”可能被认为是一种病态的情况，但它更典型地代表了我需要这种方法的特定领域。我的“第二个”尝试解决方案（它的 LinkedList contains() 调用性能很差）作为一个真正的答案值得怀疑（在那个问题上向 Stephen 点头）。

感谢您的所有反馈。

接下来，在数亿次调用中对单个变体/更改进行大量经验测试。我会在这个周末的某个时候更新这个答案的细节。

于 2010-12-07T04:54:51.783 回答