的Java ArrayList包含了循环

-1

主场迎战据了解，如果我想找到一个对象是否是一个ArrayList我既可以使用contains（）方法：的Java ArrayList包含了循环

if(arraylist.contains(obj)) { // do things }

或者我可以用一个用于环（条件是我已重载equals（）方法）：

for(Object o : arraylist) { 

    if(obj.equals(o)) { 

     // do things 

    } 

}

正如在其他职位被称为，含有（）实际上使内部的用于循环和equals（）方法。因此，我的问题是：在数组列表较大时期望contains（）花费更多时间是否合乎逻辑？

我在问这是因为在我的代码中，我使用contains（）以避免“for循环”，因此保持运行时间低且恒定，但我注意到代码运行速度明显慢于arraylist大小变得更大。

2014-02-17 Kotsos

“我注意到代码运行作为该ArrayList尺寸变得更大显著慢。”，这是很有意义的，因为更大的阵列是，则更多的元素存在通过搜索。 – Vallentin

@Vallentin这也是我的想法。不过，还没有一个性能增益（或至少不显著之一）通过使用包含（），而不是一个手动写的for循环，对不对？ – Kotsos

肯定会随着数组列表大小的增加而变慢。 '的使用包含（）'将在单行和会比你的for循环 –

当数组列表较大时期望contains（）花费更多时间是合乎逻辑的吗？

是的。 ArrayList Javadoc说：

大小，isEmpty，get，set，iterator和listIterator操作在恒定时间内运行。 add操作以分摊的恒定时间运行，即添加n个元素需要O（n）个时间。 所有其他操作在线性时间内运行（粗略地说）。

因此，的ArrayList.contains()复杂度为为O（n），由于需要检查该ArrayList的每个元素这是有意义的。没有其他的选择，因为一个ArrayList没有排序，并且给定了它的值，没有其他访问路径到特定的元素。

2014-02-17 14:01:09

“与LinkedList实现相比，常数因子较低。”这是否意味着如果我正在使用List接口的LinkedList实现而不是ArrayList，contains（）方法会导致几乎不变的时间？ – Kotsos

不，对于复杂性分析，*因素*并不重要。另外，它说'ArrayList'的因子较低，所以如果'ArrayList'是O（n），我希望'LinkedList'类似于O（2 * n），这会比'ArrayList'差。 –

好的，谢谢你的回复！ – Kotsos

当arraylist较大时期望contains（）花费更多时间是否合乎逻辑？

是的。通过你自己的话：

正如在其他职位被称为包含（）实际上是利用内部的for循环和equals（）方法。

更多要搜索的元素=需要更多时间。

如果你需要不断的查找，你可以尝试使用一个哈希集（可能会或可能不适用于你的情况）。或者，如果您的数据已排序，则可以使用二进制搜索从O（n）到O（lg（N））。

2014-02-17 14:01:43

是的，对于List需要与列表大小成比例的时间。如果您需要更快地检查会员资格，请考虑使用例如HashSet，这可以在固定时间检查会员资格。

2014-02-17 14:02:41

或二进制搜索 – holap

一个有序的ArrayList打我一分钟。 ;） – Bex

当然，这取决于有问题的对象的位置。但是，是的，在最坏的情况下，你必须检查所有的元素。 – Puce

正如很多人已经指出的那样：是的，这是有道理的，无法避免的。

如果你想以优化包含（） - 的情况下，可以考虑使用HashSet而不是ArrayList，只要你不需要拷贝，以填补集合。 HashSet搜索速度快很多。

2014-02-17 14:04:23 Bex

的方法肯定会需要时间，因为它是内部实现也是一个for循环，就像你给什么作为一个例子。

你在ArrayList它需要完成的时间越长有越多的物品。

2014-02-17 14:10:28 krato

我之前看到过这个答案，但它指的是contains（）与foreach | iterator案例的比较，我认为它可能是某种不同的情况。看起来，我错了。 – Kotsos

回答