插入自己的列表

Question

給定List實例，將List的大小增加f的最有效方法是什麼，使得新元素是原始元素的副本，與原始數組交叉？

例如

f  = 2 
Original = [a,b,c,...,x,y,z] 
New  = [a,a,b,b,c,c,...,x,x,y,y,z,z] 

我目前的實施過程是這樣：

List<Foo> interleave(List<Foo> original, int f) { 
    int newSize = original.size() * f; 
    List<Foo> interleaved = new ArrayList<Foo>(newSize); 

    for(Foo foo : original) { 
     for(int j = 0; j < factor; j++) { 
      interleaved.add(new Foo(foo)); 
     } 
    } 
} 

的問題是，我原來的名單可以說是相當大的，所以表現不是很好。我有一種預感，那就是有一種更有效的方法來做到這一點;有沒有人有什麼建議？

Answer 1

你的代碼提供就是我們會進行優化，但是可以進行一些改進;重要的取決於你的確切需求。

---

首先，如果你克隆的元素會留在相同的值作爲原始，或以其他方式只是其中（相對於總）將有自己的價值觀改變了，你可能想考慮基於參考的克隆而不是當前的「真正克隆它」代碼，如果不是完全不同的方法，甚至不創建新的列表。

/** 
    * PROS: 
    * -Very low memory-footprint, as no new objects are created in memory, just references to a single (original) object. 
    * -Can be done with generalization; A single method will function for most classes and data-types, as is below. 
    * 
    * CONS: 
    * -If you need each clone element to be changed independently from eachother and/or the orininal, this will not work directly, 
    * because any change to an reference-element will apply to all other reference-elements that point to that same Object. 
    * 
    * @param <E> Sub-class generalizator. Used so that the returned list has the same sub-class as the source. 
    * @param list Source list. The list containing the elements to be interleaved. 
    * @param f The factor to interleave for. In effect, the number of resulting elements for each original. 
    * @return A list containing the interleaved elements, with each element being a REFERENCE to the original object. 
    */ 
    public static <E> List<E> interleaveByReference(List<E> list, int f) { 
     List<E> interleaved = new ArrayList<E>(list.size() * f); 
     for (E obj : list) { 
      for (int i = 0; i < f; i++) { 
       interleaved.add(obj); 
      } 
     } 
     return interleaved; 
    } 

如果你將需要短短的克隆的改變值，它可能是更好地爲您的交織列表爲參考依據，並改爲單獨更換需要的元素稍後的。

但是請注意，這種方法的有效性將高度依賴於您的原始列表元素需要更改多少;如果太多需要改變，這種方法雖然在內存佔用方面更好，但速度性能會更差（這似乎是您最關心的問題）。

的「後個人克隆」可以用類似的措施來實現：

public static void replaceWithTrueClone(List<String> list, int objIndex) { 
    list.add(objIndex, new String(list.get(objIndex))); 
    list.remove(objIndex + 1); 
} 

//OR 

public static void replaceWithNewObject (List<String> list, int objIndex, String newObject) { 
    list.add(objIndex, newObject); 
    list.remove(objIndex + 1); 
} 

---

如果大多數每一個元素都將有獨立的價值在你的程序的執行過程中，那麼你目前的方法已經很精確了。

有兩個可以改進的地方。它會更容易直接顯示它的代碼，所以這就是我會做：

/** 
    * PROS: 
    * -Each element is an independent object, and can be set to independent values without much of an effort. 
    * 
    * CONS: 
    * -Each element has it's own allocated memory for it's values, thus having a much heavier memory footprint. 
    * -Is constructor-dependent, and thus cannot be generalized as easily; 
    * Each different expected class will probably need it's own method. 
    * 
    * @param list Source list. The list containing the elements to be interleaved. 
    * @param f The factor to interleave for. In effect, the number of resulting elements for each original. 
    * @return A list containing the interleaved elements. 
    * For each of the original elements, the first is a REFERENCE, and the other are CLONES. 
    */ 
    public static List<String> interleaveByClone(List<String> list, int f) { 
     List<String> interleaved = new ArrayList<String>(list.size() * f); 
     for (String obj : list) { 
      interleaved.add(obj); //The first element doesn't have to be cloned, I assume. 
      //If it has to be cloned, delete the line above, and change 'i=1' to 'i=0' on the line below. 
      for (int i = 1; i < f; i++) { 
       interleaved.add(new String(obj)); 
      } 
     } 
     return interleaved; 
    } 

    /* 
    * What was changed from the original is commented below. 
    */ 

    public static List<String> original(List<String> original, int factor) { 
     /* 
     * It is unnessessary to have this 'newSize' variable. It gets needlessly maintained until the end of the method. 
     * Although the impact is unworthy of measurement (negligible), it still exists. 
     */ 
     int newSize = original.size() * factor; 
     List<String> interleaved = new ArrayList<String>(newSize); //Just do the '*factor' operarion directly, instead of 'newSize'. 

     for (String foo : original) { 
      /* 
      * If you can use the original here, that's one less cloning operation (memory-allocation, etc...) per original element. 
      * A low-impact optimization, but still a good one. 
      */ 
      for (int j = 0; j < factor; j++) { 
       interleaved.add(new String(foo)); 
      } 
     } 
     return interleaved; 
    } 

---

有兩個百萬個元素的原始名單，和2倍，我得到以下平均速度超過10次運行：

• 它需要6030（〜）毫秒創建並填寫原始列表 2000000個不同的元素。
• 需要75（〜）毫秒將列表與 interleaveByReference()方法交錯。
• 需要185（〜）毫秒將列表與 interleaveByClone()方法交錯。
• 需要210（〜）毫秒才能將列表與 original()方法交錯。

Answer 2

這工作相當好，沒有一個完整的重複的費用。

List<String> interleave(final List<String> original, final int f) { 
    final int size = f * original.size(); 
    final List<String> originalCopy = new ArrayList<String>(); 
    for (String each : original) { 
     originalCopy.add(new String(each)); // <=== duplicate here. 
    } 
    return new AbstractList<String>() { 
     @Override 
     public String get(int index) { 
      return originalCopy.get(index/f); 
     } 

     @Override 
     public int size() { 
      return size; 
     }    
    }; 
} 

測試

System.out.println(interleave(Arrays.asList("a", "b", "c"), 2)); 
System.out.println(interleave(Arrays.asList("x", "y"), 3)); 

輸出

[a, a, b, b, c, c] 
[x, x, x, y, y, y] 

Answer 3

A小調加速可以通過重新插入原始的元素，只有創建副本來實現：

List<Foo> interleave(List<Foo> original, int factor) { 
    int newSize = original.size() * factor ; 
    List<Foo> interleaved = new ArrayList<Foo>(newSize); 

    for(Foo foo : original) { 
    interleaved.add(foo); 
    for(int j = 1; j < factor; j++) { 
     interleaved.add(new Foo(foo)); 
    } 
    } 

    return interleaved; 
}