Java：[性能]存储和搜索<整数，整数>以查找出现最多的一个

Question

我有这个问题，解决它不是问题，更像是最快的方法。因此，我请你们中更有经验的人帮助我找到一个快速的解决方案。

我有人员，每个人员都定义为 1000 到 3000 之间的整数。这些人中的每一个都可以分配给其他人，这看起来像：<整数表示 p2=">这些连接有一些规则，不会超过 10000 个，但至少其中一个而且每对人只能出现一次，所以<1000,2000>和<2000,1000>是不允许的！目前，我将所有这些连接存储在一个链接列表中，其中连接是一个包含两个人的两个整数的类。

然后，我需要找到在所有连接中出现次数最多的人，如果有多个连接，我需要对所有这些连接进行未排序。

之后，我将遍历 LinkedList 并删除这些人参与的所有连接并重做该过程，直到列表为空。

我遇到的一些问题是并发访问或使用错误的地图/列表以及排序方法缓慢。

我目前没有代码，因为我看到了旧代码的性能，现在除了处理输入(女巫已经优化(之外什么都没有;)

对我帮助最大的是有人查看我的案例并告诉我他的经验，即具有不同数据类型的不同解决方案有多快。我想主要自己编写代码，我只需要一些提示如何正确编写代码。

感谢您的关注，并希望得到答复。如果有什么不清楚的地方，我对此表示歉意，并在询问:)

Answer 1

你得到的是一个无向图。即存在一组节点，其连接之间，并且每个连接是双向的。

可以在此处找到四种常见的图形表示形式。

您需要确定哪种表示形式最适合您的需求，以及是否可以对其进行调整以提高性能。

我的建议是使用邻接列表，但让每个节点存储一个包含其链接到的所有节点的列表，以及另一个包含链接到它的所有节点的列表。

例如。

class Node {
    Integer personID;
    List<Integer> links;
}
// graph data type
Map<Integer, Node> graph;

现在，由于数据的存储方式，找出一个人总共有多少连接变得如此简单：

Integer personID = ...;
Node n = graph.get(personID);
int totalConnections = n.links.size();

然后，

您需要做的就是创建一个对象列表，该列表存储人员ID和他们总共有多少个链接，然后按链接总数排序(这将在列表末尾将所有高链接总数分组(。

当然，您必须确保在初始化阶段正确构建图形数据。

要记住的一件事是，这种表示将在一定程度上增加图形的内存复杂性，但会显着降低算法的时间复杂度。您在程序、时间或内存中更看重什么？

但是，根据图中连接的密度，邻接矩阵可能更适合您的需求。

其他问题：

与ArrayList相比，Java中的LinkedList对于大多数任务的性能都非常糟糕。与ArrayList相比，它确实擅长的一件事是，当您通过ListIterator在列表中间进行大量插入/删除时。如果您不使用ListIterator，那么性能将再次变得糟糕。由于 LinkedList 的实现，java Collections API 中的默认排序算法在对 LinkedList 进行排序时性能非常差;

使用 foreach 循环并在循环期间修改集合时，会发生集合 API 的并发访问异常。您需要使用迭代器或列表迭代器循环集合，并通过迭代器/列表迭代器添加/删除元素。

Answer 2

如果空间不是问题，我会使用矩阵来存储连接。

第一个维度是 p1，第二个维度是 p2。我会有一个

boolean[][] connection = new boolean [2001][2001];

(我会从 0 到 2000 考虑(。

当 455 和 985 之间有连接时，我必须检查两个方向。例如：

connection[455][985] = true;
connection[985][455] = true;

如果我想测试两个人之间是否有联系，我会这样做

 if(connection[455][985]) //the other end will have the same values

这会浪费太多空间，但它会非常快速且易于使用。

Answer 3

不要使用 LinkedList，不要使用 2 个元素的整数数组，或者两个字段的特殊类。

class Relation {
    private int id1, id2;
    public Relation(int id1, int id2) {   
         if( id1 > id2 ) {   
             this.id2 = id1;
             this.id1 = id2;
         }
         else {
             this.id1 = id1;
             this.id2 = id2;
         }
    }

    public int hashCode() { 
        return id1 ^ id2;
    }
    public boolean equals(object o) {
        return 
             ((Relation)o).p1 == p1 &&
             ((Relation)o).p2 == p2;
    }
}

最后两种方法用于在需要检查唯一性时使用 HashSet。

然后将所有关系放入HashSet<Relation>，并将它们备份到一些线性结构中，如数组或Vector<Relation>

Answer 4

我在评论中的意思的粗略概述：

人

class Person {
    long id;
    Person(long id) {
        this.id = id;
    }
    @Override
    public boolean equals(Object o) {
        // Compare by id
    }
    @Override
    public int hashCode() {
        // Hash by id
    }
}

连接

class Connection {
    Person person1;
    Person person2;
    Connection(Person person1, Person person2) {
        if (person1.equals(person2)) throw new IllegalArgumentException("Cannot connect a person to itself");
        if (person1.id < person2.id) {
            this.person1 = person1;
            this.person2 = person2;
        } else {
            // The person1 field should contain the person with the smaller id
            this.person1 = person2;
            this.person2 = person1;
        }
    }
    @Override
    public boolean equals(Object o) {
        // Compare person1 and person2
    }
    @Override
    public int hashCode() {
        // Hash person1 and person2
    }
}

连接管理器

class ConnectionManager {
    Set<Connection> connections = new HashSet<Connection>();
    Map<Person, Set<Person>> adjacency = new HashMap<Person, Set<Person>>();
    public void connect(Person p1, Person p2) {
        Connection connection = new Connection(p1, p2);
        if (connections.add(connection)) {
            getAdjacency(p1).add(p2);
            getAdjacency(p2).add(p1);
        } else {
            throw new RuntimeException(String.format("Persons %d and %d are already connected", p1.id, p2.id));
        }
    }
    private Set<Person> getAdjacency(Person person) {
        Set<Person> result = adjacency.get(person);
        if (result == null) {
            adjacency.put(person, result = new HashSet<Person>());
        }
        return result;
    }
    public void disconnect(Person p1, Person p2) {
        if (connections.remove(new Connection(p1, p2))) {
            getAdjacency(p1).remove(p2);
            getAdjacency(p2).remove(p1);
        } else {
            throw new RuntimeException(String.format("No connection between persons %d and %d exists", p1.id, p2.id));
        }
    }
    public Collection<Map.Entry<Person, Set<Person>>> getMostConnected() {
        int maxConnections = 0;
        List<Map.Entry<Person, Set<Person>>> result = new ArrayList<Map.Entry<Person, Set<Person>>>();
        // return all the entries with the maximum size;
        for (Map.Entry<Person, Set<Person>> entry : adjacency.entrySet()) {
            int connections = entry.getValue().size();
            if (connections > maxConnections) {
                result.clear();
                maxConnections=connections;
            }
            if (connections == maxConnections) {
                result.add(entry);
            } 
        }
        return result;
    }

    public Set<Person> getConnections(Person person) {
        return new HashSet(getAdjacency(person));
    }
}

为简洁起见，省略了 Getters/setter 和 equals()/hashCode() 实现 - IDE 为后者生成的任何内容都可以。

此代码本质上是一个矩阵，用邻接列表表示。它唯一不是 O(1( 的部分是搜索具有最多联系的人的部分，即 O(n(。

您可以通过使用保存存储在adjacency映射中的Set<Person>对象的PriorityQueue来降低性能影响，并将设置的大小设置为"优先级"。每当要触摸这样的集合时，请将其从队列中删除，更改它，然后再次插入。(然而，我的预感是，这只会通过使连接和断开人们的速度变慢来更快地获得最紧密联系的人。

免责声明：上面的代码完全未经测试，只是为了让您了解您可以尝试的内容。