从Java的另一个中移除多个Longs集合的最快方法

我有两个Long类型的集合。尺寸均为20-30万元。从第一种方法中删除的最快捷方式是什么？取得的堆空间越小越好，因为还有其他事情正在平行进行。从Java的另一个中移除多个Longs集合的最快方法

我知道LinkedList比使用迭代器的ArrayList更好，但我不确定是否需要迭代每个元素。我想调查任何更好的方法，都Collections排序。

编辑：我前面提到我的集合大小为2-3万，我意识到这是20-30万元。会有很多重叠。集合的确切类型也可以进行辩论。

2014-10-30 Brian

如果他们排序，你可以使用普通的二进制查找，找到的元素从第二删除。显然你需要迭代要删除的数字集合。 – 2014-10-30 12:51:46

在这个尺寸下，收集的确切类型非常重要。 – biziclop 2014-10-30 13:00:59

re：收集和堆空间的确切类型：[trove]（http://java-performance.info/primitive-types-collections-trove-library/）例如为不使用原始类型的“收集”实现大量的包装对象。节省大量的堆空间，速度明智不知道。 – zapl 2014-10-30 13:20:39

没有堆积。

Collection<Long> a = new HashSet<Long>(); 
//fill a 
Collection<Long> b = new ArrayList<Long>(); 
//fill b 
for(int i = 0; i < b.size(); i++){ 
    a.remove(b.get(i)); 
}

b.size()和b.get(int i)运行在根据甲骨文的Javadoc恒定时间。另外a.remove(O o)在恒定时间内运行。

来源

2014-10-30 12:51:19 user

我正在寻找更好的执行比removeAll ArrayList。我的收藏尺寸相对较大。 – Brian 2014-10-30 13:08:50

我更新了答案 – user 2014-10-30 13:09:26

随着计数在数百万的范围内，解决方案与O（n ）复杂性应该出来。您这里有两个基本的解决方案：

排序第二收集，并使用二进制搜索为O（（N + M）* 10gm的）解决方案，或从第二收集
认沽元素融入哈希容器，对于O（N + M）解决方案

上面，N是第一个集合中元素的数量，M是第二个集合中元素的数量。

Set<Long> toRemove = new HashSet<Long>(collection2); 
Iterator<Long> iter = collection1.iterator(); 
while (iter.hasNext()) { 
    if (toRemove.contains(iter.next())) { 
     iter.remove(); 
    } 
}

注意，如果collection1是ArrayList，这将是非常缓慢的。如果你必须保持它的ArrayList，你可以做这样的：

int rd = 0, wr = 0; 
// Copy the elements you are keeping into a contiguous range 
while (rd != arrayList1.size()) { 
    Long last = arrayList1.get(rd++); 
    if (!toRemove.contains(iter.next()) { 
     arrayList1.put(wr++, last); 
    } 
} 
// Remove "tail" elements 
while (rd > wr) { 
    arrayList1.remove(--wr); 
}

来源

2014-10-30 13:00:08 dasblinkenlight

第一个停靠港将是Collection.removeAll方法。这不使用额外的堆空间，其时间复杂度取决于第二个集合上的contains方法的性能。如果你的第二个集合是TreeSet，那么a.removeAll(b)需要O(n . log(m))时间（其中n是a的大小，m是b的大小），如果b是HashSet，那么它需要O(n)时间，如果b是排序的ArrayList，那么它是O(nm)，但是你可以创建一个使用二进制搜索将其降低到O(n . log(m))可忽略常量内存成本的新包装系列：

private static class SortedList<T extends Comparable<? super T>> extends com.google.common.collect.ForwardingList<T> 
{ 

    private List delegate; 

    public SortedList(ArrayList<T> delegate) 
    { 
     this.delegate = delegate; 
    } 

    @Override 
    protected List<T> delegate() 
    { 
     return delegate; 
    } 

    @Override 
    public boolean contains(Object object) 
    { 
     return Collections.binarySearch(delegate, (T) object) >= 0; 
    } 
} 

static <E extends Comparable<? super E>> void removeAll(Collection<E> a, ArrayList<E> b) 
{ 
    //assumes that b is sorted 
    a.removeAll(new SortedList<E>(b)); 
}

来源

2014-10-30 13:10:38 MikeFHay

你应该Apache Common Collections

我的LinkedList测试它看看〜3M多头，它给出了相当不错的结果：

Random r = new Random(); 
    List<Long> list1 = new LinkedList<Long>(); 
    for (int i = 0; i < 3000000; i++) { 
     list1.add(r.nextLong()); 
    } 
    List<Long> list2 = new LinkedList<Long>(); 
    for (int i = 0; i < 2000000; i++) { 
     list2.add(r.nextLong()); 
    } 

    Collections.sort(list1); 
    Collections.sort(list2); 

    long time = System.currentTimeMillis(); 
    list3 = ListUtils.subtract(list2, list1); 
    System.out.println("listUtils.intersection = " + (System.currentTimeMillis() - time));

我不能确保你这是最好的解决方案，但它是一样容易的。

我得到的执行时间等于：

1247 ms

难以忽视的：它会创建一个新的列表

来源

2014-10-30 13:10:57 yunandtidus

从Java的另一个中移除多个Longs集合的最快方法

回答

相关问题