我有这个代码生成一个HashSet并调用removeAll().我做了一个类A,它只是一个int的包装,它记录了等于被调用的次数 – 程序输出这个数字.
import java.util.*;
class A {
int x;
static int equalsCalls;
A(int x) {
this.x = x;
}
@Override
public int hashCode() {
return x;
}
@Override
public boolean equals(Object o) {
equalsCalls++;
if (!(o instanceof A)) return false;
return x == ((A)o).x;
}
public static void main(String[] args) {
int setSize = Integer.parseInt(args[0]);
int listSize = Integer.parseInt(args[1]);
Set<A> s = new HashSet<A>();
for (int i = 0; i < setSize; i ++)
s.add(new A(i));
List<A> l = new LinkedList<A>();
for (int i = 0; i < listSize; i++)
l.add(new A(i));
s.removeAll(l);
System.out.println(A.equalsCalls);
}
}
事实证明,removeAll操作不是线性的,我会想到：@H_403_5@
$java A 10 10 55 $java A 100 100 5050 $java A 1000 1000 500500
其实呢似乎是二次的.为什么？@H_403_5@
替换行s.removeAll(l);与(A b：l)s.remove(b);修正它以我期望的方式行事：@H_403_5@
$java A 10 10 10 $java A 100 100 100 $java A 1000 1000 1000
为什么？@H_403_5@
x和y轴是Java程序的两个参数. z轴是A.equals调用的数量.@H_403_5@
import graph3;
import grid3;
import palette;
currentprojection=orthographic(0.8,1,1);
size(400,300,IgnoreAspect);
defaultrender.merge=true;
real[][] a = new real[][]{
new real[]{0,0},new real[]{0,1},3,3},2,6,6},10,10},4,15,15},5,21,21},28,28},7,36,36},8,45,45},9,55,55},66,66},11,78,78},12,91,91},13,105,105},14,120,120},136,136},16,153,153},17,171,171},18,190,190},19,210},};
surface s=surface(a,(-1/2,-1/2),(1/2,1/2),Spline);
draw(s,mean(palette(s.map(zpart),Rainbow())),black);
//grid3(XYZgrid);
import System.Process
import Data.List
f :: Integer -> Integer -> IO Integer
f x y = fmap read $readProcess "/usr/bin/java" ["A",show x,show y] ""
g :: [[Integer]] -> [String]
g xss = map (\xs -> "new real[]{" ++ intercalate "," (map show xs) ++ "},") xss
main = do
let n = 20
xs <- mapM (\x -> mapM (\y -> f x y) [0..n]) [0..n]
putStrLn $unlines $g xs
解决方法
removeAll工作所需的时间取决于您通过什么样的集合.当你看看removeAll的实现时：
public boolean removeAll(Collection<?> c) {
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
可以看到,当HashSet和集合具有相同的大小时,它会迭代HashSet,并为每个元素调用c.contains.由于您使用LinkedList作为参数,所以这是每个元素的O(n)操作.由于需要为被删除的n个元素中的每一个执行此操作,所以结果是O(n2)操作.@H_403_5@
如果将LinkedList替换为提供了更有效的包含内容的集合,那么removeAll的性能就会相应改善.如果使HashSet大于集合,性能也应该显着提高,因为它会遍历集合.@H_403_5@
