數據結構中的高效搜索ArrayList

我有一個包含我的節點的ArrayList。節點具有源，目標和成本。現在我必須迭代整個ArrayList。這持續了超過1000個節點。因此我嘗試按來源對我的List進行排序。但是爲了在列表中找到相應的對，我嘗試了二進制搜索。不幸的是，只有當我想比較源或目標時纔有效。但我必須比較兩者才能找到合適的配對。是否有另一種可能性來搜索ArrayList高效？數據結構中的高效搜索ArrayList

來源

2013-06-24 Irgendw Pointer

你如何做搜索？你必須匹配這兩個對的項目？或者您需要能夠搜索僅匹配每對中的一個項目的記錄？ – Plato

我在我提供的答案中添加了一些代碼。我希望它會證明有用！ – Eric

數據來自哪裏？您在1000個節點中使用的數據，您從哪裏獲取數據？ – LuckyMe

不幸的是，沒有。 ArrayList不能被有效搜索。它們用於存儲數據而不搜索它。如果您只想知道是否包含某個項目，我建議您使用HashSet，因爲查找將具有O（1）的時間複雜度而不是ArrayList的O（n）（假定您已實施了功能equals方法爲你的對象）。

如果您想快速搜索對象，我推薦使用Dictionnary的實現，如HashMap。如果您可以承擔空間要求，則可以擁有多個地圖，每個地圖都有不同的密鑰，以便快速查找對象，而無論您需要搜索哪個密鑰。請記住，查找還需要實施正確的方法。不幸的是，這要求每把鑰匙都是獨一無二的，在你的情況下這可能不是一個好主意。

但是，您可以使用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));

來源

2013-06-24 15:11:00 Eric

這實際上並不是我想要的。我現在創建了一個Map >。因此，現在我有一個源= 3和目標= 6的節點。因此，我必須搜索以找到一個唯一的元素，其中源爲3，目標爲6.因爲也可以有一個帶源的節點是3目標是8. –

由於錯誤轉貼評論！ \t 是的，但你必須搜索的集合大大減少。我會建議的是，您按照我注意到的方式嘗試它，然後執行以下操作：獲取源數爲3的所有節點的集合，獲取目標爲8的所有節點，獲取兩個集合的交集。然後您將擁有一個集合，其中包含源爲3，目標爲8的所有節點。對於交集，請查看Java的retainAll（List）方法。如果你願意，我可以提供一個例子！ – Eric

僅供參考，截至Java 7，您不再需要冗餘，冗餘'HashMap > sourceMap = new HashMap >（）;'。相反，你可以寫：'HashMap > sourceMap = new HashMap <>（）;' –

您需要將源和目標合併爲一個比較器，例如，

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

來源

2013-06-24 15:07:18

您可以使用.compareTo()方法來比較您的節點。

來源

2013-06-24 15:07:35

我試着用compareTo（），但我需要確保源和目標與我正在比較的節點相同。因此用compareTo（）不可能做到這一點。 –

您可以創建兩個ArrayList。第一個按來源排序，第二個按目標排序。然後，您可以使用相應List上的binarySearch按源或目標進行搜索。

來源

2013-06-24 15:10:45 lopisan

你可以讓一個輔助類來存儲源 - 目標對：

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

或者以製作一個輔助類，你可以使用以星 - 讚的答案比較，並充當SourceTarget對有代表性的Node對象TreeMap<Node,List<Node>>。

來源

2013-06-24 16:41:01 trutheality

數據結構中的高效搜索ArrayList

回答

相關問題