[[440000]]

本文轉(zhuǎn)載自微信公眾號「Java極客技術(shù)」，作者鴨血粉絲Tang 。轉(zhuǎn)載本文請聯(lián)系Java極客技術(shù)公眾號。

最近阿粉在實(shí)現(xiàn)一個功能的時候，遇到了一個性能問題，一個方法在某些場景下運(yùn)行時長達(dá)到了 4s 多，雖然說業(yè)務(wù)功能是實(shí)現(xiàn)了，但是不管是從業(yè)務(wù)的角度還是作為一個有追求的程序員，都是不能接受的，所以優(yōu)化這個方法勢在必行。在優(yōu)化的過程中就用到了本文要說明的一個知識點(diǎn)，看阿粉慢慢道來。

在提供優(yōu)化代碼之前，先簡單的描述一下這個方法做的事情，要做的事情很簡單，就是返回一個整數(shù)，整數(shù)表示的是二進(jìn)制數(shù)組中有多少個 1。給到了入?yún)⑹且粋€ Map

根據(jù)我們上面的分析，列一下我們寫代碼的步驟：

• 因?yàn)槲覀円次贿M(jìn)行或運(yùn)算，所以二進(jìn)制的長度應(yīng)該要一樣才行，我們?nèi)∽铋L的二進(jìn)制的長度為 maxLength，所有沒有這么長的二進(jìn)制字符串，我們需要進(jìn)行前面補(bǔ) 0 ;
• 將所有的二進(jìn)制字符串按位進(jìn)行或運(yùn)算;
• 遍歷最終的數(shù)組輸出 1 的個數(shù);

按照這個思路，我們可以寫出下面的代碼，maxLength 作為入?yún)鬟f到我們的方法中。

public static long version1(Map<String, String> map, int maxLength) { 
        long result = 0L; 
        if (!CollectionUtils.isEmpty(map)) { 
            //1. 將長度不夠 maxLength 長的二進(jìn)制字符串前面補(bǔ) 0 
            for (Map.Entry<String, String> m : map.entrySet()) { 
                if (m.getValue().length() < maxLength) { 
                    StringBuilder newValue = new StringBuilder(); 
                    for (int i = 0; i < maxLength - m.getValue().length(); i++) { 
                        newValue.append(0); 
                    } 
                    newValue.append(m.getValue()); 
                    map.put(m.getKey(), newValue.toString()); 
                } 
            } 
            //2. 將每個關(guān)鍵字的二進(jìn)制字符串按位進(jìn)行或 | 運(yùn)算 
            Integer[] sum = new Integer[maxLength]; 
            for (int i = 0; i < maxLength; i++) { 
                sum[i] = 0; 
            } 
            for (Map.Entry<String, String> m : map.entrySet()) { 
                for (int i = 0; i < maxLength; i++) { 
                    String substring = m.getValue().substring(i, i + 1); 
                    sum[i] = sum[i] | Integer.parseInt(substring); 
                } 
            } 
            //3. 統(tǒng)計(jì)計(jì)算結(jié)果中 1 的個數(shù) 
            for (Integer integer : sum) { 
                result += integer; 
            } 
        } 
        return result; 
    } 

簡單分析一下：

第一步的時候我們構(gòu)造了一個 StringBuilder 對象，根據(jù)二進(jìn)制字符串的長度和 maxLength 的長度，在前面進(jìn)行補(bǔ) 0 操作，兩者相差多少就在前面補(bǔ)多少個 0，然后將原始的二進(jìn)制補(bǔ)到最后，得到一個新的二進(jìn)制字符串;

第二步我們遍歷 Map，將二進(jìn)制字符串中的每一位與之前構(gòu)造的全是 0 的 sum 數(shù)組進(jìn)行或運(yùn)算操作，并將結(jié)果寫到 sum 數(shù)組對應(yīng)的位置上，因?yàn)榻?jīng)過第一步的補(bǔ) 0 這里 Map 中所有的 value 的長度是一樣的;

第三步再遍歷 sum 數(shù)組，將每一位累加起來，得到的結(jié)果就是我們需要的結(jié)果，因?yàn)?sum 數(shù)組中只有 1 和 0，所以總和就是 1 的個數(shù)。

代碼寫到這里，內(nèi)心毫無波瀾，沒有一絲絲感覺，畢竟只要思路清晰，代碼的實(shí)現(xiàn)都是小事。

然而就當(dāng)把這個功能發(fā)到測試環(huán)境的時候，測試妹妹反饋某些情況下在前端頁面等待的時間太長了，loading 的小按鈕一直轉(zhuǎn)不停，往往要 4，5 秒的時間才能得到結(jié)果，體驗(yàn)太差了。

抱著以用戶體驗(yàn)為目標(biāo)的決心(其實(shí)是怕被扣工資)，阿粉看了一下測試用例，追蹤了一下代碼結(jié)果發(fā)現(xiàn)當(dāng)這個方法中 map 中的 key 達(dá)到 1000+ 的時候，整個方法竟然執(zhí)行了4s 多!是可忍孰不可忍，作為一個有追求的程序員怎么能讓這種情況發(fā)生了，不得已阿粉走上了優(yōu)化這個方法的道路。

優(yōu)化之前我們當(dāng)然需要知道有哪些可以優(yōu)化的地方，看下這段代碼，發(fā)現(xiàn)里面好多 for 循環(huán)，毫無疑問我們的優(yōu)化目標(biāo)就是降低 for 循環(huán)的個數(shù)以及次數(shù)。

仔細(xì)看了一下代碼，我們想一想真的有必要要先將每個二進(jìn)制字符串進(jìn)行前面補(bǔ) 0 的動作嗎?是不是可以在進(jìn)行或運(yùn)算的時候發(fā)現(xiàn)位數(shù)不夠的時候自動補(bǔ) 0 呢?還有就是我們真的有必要在最后遍歷 sum 數(shù)組，得到 1 的個數(shù)嗎?因?yàn)槭腔蜻\(yùn)算，只要 sum[i] 是 1 了，或運(yùn)算得到的結(jié)果就一定是 1 那這個時候是不是就可以得到結(jié)果呢?

帶著這兩個問題，將代碼優(yōu)化成了下面的樣子：

public static long version2(Map<String, String> map, int maxLength) { 
        long result = 0L; 
        if (!CollectionUtils.isEmpty(map)) { 
            Integer[] sum = new Integer[maxLength]; 
            for (int i = 0; i < maxLength; i++) { 
                sum[i] = 0; 
            } 
            // 1. 將長度不夠 maxLength 長的二進(jìn)制字符串前面補(bǔ) 0 
            // 2. 并將每個關(guān)鍵字的二進(jìn)制字符串按位進(jìn)行或 | 運(yùn)算 
            for (Map.Entry<String, String> m : map.entrySet()) { 
                String value = m.getValue(); 
                for (int i = maxLength - 1; i >= 0; i--) { 
                    char c; 
                    int index = value.length() - i - 1; 
                    if (index < 0) { 
                        c = '0'; 
                    } else { 
                        c = value.charAt(index); 
                    } 
                    //3. 統(tǒng)計(jì)計(jì)算結(jié)果中 1 的個數(shù) 
                    int temp = sum[i]; 
                    sum[i] = sum[i] | Integer.parseInt(String.valueOf(c)); 
                    if (temp == 0 && sum[i] == 1) { 
                        result += 1; 
                    } 
                } 
            } 
        } 
        return result; 
    } 

簡單分析一下，我們可以從數(shù)組的最后一位開始進(jìn)行按位或運(yùn)算，這樣當(dāng)?shù)玫降?index 小于 0 的時候，表示該二進(jìn)制數(shù)組已經(jīng)遍歷完了，那么這個時候如果還沒有達(dá)到 maxLength 的長度，我們就補(bǔ) 0，用 0 進(jìn)行或運(yùn)算;同時我們在進(jìn)行或運(yùn)算的時候，通過記錄 sum[i] 在或運(yùn)算前和或運(yùn)算后差異來記錄 1 的個數(shù)，我們只記錄或運(yùn)算前 sum[i] == 0 或運(yùn)算后 sum[i] == 1 的值，就是我們需要的結(jié)果。

經(jīng)過我們優(yōu)化后的代碼，首先從 for 循環(huán)的個數(shù)來看就已經(jīng)減少了，我們測試一下效果如下，這里因?yàn)槎M(jìn)制的數(shù)組很長，不能放到公眾號文章里面，就簡化了。

public static void main(String[] args) { 
    String binaryString1 = "1000101010010101010101010100110101010101001001010101010101..."; 
        Map<String, String> map = new HashMap<>(16); 
        for (int i = 0; i < 1500; i++) { 
            map.put("key_" + i, binaryString1); 
        } 
        int maxLength = 0; 
        for (Map.Entry<String, String> m : map.entrySet()) { 
            maxLength = Math.max(maxLength, m.getValue().length()); 
        } 
        long start1 = System.currentTimeMillis(); 
        long aLong1 = version1(map, maxLength); 
        System.out.println("version1:" + aLong1 + ":" + (System.currentTimeMillis() - start1)); 
 
        long start2 = System.currentTimeMillis(); 
        long aLong2 = version2(map, maxLength); 
        System.out.println("version1:" + aLong2 + ":" + (System.currentTimeMillis() - start2));     
} 

從測試結(jié)果我們可以看到，當(dāng) map size 在 1000 的時候，version1 耗費(fèi)了 4034ms，version2 耗費(fèi)了 2090ms，性能提升接近 2 倍說明我們的優(yōu)化還是有效果的。

事情到了這里，你以為就結(jié)束了嗎?那就錯了，因?yàn)檫€沒有提到阿粉前面說的知識點(diǎn)，下面重點(diǎn)來了，請注意看。version2 的代碼我們能不能再優(yōu)化了?不管能不能再優(yōu)化，有一行代碼看起來總是讓人很不爽，那就是sum[i] = sum[i] | Integer.parseInt(String.valueOf(c)); 這一行，將 char 字符，轉(zhuǎn)換成 String，再通過 Integer.parseInt() 轉(zhuǎn)成 int 的 0 或者 1 來進(jìn)行或運(yùn)算。很容易讓人想到，這里經(jīng)過幾層的包裝轉(zhuǎn)換，是很浪費(fèi)資源的，所以這里也是我們優(yōu)化的點(diǎn)。

這一行的目標(biāo)是進(jìn)行或運(yùn)算，Integer.parseInt(String.valueOf(c)) 的目標(biāo)就是將 char 的 0 或者 1 轉(zhuǎn)成 int 的 0 或者 1。那為什么我們不直接用 c ?然后我們測試了一下下面的代碼，結(jié)果跟我們想象的不太一樣，但是這個結(jié)果也是可以用的，我們再后面減掉一個 48 是不是就可以了呢?得到的就是 0 和 1 了。

經(jīng)過上面的測試，我們 version3 版本的代碼如下：

public static long version3(Map<String, String> map, int maxLength) { 
        long result = 0L; 
        if (!CollectionUtils.isEmpty(map)) { 
            Integer[] sum = new Integer[maxLength]; 
            for (int i = 0; i < maxLength; i++) { 
                sum[i] = 0; 
            } 
            // 1. 將長度不夠 maxLength 長的二進(jìn)制字符串前面補(bǔ) 0 
            // 2. 并將每個關(guān)鍵字的二進(jìn)制字符串按位進(jìn)行或 | 運(yùn)算 
            for (Map.Entry<String, String> m : map.entrySet()) { 
                String value = m.getValue(); 
                for (int i = maxLength - 1; i >= 0; i--) { 
                    char c; 
                    int index = value.length() - i - 1; 
                    if (index < 0) { 
                        c = '0'; 
                    } else { 
                        c = value.charAt(index); 
                    } 
                    //3. 統(tǒng)計(jì)計(jì)算結(jié)果中 1 的個數(shù) 
                    int temp = sum[i]; 
                    sum[i] = sum[i] | ((int) c - 48); 
                    if (temp == 0 && sum[i] == 1) { 
                        result += 1; 
                    } 
                } 
            } 
        } 
        return result; 
    } 

測試結(jié)果如下：

我們發(fā)現(xiàn)在同樣大小的情況下，version3 版本直接進(jìn)入到了 1 秒了，只用了 746ms，這次的優(yōu)化性能提升了接近 5.5 倍!至此此次的性能優(yōu)化終于畫上了句號。

相信看到這里的小伙伴也知道了阿粉前面提到的知識點(diǎn)是什么了，那就是 char 類型可以跟 int 做轉(zhuǎn)換，其實(shí)這就是我們學(xué)編程之初學(xué)到的 ASCII 碼，可能學(xué)習(xí)的時候并沒有想過要怎么用，當(dāng)真正用到的時候就會發(fā)現(xiàn)真香!

總結(jié)一下今天阿粉給大家介紹了如果將一個運(yùn)行 4s 多的方法，優(yōu)化到了 800ms 以內(nèi)，通過實(shí)戰(zhàn)介紹了 ASCII 在我們?nèi)粘９ぷ髦械膽?yīng)用。如果大家覺得看了文章的內(nèi)容有收獲，歡迎小伙伴們收藏，點(diǎn)贊，評論，轉(zhuǎn)發(fā)，每一次互動都是對阿粉的鼓勵。