Java 中一個你不常用，但是關鍵時刻可以幫我們提升性能的一個知識點
本文轉載自微信公眾號「Java極客技術」，作者鴨血粉絲Tang 。轉載本文請聯系Java極客技術公眾號。
最近阿粉在實現一個功能的時候，遇到了一個性能問題，一個方法在某些場景下運行時長達到了 4s 多，雖然說業務功能是實現了，但是不管是從業務的角度還是作為一個有追求的程序員，都是不能接受的，所以優化這個方法勢在必行。在優化的過程中就用到了本文要說明的一個知識點，看阿粉慢慢道來。
在提供優化代碼之前，先簡單的描述一下這個方法做的事情，要做的事情很簡單，就是返回一個整數，整數表示的是二進制數組中有多少個 1。給到了入參是一個 Map
根據我們上面的分析，列一下我們寫代碼的步驟：
- 因為我們要按位進行或運算，所以二進制的長度應該要一樣才行，我們取最長的二進制的長度為 maxLength，所有沒有這么長的二進制字符串，我們需要進行前面補 0 ;
- 將所有的二進制字符串按位進行或運算;
- 遍歷最終的數組輸出 1 的個數;
按照這個思路，我們可以寫出下面的代碼，maxLength 作為入參傳遞到我們的方法中。
- public static long version1(Map<String, String> map, int maxLength) {
- long result = 0L;
- if (!CollectionUtils.isEmpty(map)) {
- //1. 將長度不夠 maxLength 長的二進制字符串前面補 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. 將每個關鍵字的二進制字符串按位進行或 | 運算
- 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. 統計計算結果中 1 的個數
- for (Integer integer : sum) {
- result += integer;
- }
- }
- return result;
- }
簡單分析一下：
第一步的時候我們構造了一個 StringBuilder 對象，根據二進制字符串的長度和 maxLength 的長度，在前面進行補 0 操作，兩者相差多少就在前面補多少個 0，然后將原始的二進制補到最后，得到一個新的二進制字符串;
第二步我們遍歷 Map，將二進制字符串中的每一位與之前構造的全是 0 的 sum 數組進行或運算操作，并將結果寫到 sum 數組對應的位置上，因為經過第一步的補 0 這里 Map 中所有的 value 的長度是一樣的;
第三步再遍歷 sum 數組，將每一位累加起來，得到的結果就是我們需要的結果，因為 sum 數組中只有 1 和 0，所以總和就是 1 的個數。
代碼寫到這里，內心毫無波瀾，沒有一絲絲感覺，畢竟只要思路清晰，代碼的實現都是小事。
然而就當把這個功能發到測試環境的時候，測試妹妹反饋某些情況下在前端頁面等待的時間太長了，loading 的小按鈕一直轉不停，往往要 4，5 秒的時間才能得到結果，體驗太差了。
抱著以用戶體驗為目標的決心(其實是怕被扣工資)，阿粉看了一下測試用例，追蹤了一下代碼結果發現當這個方法中 map 中的 key 達到 1000+ 的時候，整個方法竟然執行了4s 多!是可忍孰不可忍，作為一個有追求的程序員怎么能讓這種情況發生了，不得已阿粉走上了優化這個方法的道路。
優化之前我們當然需要知道有哪些可以優化的地方，看下這段代碼，發現里面好多 for 循環，毫無疑問我們的優化目標就是降低 for 循環的個數以及次數。
仔細看了一下代碼，我們想一想真的有必要要先將每個二進制字符串進行前面補 0 的動作嗎?是不是可以在進行或運算的時候發現位數不夠的時候自動補 0 呢?還有就是我們真的有必要在最后遍歷 sum 數組，得到 1 的個數嗎?因為是或運算，只要 sum[i] 是 1 了，或運算得到的結果就一定是 1 那這個時候是不是就可以得到結果呢?
帶著這兩個問題，將代碼優化成了下面的樣子：
- 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 長的二進制字符串前面補 0
- // 2. 并將每個關鍵字的二進制字符串按位進行或 | 運算
- 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. 統計計算結果中 1 的個數
- int temp = sum[i];
- sum[i] = sum[i] | Integer.parseInt(String.valueOf(c));
- if (temp == 0 && sum[i] == 1) {
- result += 1;
- }
- }
- }
- }
- return result;
- }
簡單分析一下，我們可以從數組的最后一位開始進行按位或運算，這樣當得到的 index 小于 0 的時候，表示該二進制數組已經遍歷完了，那么這個時候如果還沒有達到 maxLength 的長度，我們就補 0，用 0 進行或運算;同時我們在進行或運算的時候，通過記錄 sum[i] 在或運算前和或運算后差異來記錄 1 的個數，我們只記錄或運算前 sum[i] == 0 或運算后 sum[i] == 1 的值，就是我們需要的結果。
經過我們優化后的代碼，首先從 for 循環的個數來看就已經減少了，我們測試一下效果如下，這里因為二進制的數組很長，不能放到公眾號文章里面，就簡化了。
- 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));
- }
從測試結果我們可以看到，當 map size 在 1000 的時候，version1 耗費了 4034ms，version2 耗費了 2090ms，性能提升接近 2 倍說明我們的優化還是有效果的。
事情到了這里，你以為就結束了嗎?那就錯了，因為還沒有提到阿粉前面說的知識點，下面重點來了，請注意看。version2 的代碼我們能不能再優化了?不管能不能再優化，有一行代碼看起來總是讓人很不爽，那就是sum[i] = sum[i] | Integer.parseInt(String.valueOf(c)); 這一行，將 char 字符，轉換成 String，再通過 Integer.parseInt() 轉成 int 的 0 或者 1 來進行或運算。很容易讓人想到，這里經過幾層的包裝轉換，是很浪費資源的，所以這里也是我們優化的點。
這一行的目標是進行或運算，Integer.parseInt(String.valueOf(c)) 的目標就是將 char 的 0 或者 1 轉成 int 的 0 或者 1。那為什么我們不直接用 c ?然后我們測試了一下下面的代碼，結果跟我們想象的不太一樣，但是這個結果也是可以用的，我們再后面減掉一個 48 是不是就可以了呢?得到的就是 0 和 1 了。
經過上面的測試，我們 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 長的二進制字符串前面補 0
- // 2. 并將每個關鍵字的二進制字符串按位進行或 | 運算
- 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. 統計計算結果中 1 的個數
- int temp = sum[i];
- sum[i] = sum[i] | ((int) c - 48);
- if (temp == 0 && sum[i] == 1) {
- result += 1;
- }
- }
- }
- }
- return result;
- }
測試結果如下：
我們發現在同樣大小的情況下，version3 版本直接進入到了 1 秒了，只用了 746ms，這次的優化性能提升了接近 5.5 倍!至此此次的性能優化終于畫上了句號。
相信看到這里的小伙伴也知道了阿粉前面提到的知識點是什么了，那就是 char 類型可以跟 int 做轉換，其實這就是我們學編程之初學到的 ASCII 碼，可能學習的時候并沒有想過要怎么用，當真正用到的時候就會發現真香!
總結一下今天阿粉給大家介紹了如果將一個運行 4s 多的方法，優化到了 800ms 以內，通過實戰介紹了 ASCII 在我們日常工作中的應用。如果大家覺得看了文章的內容有收獲，歡迎小伙伴們收藏，點贊，評論，轉發，每一次互動都是對阿粉的鼓勵。
