Tại sao HashSet.removeAll lấy một số lượng hoạt động bậc hai?

Question

Tôi có mã này tạo ra một HashSet và gọi removeAll() trên đó. Tôi đã thực hiện một lớp học A mà chỉ là một wrapper của một int, trong đó ghi lại số lần equals được gọi là - chương trình kết quả đầu ra số đó.

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); 
    } 
} 

Nó chỉ ra rằng hoạt động removeAll không tuyến tính như tôi lại có thể ngờ:

$ java A 10 10 
55 
$ java A 100 100 
5050 
$ java A 1000 1000 
500500 

Trong thực tế, nó có vẻ là bậc hai. Tại sao?

Thay thế dòng s.removeAll(l); với for (A b : l) s.remove(b); sửa nó hoạt động cách tôi mong đợi:

$ java A 10 10 
10 
$ java A 100 100 
100 
$ java A 1000 1000 
1000 

Tại sao?

Dưới đây là một biểu đồ hiển thị các đường cong bậc hai:

Các trục x và y là hai đối số cho chương trình Java. Trục z là số lượng cuộc gọi A.equals.

---

Đồ thị được tạo ra bởi Asymptote chương trình này:

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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
    new real[]{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, 
    new real[]{0,1,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3}, 
    new real[]{0,1,2,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6}, 
    new real[]{0,1,2,3,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10}, 
    new real[]{0,1,2,3,4,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15}, 
    new real[]{0,1,2,3,4,5,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21}, 
    new real[]{0,1,2,3,4,5,6,28,28,28,28,28,28,28,28,28,28,28,28,28,28}, 
    new real[]{0,1,2,3,4,5,6,7,36,36,36,36,36,36,36,36,36,36,36,36,36}, 
    new real[]{0,1,2,3,4,5,6,7,8,45,45,45,45,45,45,45,45,45,45,45,45}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,55,55,55,55,55,55,55,55,55,55,55}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,66,66,66,66,66,66,66,66,66,66}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,78,78,78,78,78,78,78,78,78}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,91,91,91,91,91,91,91,91}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,105,105,105,105,105,105,105}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,120,120,120,120,120,120}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,136,136,136,136,136}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,153,153,153,153}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,171,171,171}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,190,190}, 
    new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,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); 

Mảng a được tạo ra bởi chương trình Haskell này:

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 

Answer 1

Thời gian cần cho removeAll để làm việc phụ thuộc vào loại bộ sưu tập bạn vượt qua. Khi bạn nhìn vào việc thực hiện các 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; 
} 

người ta có thể thấy rằng khi HashSet và bộ sưu tập có cùng kích thước, nó lặp qua HashSet và gọi c.contains cho mỗi phần tử. Vì bạn đang sử dụng một đối số LinkedList, đây là một hoạt động O (n) cho mỗi phần tử. Vì nó cần phải làm điều này cho mỗi phần tử n bị loại bỏ, kết quả là một hoạt động O (n).

Nếu bạn thay thế LinkedList bằng bộ sưu tập cung cấp triển khai hiệu quả hơn contains, thì hiệu suất của removeAll sẽ cải thiện tương ứng. Nếu bạn làm cho số lượng lớn hơn bộ sưu tập HashSet lớn hơn, hiệu suất cũng sẽ cải thiện đáng kể, vì sau đó nó sẽ lặp qua bộ sưu tập.