Эффективный поиск в datastructure ArrayList

Question

У меня есть ArrayList, который содержит мои узлы. У узла есть источник, цель и затраты. Теперь мне нужно перебирать весь массив ArrayList. Это длится более 1000 узлов. Поэтому я попытался отсортировать список по источнику. Но чтобы найти соответствующую пару в списке, я попробовал двоичный поиск. К сожалению, это работает только в том случае, если я хочу сравнить источник или цель. Но я должен сравнивать оба, чтобы получить правильную пару. Есть ли еще одна возможность эффективно искать ArrayList?

Answer 1

К сожалению, нет. ArrayList s не предназначены для эффективного поиска. Они используются для хранения данных, а не для поиска. Если вы хотите просто знать, содержит ли элемент, я бы предложил вам использовать HashSet, так как поиск будет иметь сложность по времени для O (1) вместо O (n) для ArrayList (при условии, что вы внедрили функционирующий метод equals для ваших объектов).

Если вы хотите быстро выполнять поиск объектов, я рекомендую использовать реализацию Dictionnary как HashMap. Если вы можете позволить себе пространство, вы можете иметь несколько карт, каждый с разными ключами, чтобы иметь быстрый поиск вашего объекта независимо от того, какой ключ вам нужно искать. Имейте в виду, что поиск также требует применения правильного метода equals. К сожалению, это требует, чтобы каждый ключ был уникальным, что не может быть блестящей идеей в вашем случае.

Однако вы можете использовать HashMap для хранения для каждого источника списка узлов, у которых есть источник ключей в качестве источника. Вы можете сделать то же самое для стоимости и цели. Таким образом, вы можете сократить количество узлов, которые вам нужны, чтобы итерации по существу. Это должно быть хорошим решением с едва подключенной сетью.

private HashMap<Source, ArrayList<Node>> sourceMap = new HashMap<Source, ArrayList<Node>>(); 
private HashMap<Target, ArrayList<Node>> targetMap = new HashMap<Target, ArrayList<Node>>(); 
private HashMap<Cost, ArrayList<Node>> costMap = new HashMap<Cost, ArrayList<Node>>(); 

/** Look for a node with a given source */ 
for(Node node : sourceMap.get(keySource)) 
{ 
    /** Test the node for equality with a given node. Equals method below */ 
    if(node.equals(nodeYouAreLookingFor) { return node; } 
} 

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

@Override 
public boolean equals(Object object) 
{ 
    if(object instanceof Node) 
    { 
     Node node = (Node) object; 
     if(source.equals(node.getSource() && target.equals(node.getTarget())) 
     { 
      return true; 
     } 
    } else { 
     return false; 
    } 
} 

Если вы этого не сделаете, тест будет просто сравнивать ссылки, которые могут быть или не быть равными в зависимости от того, как вы обрабатываете свои объекты.

Редактировать: Просто прочитайте, на чем вы основываете свое равенство. Метод equals должен быть реализован в вашем классе узлов. Однако для его работы вам необходимо реализовать и переопределить метод equals для источника и цели. То есть, если они являются объектами. Будьте бдительны, хотя, если они тоже Node, это может привести к довольно некоторым испытаниям, охватывающим всю сеть.

Обновление: Добавлен код, отражающий цель кода в комментариях.

ArrayList<Node> matchingNodes = sourceMap.get(desiredSourde).retainAll(targetMap.get(desiredTarget)); 

Теперь у вас есть список всех узлов, соответствующих исходным и целевым критериям.При условии, что вы готовы пожертвовать немного памяти, поиск выше будет иметь сложность O (| sourceMap | * (| sourceMap | + | targetMap |)) [1]. Хотя это превосходит просто линейный поиск всех узлов, O (| allNodeList |), если ваша сеть достаточно велика, и, по-моему, это 1000 узлов, вы могли бы выиграть. Если ваша сеть следует за естественной сетью, то, как показал Альберт-Ласло Барабаши, это, скорее всего, не будет бесплатным. Это означает, что разделение вашей сети на списки, по крайней мере, источника и цели, вероятно (у меня нет доказательств для этого), приведет к распределению по размерам этих списков без масштаба. Поэтому я считаю, что сложность поиска источника и цели будет существенно уменьшена, поскольку | sourceMap | и | targetMap | должен быть существенно ниже | allNodeList |.

Answer 2

Вам необходимо объединить источник и цель в один компаратор, например.

compare(T o1, T o2) { 
    if(o1.source < o2.source) { return -1; } 
    else if(o1.source > o2.source) { return 1; } 
    // else o1.source == o2.source 
    else if(o1.target < o2.target) { return -1; } 
    else if(o1.target > o2.target) { return 1; } 
    else return 0; 
} 

Answer 3

Вы можете использовать .compareTo() метод сопоставляет узлы.

Answer 4

Вы можете создать два массива ArrayLists. Первый отсортирован по источнику, второй - по цели. Затем вы можете искать по источнику или цели, используя binarySearch в соответствующем списке.

Answer 5

Вы можете сделать вспомогательный класс для хранения источника целевых пар:

class SourceTarget { 

    public final Source source; // public fields are OK when they're final and immutable. 
    public final Target target; // you can use getters but I'm lazy 
           // (don't give this object setters. Map keys should ideally be immutable) 

    public SourceTarget(Source s, Target t){ 
     source = s; 
     target = t; 
    } 

    @Override 
    public boolean equals(Object other){ 
     // Implement in the obvious way (only equal when both source and target are equal 
    } 

    @Override 
    public int hashCode(){ 
     // Implement consistently with equals 
    } 
} 

Затем хранить ваши вещи в HashMap<SourceTarget, List<Node>>, с каждым источником целевых парами отображенных в список узлов, которые имеют именно тот источника- целевой пары. Чтобы получить просто использовать

List<Node> results = map.get(new SourceTarget(node.source, node.target)); 

---

В качестве альтернативы, чтобы сделать вспомогательный класс, вы можете использовать компаратор в ответе ЗИМ-ZAM в и TreeMap<Node,List<Node>> с репрезентативным Node объектом, действующим в качестве SourceTarget пары.