时间戳

首页 > 解决方案 > 基于实体等于的嵌套列表到唯一集

java - 基于实体等于的嵌套列表到唯一集

问题描述

我发现了我的 Kruskal 实现的瓶颈。我需要转换一个

List<List<Edge<T extends Comparable<T>>>> adjacencyList;
// This looks like this: get(0) = [Edge:{Vertex V0, Vertex V1, T weight}, Edge:{Vertex V0, Vertex V2, T weight}, ...]
// and get(indexOf(Vertex V1)) = [{Vertex V1, Vertex V0}, ...]
// obviously indexOf(Vertex) does not comply with type Edge, but the idea is that the index of the Edge where the Vertex otherFirst is the getFrom() is retrieved.

到一个唯一的边列表（参见 equals 方法以了解相等性）。我需要对此进行优化，并可能用更有效的解决方案替换。解决方案应如下所示：

get(0) = Edge:{Vertex V0, Vertex V1, T weight}
// there is no element which is Edge:{Vertex V1, Vertex V0, T weight}

我目前的解决方案如下所示：

private List<Edge<T>> toAdjacencyList(final List<List<Edge<T>>> edges) {
    List<Edge<T>> flat = edges.parallelStream().flatMap(List::stream)
        .collect(Collectors.toList());
    final Set<Edge<T>> unique = new HashSet<>();
    unique.addAll(flat);
    return new ArrayList<>(unique);
}

数据缓存后的实际 Kruskal 算法需要不到一秒的时间。

我该如何优化它，或者替换它？

注意：两条边相等意味着 Edge:{V1, V0, 10f} 和 Edge:{V0, V1, 10f} 相同。我很肯定这有效。

标签： javagraph-theory

解决方案

我错误地实现了 equals 方法，但是，如果有人遇到类似问题，我忘记在 hashCode 中包含 Vertex from 和 Vertex to。

推荐阅读