改進交集算法

我有一個算法來構建兩個排序列表的交集。如果我在性能測試中將它與java.util.BitSet進行比較，我的算法很慢。改進交集算法

public static List<Integer> intersection(List<Integer> list1, List<Integer> list2) { 
      int size1 = list1.size(), size2 = list2.size(); 
      int capacity = size1 < size2 ? size1 : size2; 
      List<Integer> intersection = new ArrayList<Integer>(capacity); 
      int i1 = 0, i2 = 0; 
      while (i1 < size1 && i2 < size2) { 
       if (list1.get(i1) < list2.get(i2)) 
        i1++; 
       else if (list2.get(i2) < list1.get(i1)) 
        i2++; 
       else { 
        intersection.add(list2.get(i2++)); 
        i1++; 
       } 
      } 
      return intersection; 
     }

任何人都看到有所改進？

感謝

來源

2013-03-26 myborobudur

使用'BitSet'，甚至是'int []'。指定'ArrayList'的容量可能是一個錯誤。可能不需要那麼大。每個循環只需要兩個'get's。即使只是在相關的增量上「獲得」，也可以減少這種情況。你可能要考慮使用'Iterator's，特別是如果給你一個'LinkedList'作爲參數。 – 2013-03-26 10:02:29

是輸入你的函數總是ArrayList類型的？

如果是，算法上你的方法沒有問題。我會做兩個更改：
1. 我會將參數類型更改爲ArrayList<Integer> list1, ArrayList<Integer> list2;
2. 我只能撥打list1.get(i1)和list2.get(i2)一次。這可能會或可能不會影響性能，但在風格上我更願意將其分解。
如果你需要支持任何列表，那麼我會用兩個迭代器重寫函數，因爲調用get(index)可能非常昂貴。

最後，測試性能時，請務必按照How do I write a correct micro-benchmark in Java?

來源

2013-03-26 09:57:08 NPE

它總是ArrayList。我採納了你的建議，謝謝！ – myborobudur 2013-03-27 07:28:22

提出的意見，你應該知道，這樣的：

List<Integer> intersection = new ArrayList<Integer>(capacity);

分配大小capacity的內部數組。

假設list1.size() == 5000和list2.size() == 5000和intersection(list1, list2).size() == 3，該方法將分配4997個無用整數。

嘗試使用合理的容量（取決於方法的用途）或僅將其保留爲默認值（即10）。

（裸記住該分配尺寸n的陣列的複雜性（或ArrayList的容量n）是O(n)。）

來源

2013-03-26 10:20:33

在ArrayList中分配更多空間不是很昂貴嗎？ – myborobudur 2013-03-27 07:30:10

分配更多空間是很昂貴的，讓'ArrayList'調整內部數組的次數太多，你應該選擇一個合理的'容量'也是很昂貴的。 – 2013-03-27 08:22:03

它實現列表可以調用的方法。載（任何列表對象o）和.add（對象o）。以下代碼返回一個ArrayList，但可以替代任何列表實現。

public List<Integer> intersection(List<Integer> a, List<Integer> b){ 
     ArrayList<Integer> intersection = new ArrayList<Integer>(); 
     for(Integer x : a)//Loop over a list 
      if(b.contains(x))//if the list contains the element 
       intersection.add(x);//add to return list 
     return intersection; 
    }

明智的是，這應該在theta（m）（其中m是其中一個列表的長度）中運行。

來源

2013-03-26 13:00:26

這肯定太慢了。 for循環中的每一步都會導致整個「遍歷」列表b。 – myborobudur 2013-03-27 07:25:28

改進交集算法

回答

相關問題