還在用雙層for循環嗎？太慢了

• 2022 年 11 月 3 日
• 筆記
• 技術點

前情提要

我們在開發中經常碰到這樣的場景，查出兩個 list 集合數據，需要根據他們相同的某個屬性為連接點，進行聚合。但是平時我們使用的時候關注過性能嗎？下面讓我們一起來看看它的表現如何。

來個例子

我們現在有兩個 List集合，需要根據他們相同的 personId 進行聚合處理，我們很容易想到的寫法是這樣的：

private static void test1(List<Person> list1, List<Person> list2) {
    for (Person before:list1){
        for (Person after:list2){
            if(before.getPersonId().equals(after.getPersonId())){
               //TODO 業務邏輯
                break;
            }
        }
    }
}

這樣的程式碼是我們開發中最常用的一種方式，數據少的話沒問題。如果數據量大的會很慢，接下來我做一個實驗。看看在 1w 和 10w 的數據量下他的性能如何？

測試程式碼如下：

   public static void main(String[] args) {
        List<Person> list1= new ArrayList<>();
        List<Person> list2= new ArrayList<>();
        for (int i = 0; i < 10_0000; i++) {
            list1.add(Person.builder().personId(Long.valueOf(i+"")).build());
            list2.add(Person.builder().personId(Long.valueOf(i+"")).build());
        }
        long start = System.currentTimeMillis();
        test1(list1, list2);
        System.out.println("for循環耗時："+(System.currentTimeMillis()-start));

1w 耗時：343

10w 耗時：64285

僅僅 10w 的數據竟然達到了 64 秒多，可以看出它的性能是多麼差了吧。

那怎麼優化呢？我們可以把第二個 list 轉為 map 的方式來做，示例如下：

程式碼如下：

private static void test2(List<Person> list1, List<Person> list2) {
    Map<Long, Person> baseMap =
            list2.stream().collect(Collectors.toMap(Person::getPersonId, Function.identity()));
    for (Person before:list1){
        Person after = baseMap.get(before.getPersonId());

    }
}

接下來我們再進行下性能測試。

1w 耗時：88

10w 耗時：95

可以看出速度快了上百倍不止，如果還有小夥伴用第一種方式的話就趕緊優化了吧。

思考

我們想想第一種為什麼會慢呢？

在第二個循環里他需要從 0 開始遍歷所有的元素來進行比對，數據量越大，它需要遍歷的數就越多，所以很慢。

所以如果我們業務上兩個集合的大小和順序一致（即能知道應該第二個循環能匹配上的元素在第幾個)，那麼就能避免掉大量的循環。

示例如下：

我們直接在第二層循環的時候，將下標先指定為和第一層循環的一致，如果他們倆屬性相同，立馬跳出；進行第二次循環。

private static void test3(List<Person> list1, List<Person> list2) {
    for (int i=0;i<list1.size();i++){
        int jj = 0;
        for (int j = i; j < list2.size(); j++) {
            if (jj == list2.size()) {
                break;
            }

            if(list1.get(i).getPersonId().equals(list2.get(j).getPersonId())){
                // 編寫具體的邏輯
                break;
            }
            if (j == list2.size() - 1) j = -1;
            jj += 1;
        }
    }
}

性能測試如下：

1w 耗時：2

10w 耗時：13

我們發現又更加快了。

下面是總體的測試數據：

總結：如果數據量小於 5000，推薦就用雙層 for 循環，如果大於 5000，則使用循環+map 的方式。

如果兩個集合順序一致，則可以用改良版的 for 循環