В Java какая коллекция наиболее эффективна для сети данных? - PullRequest
Новая
       41

В Java какая коллекция наиболее эффективна для сети данных?

0 голосов
/ 21 декабря 2011

У меня есть сеть «сущностей» (Objects), каждая из которых содержит информацию о том, каковы «следующие» (следующие) сущности, которые могут быть любыми между ничем и многими. Кроме того, «следующие» сущности содержат информацию для своих «следующих сущностей» (которые могут быть совершенно новыми или предыдущими, только что связанными с ним).

Итак, A знает, где B a C, B знает, где A, D и E есть, и так далее. Обратите внимание на двустороннее направление A и B. Нет ограничений на количество или направление соединений.

Какая коллекция (самая производительная) была бы лучшей (наиболее производительной) для симуляции такой сети, если бы мне приходилось часто просматривать объекты (много тысяч раз)? Что было бы лучшей коллекцией, если бы я искал строки вместо объектов? Есть ли разница? Будет ли любой другой тип объекта быстрее?

Спасибо всем!

Редактировать: я пытаюсь сохранить огромное количество «воспоминаний» (исторических событий в симуляции) в сети / графике, затем найти определенную память и проследить соединения с ее соседями и соседи соседей и т. д., ища «комбинации» воспоминаний, которые соответствуют моему шаблону поиска. Например, я проверяю, существуют ли сущности "A, B, C и снова A" в этом порядке.

Ответы [ 5 ]

3 голосов
/ 21 декабря 2011

Ваш вопрос довольно расплывчатый.Если вы можете как-то определить «ключ» для ваших поисковых терминов, вы можете использовать HashMap структуру данных (в java.util) в качестве очень быстрой таблицы поиска.

В худшем случае выДля поиска по всей сети необходимо использовать поиск в глубину (DFS) или поиск в ширину (BFS) (технический термин - «график»).

1 голос
/ 22 декабря 2011

Для меня это звучит так, как будто у вас проблема типа "график".Возможно, вы могли бы использовать neo4j (http://neo4j.org/) как способ представления ваших отношений, а затем использовать его API для выполнения поиска?

1 голос
/ 21 декабря 2011

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

Примерно так: 

public class Entity {
    static Map<String, Entity> map = new HashMap<String, Entity>();

    String id;
    Set<Entity> nextEntities = new HashSet<Entity>();
    Set<Entity> prevEntities = new HashSet<Entity>();

    public Entity (String id) {
        this.id = id;
        map.put(id, this);
    }

    public static forId(String id) {
        return map.get(id);
    }
}
1 голос
/ 21 декабря 2011

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

Если бы вы добавили больше информации о поиске, можно было бы предложить более адекватные решения.

Пример 1: у сущностей есть числовые атрибуты, а критерии поиска - это когда атрибут> определенный порог - RBTReeMap будет решением.

Пример 2: вы ищете последовательности объектов - алгоритмы поиска в графе могут быть рассмотрены.

Пример 3: Ваша структура сущностей очень похожа на FSA (конечные автоматы). В этом случае - поиск здесь осуществляется по языку ввода (а не по сущностям). Решения - это минимизация автомата и его детерминированность.

1 голос
/ 21 декабря 2011

Как насчет: 

Map<Entity, List<Entity>>

?

На карте хранится сама сущность плюс список всех преемников (следующий и / или предыдущий).Доступ к значениям карт с помощью ключа всегда равен O (1), что означает, что к элементу обращаются в течение постоянного времени (это не зависит от того, сколько элементов хранится на карте)

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

...