HashSet removeAll yöntemi şaşırtıcı derecede yavaş

Question

Bir kümem var - HashSet Bazı öğeleri kaldırmak istiyorum… "kaldırmalar" koleksiyonundaki öğelerin hiçbiri orijinal ayarında olmayacak.

"Kaynak" kümesinin boyutunu ve komut satırındaki "taşınma" koleksiyonunun boyutunu ve her ikisini de yapıyorum. Kaynak küme yalnızca negatif olmayan tamsayılar içerir; kaldırma kümeleri yalnızca negatif tamsayılar içerir. Dünyanın en doğru kronometresi olmayan System.currentTimeMillis() öğesini kullanarak tüm öğeleri kaldırmak ne kadar sürdüğünü ölçüyorum, ancak göreceğiniz gibi bu durumda yeterli değil. İşte kod:

import java.util.*; 
public class Test 
{ 
public static void main(String[] args) 
{ 
    int sourceSize = Integer.parseInt(args[0]); 
    int removalsSize = Integer.parseInt(args[1]); 

    Set<Integer> source = new HashSet<Integer>(); 
    Collection<Integer> removals = new ArrayList<Integer>(); 

    for (int i = 0; i < sourceSize; i++) 
    { 
     source.add(i); 
    } 
    for (int i = 1; i <= removalsSize; i++) 
    { 
     removals.add(-i); 
    } 

    long start = System.currentTimeMillis(); 
    source.removeAll(removals); 
    long end = System.currentTimeMillis(); 
    System.out.println("Time taken: " + (end – start) + "ms"); 
} 
} 

hadi kolay bir iş vererek başlayayım: kaynağı 100 maddeden seti ve 100 kaldırmak için:

c:UsersJonTest>java Test 100 100 
Time taken: 1ms 

Tamam, beklendiği gibi bu hızlı.

Daha sonra bir milyon öğenin ve 300.000 öğenin kaldırılmasını denedim?

c:UsersJonTest>java Test 1000000 300000 
Time taken: 38ms 

Bu hala oldukça hızlı görünüyor.

c:UsersJonTest>java Test 300000 300000 
Time taken: 178131ms 

Yaklaşık üç dakika: 300.000 kaynak öğeleri ve 300.000 removals - Şimdi daha kolay biraz yapmak?

Gerçekten kafam karıştı! Birisi bunun neden olduğunu açıklayabilir.

Answer 1

davranışı (biraz) javadoc belgelenmiştir:

Bu uygulama, her bir boyut metodu çağırarak, bu dizi ve belirtilen koleksiyon küçük olan belirler. bu seti de belirtilen koleksiyon yer alıyorsa görmek için sırayla yineleyici tarafından döndürülen her elemanı kontrol daha az sayıda parça, bu sette üzerinde daha sonra uygulama yineler varsa. İçerdiği takdirde, bu kümeden yineleyicinin kaldırma yöntemiyle kaldırılır. Belirtilen koleksiyon daha az öğeye sahipse, uygulama bu kümenin kaldırma yöntemini kullanarak yineleyici tarafından döndürülen her öğeyi bu kümeden kaldırılarak belirtilen koleksiyonun üzerinde yinelenir. Bunun pratikteki anlamı nedir

, sen source.removeAll(removals); çağrı: removals toplama source daha küçük boyutta olan

• eğer HashSet ait remove yöntem hızlıdır ki, denir. removals toplama source eşit veya daha büyük bir boyutta olduğunda

• , daha sonra removals.contains Bir ArrayList'deki yavaş olan denir.

Hızlı çözüm: tarif ne çok benzer an open bug olduğunu

Collection<Integer> removals = new HashSet<Integer>(); 

Not. Alt satır, muhtemelen kötü bir seçim olduğu, ancak değiştirilemediği için javadoc'ta belgelenmiş gibi görünüyor.

public boolean removeAll(Collection<?> c) { 
    Objects.requireNonNull(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; 
}