Bir set – bazı öğeleri kaldırmak istiyorum bir HashSet... "taşınma" koleksiyonu orijinal set içinde olacak. içinde hiçbir madde var

Ben "kaynak" ve "taşınma" komut satırında bir koleksiyon, ve her ikisi de inşa etmek. boyutunu ayarla boyutunu belirtin Kaynağı sadece negatif olmayan tamsayılar içerir; çıkarma seti tek negatif tam sayı içerir. Ben tüm öğeleri Sistemi kullanarak kaldırmak için ne kadar sürer ölçmek.en doğru dünya kronometre değil ama gördüğünüz gibi bu durumda çok daha uygun. () currentTimeMillis, İş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 bu kolay bir iş vererek başlayalım:kaynağı 100 öğeleri ayarlayın ve 100 kaldırmak için:

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

Tamam, beklediğimden hızlı oldu.

Önümüzdeki bir milyon öğeler, kaynak ve kaldırmak için 300,000 öğeleri çalıştım?

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

O hala oldukça hızlı görünüyor. Şimdi biraz daha kolay – 300,000 kaynağı öğeleri ve 300,000 taşınma olun:

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

Yaklaşık üç dakika?

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

Davranışları (biraz) javadoc belgelenmiştir:

Bu uygulama bu dizi daha küçük olan ve belirtilen koleksiyon, her boyutu yöntemini çağırarak belirler.Bu set varsa daha az elemanlarıo zaman bu uygulama bu set üzerinde dolaşır, her kontrol elemanı da yineleyici tarafından görmek için geri döndübelirtilen koleksiyon içinde yer alıyor. Eğer kontrol altında değilse, yineleyici yöntemi kaldırmak ile bu dizi kaldırılır. Eğer belirtilen toplama daha az eleman varsa, o zaman belirtilen toplama, her öğe yineleyici tarafından, bu seti kullanarak döndürdü bu dizi kaldırılıyor üzerinde uygulama dolaşır yöntem çıkarın.

source.removeAll(removals); çağırdığınızda bu basitçe şu anlama gelir,:

• eğer source, HashSet remove Bu yöntem daha küçük bir boyutta removals toplama denir, hangi hızlı.

• eğer removals koleksiyon daha eşit veya daha büyük boyutta ise source removals.contains ArrayList için yavaş denir.

Hızlı çözüm:

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

Anlattıklarınıza çok benzer an open bug olduğunu unutmayın. Alt satırında muhtemelen kötü bir seçim olduğunu görünüyor. ama javadoc belgelenen çünkü değiştirilemez.

Başvuru için, bu removeAll 8, diğer sürümlerine bakmadım Java () kodu:

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