前言

我有一個(gè)集合，實(shí)際上是一個(gè)HashSet。我想從中刪除一些item…其中許多item可能不存在。事實(shí)上，在我們的測(cè)試用例中，“removals”集合中的所有項(xiàng)都不在原始集合中。這聽(tīng)起來(lái)——實(shí)際上也是——非常容易編碼。畢竟，我們已經(jīng)準(zhǔn)備好了。removeAll來(lái)幫助我們，對(duì)嗎？

讓我們把它變成一個(gè)小測(cè)試。我們?cè)诿钚猩现付?ldquo;source”set的大小和“removals”集合的大小，并構(gòu)建它們。source set合只包含非負(fù)整數(shù)；刪除集僅包含負(fù)整數(shù)。我們使用系統(tǒng)測(cè)量刪除所有元素所需的時(shí)間System.currentTimeMillis()，它不是世界上最精確的秒表，但在這種情況下就足夠了，正如您將看到的那樣。

代碼如下：

import java.util.*;
public class Test
{
    public static void main(String[] args)
    {
        int sourceSize = Integer.parseInt(args[0]);
        int <a  rel="external nofollow"  rel="external nofollow"  target="_blank" >removals</a>Size = Integer.parseInt(args[1]);
        
        Set<Integer> source = new HashSet<Integer>();
        Collection<Integer> <a  rel="external nofollow"  rel="external nofollow"  target="_blank" >removals</a> = 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");
    }
}

首先，讓我們給它一個(gè)簡(jiǎn)單的工作：一個(gè)包含100個(gè)items的source set，以及要?jiǎng)h除的100個(gè)items：

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

好吧，所以我們沒(méi)想到會(huì)很慢……很明顯，我們可以把速度提高一點(diǎn)。一百萬(wàn)件items和300000件items的來(lái)源如何？

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

嗯，看起來(lái)還是挺快的?，F(xiàn)在我覺(jué)得我有點(diǎn)殘忍，要求它做所有這些移除。讓我們讓它變得更簡(jiǎn)單一些–300000個(gè)source items和300000個(gè)刪除：

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

快三分鐘了？哎呀！當(dāng)然，從一個(gè)較小的集合中刪除items應(yīng)該比我們?cè)?8ms內(nèi)管理的集合更容易？嗯，最終這一切都是有道理的。HashSet擴(kuò)展了AbstractSet，它在removeAll方法的文檔中包含此代碼段：

https://docs.oracle.com/javase/6/docs/api/java/util/AbstractSet.html

此實(shí)現(xiàn)通過(guò)調(diào)用每個(gè)集合上的size方法來(lái)確定此集合和指定集合中的較小者。如果此集合的元素較少，則實(shí)現(xiàn)將迭代此集合，依次檢查迭代器返回的每個(gè)元素，以查看它是否包含在指定的集合中。如果它是這樣包含的，則使用迭代器的remove方法將其從該集中移除。如果指定集合的元素較少，那么實(shí)現(xiàn)將迭代指定集合，使用該集合的remove方法從該集合中刪除迭代器返回的每個(gè)元素。

從表面上看，這聽(tīng)起來(lái)很合理——遍歷較小的集合，檢查較大集合中是否存在。然而，這就是抽象存在漏洞的地方。僅僅因?yàn)槲覀兛梢砸笠粋€(gè)item出現(xiàn)在一個(gè)大的集合中，并不意味著它會(huì)很快出現(xiàn)。在我們的例子中，集合的大小是相同的，但是檢查哈希集中是否存在項(xiàng)是O（1），而在ArrayList中檢查是O（N）…而每個(gè)集合的迭代成本是相同的?；旧?，通過(guò)選擇遍歷HashSet并檢查ArrayList中是否存在，我們得到了一個(gè)O（M*N）解決方案，而不是O（N）解決方案。removeAll方法基于在這種情況下無(wú)效的假設(shè)進(jìn)行“優(yōu)化”。

那么如何解決？

有兩種簡(jiǎn)單的方法可以解決這個(gè)問(wèn)題。首先，只需更改要從中刪除的集合的類型。只需將ArrayList<Integer>更改為HashSet<Integer>，我們就可以回到34ms的范圍。我們甚至不需要更改聲明的刪除類型。

第二種方法是更改我們使用的API：如果我們知道要迭代刪除并在源代碼中執(zhí)行查找，那么很容易做到：

for (Integer value : removals)
{
    source.remove(value);
}

事實(shí)上，在我的機(jī)器上，它的性能略優(yōu)于removeAll–它不需要在每次迭代時(shí)檢查remove的返回值，removeAll這樣做是為了返回是否刪除了任何項(xiàng)。以上運(yùn)行時(shí)間約為28ms。（我已經(jīng)用相當(dāng)大的數(shù)據(jù)集對(duì)其進(jìn)行了測(cè)試，它確實(shí)比雙哈希集方法更快。）

然而，這兩種方法都需要在源代碼中添加注釋，以解釋為什么我們沒(méi)有使用最明顯的代碼（列表和刪除）。我不能抱怨這里的文檔——它確切地說(shuō)明了它將做什么。在你遇到這樣的問(wèn)題之前，你根本不需要擔(dān)心它。

那么，實(shí)現(xiàn)應(yīng)該做什么呢？可以說(shuō)，它真的需要知道它所處理的每一個(gè)集合中什么是便宜的。在決定策略之前探索性能特征的想法對(duì)于清理我們喜歡在Java集合之類的框架中考慮的抽象是完全不可取的……但在這種情況下，這可能是一個(gè)好主意。

到此這篇關(guān)于Java HashSet的Removals()方法注意事項(xiàng)的文章就介紹到這了,更多相關(guān)Java HashSet 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論