從ArrayList中移動對象的其他

我有三個列表，我需要移動動物對象從列表animalSource使用列表animalFilterName列出animalTarget。只有列表中出現名字的動物animalFilterName，應該從動物來源改爲animalTarget，表現明智的做法是否比下面做得更好。現在只使用樣本數據。從ArrayList中移動對象的其他

public class Animal { 

    private String name; 
    private String color; 

    public String getName() { 
     return name; 
    } 
    public void setName(String name) { 
     this.name = name; 
    } 
    public String getColor() { 
     return color; 
    } 
    public void setColor(String color) { 
     this.color = color; 
    } 
} 


public class MoveAnimal { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 

     List<Animal> animalSource = new ArrayList<Animal>(); 
     List<String> animalFilterName = new ArrayList<String>(); 
     List<Animal> animalTarget = new ArrayList<Animal>(); 

     animalFilterName.add("Name1"); 
     animalFilterName.add("Name2"); 

     Animal a1 = new Animal(); 
     a1.setColor("Color1"); 
     a1.setName("Name1"); 

     Animal a2 = new Animal(); 
     a2.setColor("Color2"); 
     a2.setName("Name2"); 

     Animal a3 = new Animal(); 
     a3.setColor("Color1"); 
     a3.setName("Name3"); 

     Animal a4 = new Animal(); 
     a4.setColor("Color1"); 
     a4.setName("Name4"); 

     Animal a5 = new Animal(); 
     a5.setColor("Color5"); 
     a5.setName("Name1"); 


     animalSource.add(a1); 
     animalSource.add(a2); 
     animalSource.add(a3); 
     animalSource.add(a4); 
     animalSource.add(a5); 


     for(String s: animalFilterName) { 
      for(Animal a: animalSource) { 
       if(s.equals(a.getName())) { 
        animalTarget.add(a); 
       } 
      } 
     } 

    } 

}

來源

2012-06-28 Himalay Majumdar

對不起，你的問題是什麼？編輯：啊，我錯過了，因爲缺少「？」。「更好」是什麼意思？也許更快，或更清潔？ – BlackVegetable

爲了獲得更好的性能，您可能需要使用集。我敢肯定，你在做什麼是M = animalSource.size（）和n = animalFilterName.size（）的O（m * n個）的操作，因爲在查找的ArrayList是爲了N（在列表大小）

查找，插入和在集清除通常是（根據設定實現的細節），以便最壞情況分期常量時間或對數時間（該組的大小），使用套將這個降低到O（ m * log（n））爲相同的m和n。

Set<Animal> animalSource = ...; 
Set<Animal> animalTarget = ...; 
Set<String> animalFilterName = ...; 

// add matching animals to new set 
for (Animal a : animalSource) 
    if (animalFilterName.contains(a.getName())) animalTarget.add(a); 

// if you need to remove them from the first set, uncomment these lines 
// for (Animal a : animalTarget) 
//  animalSource.remove(a);

我想在一行IFS忽略換行符和循環使它們看起來更整潔。這是個人偏好，你沒有義務複製我的風格。

編輯：固定的時間複雜度

另一個編輯：當你說動，你的意思是添加到一個列表並從其他？或者你只是想添加到一個列表？

三編輯：固定零散線

來源

2012-06-28 21:30:57 Wug

謝謝Wug，首先我不想修改原始列表，也應該澄清我的3個列表數據結構是固定的。我在想，如果可能的話，我應該將列表中的值傳遞給地圖上的地圖，然後添加到另一個列表中？不過，我喜歡你用過的方式，而不是嵌套for。我現在要使用這種風格。請讓我知道你是否有更好的解決方案。謝謝。 –

兩件事情浮現在腦海

1），而不是做一個過濾器列表並遍歷它，你可以做一組過濾器，並檢查動物的名字在集合中。這是大O字方面比較好，無論是在實時速度取決於實際的集合大小。

2）如果你既不排序也不做隨機存取，LinkedLists比的ArrayList更有效。

public static void main(String[] args) { 

    List<Animal> animalSource = new LinkedList<Animal>(); 
    Set<String> animalFilterName = new HashSet<String>(); 
    List<Animal> animalTarget = new LinkedList<Animal>(); 

    //Set-up 

    for (Animal a : animalSource) { 
     if (animalFilterName.contains(a.getName())) { 
      animalTarget.add(a); 
     } 
    } 
}

來源

2012-06-28 21:31:25 Affe

所示的算法具有複雜度O（n×m個）（由於兩個嵌套循環），其中n是所述元素在第一列表中的數，m是在過濾器元件的數量。

爲了提高對n和m的值越大性能更好的算法，可以過濾列表轉換成一個哈希表。

像這樣：

Hashtable<String, String> animalFilterName = new Hashtable<String, String>(); 
animalFilterName.put("Name1", null); 
animalFilterName.put("Name2", null);

然後，雙for循環可以被簡化爲：

for (Animal a: animalSource) { 
    if (animalFilterName.containsKey(a.getName())) { 
     animalTarget.add(a); 
    } 
}

現在複雜好得多：O（n）的作爲哈希表表現爲平均O（1）。但你只注意到與n和m較大數量的差別。

來源

2012-06-28 21:44:40 pjmolina

「O（1）的平均值」？這似乎意味着某些操作比O（1）更快以抵消那些不是的操作。 – Dave

整潔的想法，但我會馬上使用HashSet。只是一點點清潔。 – Jochen

這個解決方案的好處是如果你的過濾器是基於字符串的，否則最好使用一個Set（也許使用HashSet實現）。順便說一句buen trabajoseñor。 –

要尊重事實，你允許你的sourceAnimal列表中的重複條目我建議如下：

添加兩件事情：

類型列表的indexList

List<List<Integer>>

持有您的sourceAnimal列表中動物的指數。當您添加一個額外的最後一塊

indexList: [ 0: [0, 4], 1: [1], 2:[2], 3:[3] ]

這一切是有道理的：一個哈希表這意味着，如果你有以下sourceAnimal列表

sourceAnimal: [ 0:"rabbit", 1:"dog", 2:"cat", 3:"horse", 4:"rabbit" ]

，你將有以下（新）indexList。

HashTable將動物名稱映射到indexList中的相應索引，您可以在其中讀取實際sourceAnimal列表中所有出現的動物名稱的實際索引。

隨着該如下，你會處理你的任務：

// Pseudo-Code ! 

foreach (animal: animalFilter) { 

    if (hashtable.contains(animal) { 

     int superIndex = hashtable.get(animal); 

     foreach (int sourceAnimalIndex : indexList[superIndex]) { 

      copy sourceAnimal[sourceAnimalIndex] to targetAnimal; 
     } 
    } 

}

}

這種方法的好處是你避免任何迭代（除了在乘accuring動物一樣的索引在上面的例子中，「兔子」的索引0和索引4以及你想要過濾的動物的迭代）。

A 缺點當然可能是您必須添加額外的數據結構並添加一些維護開銷。

但是我確定如果你在sourceAnimalList中存儲了大量的項目，那麼在每個動物的整個列表中防止「主迭代」將非常有效。

來源

2012-06-28 21:45:25

從ArrayList中移動對象的其他

回答

相關問題