हैशसेट.removeAll संचालन की एक वर्ग राशि क्यों लेते हैं?

Question

मेरे पास यह कोड है जो HashSet उत्पन्न करता है और उस पर removeAll() पर कॉल करता है। मैंने एक वर्ग A बनाया जो कि एक int का एक रैपर है, जो equals के समय रिकॉर्ड करता है - प्रोग्राम उस संख्या को आउटपुट करता है।

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 आपरेशन रेखीय नहीं है के रूप में मैं अपेक्षा की होगी:

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

वास्तव में, यह द्विघात हो रहा है। क्यूं कर?

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

क्यों:

लाइन s.removeAll(l);for (A b : l) s.remove(b); सुधारों के साथ जिस तरह से मैं उम्मीद थी कार्य करने के लिए जगह?

x और y अक्ष जावा प्रोग्राम के लिए दो तर्क हैं:

यहाँ द्विघात वक्र दिखाने वाला एक ग्राफ़ है। जेड अक्ष A.equals कॉल की संख्या है।

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

सरणी a इस हास्केल प्रोग्राम द्वारा उत्पन्न की गई:

---

ग्राफ इस Asymptote कार्यक्रम द्वारा उत्पन्न की गई

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

बार यह काम करने के लिए 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 से अधिक iterates और प्रत्येक तत्व के लिए c.contains कहता है। चूंकि आप तर्क के रूप में LinkedList का उपयोग कर रहे हैं, यह प्रत्येक तत्व के लिए ओ (एन) ऑपरेशन है। चूंकि इसे प्रत्येक एन तत्वों को हटाए जाने के लिए ऐसा करने की आवश्यकता है, परिणाम एक ओ (एन) ऑपरेशन है।

यदि आप LinkedList को ऐसे संग्रह के साथ प्रतिस्थापित करते हैं जो contains का अधिक कुशल कार्यान्वयन प्रदान करता है, तो removeAll का प्रदर्शन तदनुसार सुधारना चाहिए। यदि आप संग्रह से HashSet बड़े करते हैं, तो प्रदर्शन नाटकीय रूप से भी सुधारना चाहिए, क्योंकि यह संग्रह पर फिर से चालू होगा।