Java: [Производительность] Сохранение и поиск в <Integer, Integer> наиболее часто встречающемся

Question

У меня есть эта проблема, и ее решение не является проблемой, больше похоже на то, как это сделать быстрее всего. Поэтому я прошу более опытных из вас помочь мне найти быстрое решение.

У меня есть Люди, каждый из которых определен как целое число от 1000 до 3000. Каждый из этих людей может быть назначен кому-то еще, это будет выглядеть так: Есть несколько правил для этих соединений, их будет не более 10000, но хотя бы одно из них и каждая пара людей может встречаться только один раз, поэтому <1000,2000> и <2000,1000> не допускаются! В данный момент я храню все эти соединения в LinkedList, где Connection - это класс, содержащий два целых числа двух людей.

Затем мне нужно найти человека, который встречается чаще всего во всех соединениях, если их больше одного, мне нужно было бы все они не отсортировать.

После этого я буду перебирать LinkedList и удаляю все соединения, в которых участвовали эти люди, и повторяю процесс, пока список не станет пустым.

Некоторые проблемы, с которыми я столкнулся, - это «Согласованный доступ» или использование неправильных карт / списков и медленный метод сортировки.

У меня нет кода на данный момент, так как я увидел производительность своего старого и начал с нуля, и теперь ничего другого, кроме обработки ввода (ведьма уже оптимизирована);)

Что может помочь мне больше всего, так это то, что кто-то смотрит на мой случай и рассказывает мне, как быстро работают разные решения с разными типами данных. Я хочу писать код в основном сам, мне просто нужны советы, как это сделать правильно.

Спасибо за внимание и, надеюсь, за ответ. Если что-то неясно, я прошу прощения за это и уточню, спросив:)

Answer 1

Если мы посмотрим на это объектно-ориентированным способом, мы можем заставить каждого Человека хранить Список своих друзей:

class Person {
    private Set<Person> friends = new HashSet<>();

    public void addFriend(Person newFriend) {
        friends.add(newFriend);
        newFriend.friends.add(this);
    }

    public void removeFriend(Person oldFriend) {
        friends.remove(oldFriend);
        oldFriend.friends.remove(this);
    }

    public int numberOfFriends() {
        return friends.size();
    }

    public void disappear() {
        for (Person friend : friends) {
            friend.friends.remove(this);
        }
    }
}

Преимущество этого подхода состоит в том, что все операции завершаются в постоянном ожидаемом времени.

Это намного лучше, чем ведение связанного списка друзей, где для определения количества друзей одного человека требуется, чтобы мы просмотрели список всех 10000 друзей.

Это также значительно быстреечем двумерный массив, описанный rogelware, где для определения количества друзей требуется проверка всех 2000 других людей на дружбу, а удаление человека требует очистки дружбы для всех 2000 других людей.

Answer 2

У вас есть неориентированный граф. То, что существует множество узлов с соединениями между собой, и каждое соединение двунаправленное.

Существует четыре общих представления для графиков, которые можно найти здесь .

Вам необходимо решить, какое представление лучше всего соответствует вашим потребностям и можно ли его адаптировать для повышения производительности.

Я рекомендую использовать списки смежности, но каждый узел должен хранить один список всех узлов, на которые он ссылается, и другой список всех узлов, которые на него ссылаются.

например.

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();

Все, что вам тогда нужно, это создать список объектов, в которых будет храниться как идентификатор человека, так и общее количество ссылок, которые у них есть, а затем отсортировать по общему количеству ссылок (что сгруппирует все большое количество ссылок в конце списка ).

Вы, конечно, должны убедиться, что данные графика правильно построены на этапе инициализации.

Следует иметь в виду, что это представление несколько увеличит сложность памяти вашего графа, но значительно уменьшит временную сложность вашего алгоритма. Что вы цените больше в своей программе, времени или памяти?

Однако, в зависимости от плотности соединений в вашем графике, матрица смежности может лучше соответствовать вашим потребностям.

Другие вопросы:

LinkedList в Java имеет довольно ужасную производительность для большинства задач по сравнению с ArrayList. По сравнению с ArrayList он лучше всего работает, когда вы делаете много вставок / удалений в середине списка с помощью ListIterator. Если вы не используете ListIterator, то производительность снова ужасна. Из-за реализации LinkedLists алгоритм сортировки по умолчанию в API java Collections имеет очень низкую производительность при сортировке LinkedLists;

Одновременные исключения доступа с API коллекций возникают при использовании цикла foreach и изменении коллекции во время цикла. Вам нужно перебрать коллекцию с помощью Iterator или ListIterator и добавить / удалить элементы через Iterator / ListIterator.

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
    }
}

ConnectionManager

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));
    }
}

Получатели / сеттеры и реализации equals() / hashCode() для краткости опущены - все, что IDE генерирует для последнего, подойдет.

Этот код по сути представляет собой матрицу, представленную списком смежности.Единственная его часть, которая не является O (1), это часть, которая ищет человека с наибольшим количеством соединений, а именно O (n).

Вы можете уменьшить этот удар по производительности, используя удержание PriorityQueueSet<Person> объекты, которые хранятся на карте adjacency, с заданным размером в качестве «приоритета».Каждый раз, когда к такому набору нужно прикоснуться, удалите его из очереди, измените его и вставьте снова.(Однако я догадываюсь, что это только ускорит процесс подключения наиболее подключенного человека, делая подключение и отключение людей медленнее.)

Отказ от ответственности: приведенный выше код полностью не проверен, он просто дает вам представление о том, что вымог бы попробовать.

Answer 5

Если пространство не является проблемой, я бы использовал матрицу для хранения соединений.

Первое измерение - это 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

Это потратило бы слишком много места, но было бы очень быстро и легкоработа с.