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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

насчет:

Map<Entity, List<Entity>> 

?

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

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

Answer 4

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

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

Ex1: объекты имеют числовые атрибуты и критерии поиска, когда атрибут> конкретный порог - RBTReeMap будет решением.

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

Ex3: Структура ваших объектов очень похожа на FSA (Finate State Automatons). В этом случае поиск выполняется по языку ввода (не самим сущностям). Решениями являются минимизация автомата и детерминирование.

Answer 5

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

Что-то вроде этого:

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