大數(shù)組元素差異removeAll與Map效率對(duì)比
正文
考慮這樣一個(gè)場(chǎng)景，對(duì)兩個(gè)列表對(duì)象，listA 和 listB，比較二者差異，找出只在 listA 中出現(xiàn)的元素列表 onlyListA，找出只在 listB 中出現(xiàn)的元素列表 onlyListB。
removeAll實(shí)現(xiàn)
很容易想到借助 removeAll 實(shí)現(xiàn)，代碼如下。
List<String> listA = new ArrayList<>(); List<String> listB = new ArrayList<>(); //僅在數(shù)組A中出現(xiàn)的元素 List<String> onlyListA = new ArrayList<>(listA); onlyListA.removeAll(listB); //僅在數(shù)組B中出現(xiàn)的元素 List<String> onlyListB = new ArrayList<>(listB); onlyListB.removeAll(listA);
當(dāng)數(shù)組元素較少時(shí)，借助 removeAll 實(shí)現(xiàn)并沒(méi)有任何問(wèn)題。不過(guò)在數(shù)組元素較大時(shí)，removeAll 方法耗時(shí)會(huì)較大。執(zhí)行如下測(cè)試方法，對(duì)數(shù)組元素個(gè)數(shù)為1000，1W，10W，100W 的場(chǎng)景進(jìn)行測(cè)試。
public class ListDiffTest {
public static void main(String[] args) {
testRemoveAllCostTime(1000);
testRemoveAllCostTime(10000);
testRemoveAllCostTime(100000);
testRemoveAllCostTime(1000000);
}
public static void testRemoveAllCostTime(int size) {
List<String> listA = dataList(size);
listA.add("onlyAElement");
List<String> listB = dataList(size + 3);
long startTime = System.currentTimeMillis();
//僅在數(shù)組A中出現(xiàn)的元素
List<String> onlyListA = new ArrayList<>(listA);
onlyListA.removeAll(listB);
//僅在數(shù)組B中出現(xiàn)的元素
List<String> onlyListB = new ArrayList<>(listB);
onlyListB.removeAll(listA);
System.out.println("僅在集合A中出現(xiàn)的元素：" + onlyListA);
System.out.println("僅在集合B中出現(xiàn)的元素：" + onlyListB);
System.out.println("元素個(gè)數(shù) = " + size + "時(shí)，比對(duì)耗時(shí)：" + (System.currentTimeMillis() - startTime) + " 毫秒");
}
private static List<String> dataList(int size) {
List<String> dataList = new ArrayList<>();
for (int i = 0; i < size; i++) {
dataList.add("" + i);
}
return dataList;
}
}
測(cè)試結(jié)果如下
僅在集合A中出現(xiàn)的元素：[onlyAElement]
僅在集合B中出現(xiàn)的元素：[1000, 1001, 1002]
元素個(gè)數(shù) = 1000時(shí)，比對(duì)耗時(shí)：19 毫秒
元素個(gè)數(shù) = 10000時(shí)，比對(duì)耗時(shí)：299 毫秒 #1W
元素個(gè)數(shù) = 100000時(shí)，比對(duì)耗時(shí)：24848 毫秒 #10W
元素個(gè)數(shù) = 1000000時(shí)，比對(duì)耗時(shí)：3607607 毫秒 #100W 約60m
可以看到，當(dāng)數(shù)組元素達(dá)到百萬(wàn)級(jí)時(shí)，耗時(shí)將達(dá)60min上下。
借助Map實(shí)現(xiàn)
此處給出一種優(yōu)化方式，借助 Map 計(jì)數(shù)，將 List 集合中的元素作為 Map 的 key，元素出現(xiàn)的次數(shù)作為 Map 的 value。代碼實(shí)現(xiàn)如下。
import io.vavr.Tuple2;
public class ListDiffTest {
public static void main(String[] args) {
testDifferListByMapCostTime(1000);
testDifferListByMapCostTime(10000);
testDifferListByMapCostTime(100000);
testDifferListByMapCostTime(1000000);
}
public static void testDifferListByMapCostTime(int size) {
List<String> listA = dataList(size);
listA.add("onlyAElement");
List<String> listB = dataList(size + 3);
long startTime = System.currentTimeMillis();
//僅在數(shù)組A中出現(xiàn)的元素
List<String> onlyListA = tuple2._1;;
//僅在數(shù)組B中出現(xiàn)的元素
List<String> onlyListB = tuple2._2;
System.out.println("僅在集合A中出現(xiàn)的元素：" + onlyListA);
System.out.println("僅在集合B中出現(xiàn)的元素：" + onlyListB);
System.out.println("元素個(gè)數(shù) = " + size + "時(shí)，比對(duì)耗時(shí)：" + (System.currentTimeMillis() - startTime) + " 毫秒");
}
/**
* 通過(guò)Map計(jì)數(shù)方式 比較兩個(gè)數(shù)組之間的差異
*
* @param listA 數(shù)組A
* @param listB 數(shù)組B
* @param <E> 元素類(lèi)型
* @return Tuple2對(duì)象 onlyAList-只在數(shù)組A存在的元素 onlyBList-只在數(shù)組B存在的元素
*/
public static <E> Tuple2<List<E>, List<E>> getDiffListBtMapCompare(List<E> listA, List<E> listB) {
ValidateUtils.validateNotNull(listA, "listA");
ValidateUtils.validateNotNull(listB, "listB");
List<E> onlyAList = new ArrayList<>();
List<E> onlyBList = new ArrayList<>();
if (CollectionUtils.isEmpty(listA)) {
return Tuple.of(onlyAList, listB);
} else if (CollectionUtils.isEmpty(listB)) {
return Tuple.of(listA, onlyBList);
}
/**
* listA中元素 初始化計(jì)數(shù) = 1
* listB中元素 初始化計(jì)數(shù) = -2
* 遍歷累加后
* 相同元素 計(jì)數(shù) = 2
* 僅A中出現(xiàn)元素 計(jì)數(shù) = 1
* 僅A中出現(xiàn)元素 計(jì)數(shù) = -1
*/
Map<E, Integer> countMap = new HashMap<>(Math.max(listA.size(), listB.size()));
for (E eleA : listA) {
countMap.put(eleA, 1);
}
for (E eleB : listB) {
countMap.put(eleB, 1 + countMap.getOrDefault(eleB, -2));
}
countMap.forEach((k, v) -> {
//獲取不同元素集合
if (v == 1) {
onlyAList.add(k);
} else if (v == -1) {
onlyBList.add(k);
}
});
return Tuple.of(onlyAList, onlyBList);
}
}
測(cè)試結(jié)果如下
僅在集合A中出現(xiàn)的元素：[onlyAElement]
僅在集合B中出現(xiàn)的元素：[1000, 1002, 1001]
元素個(gè)數(shù) = 1000時(shí)，比對(duì)耗時(shí)：8 毫秒
元素個(gè)數(shù) = 10000時(shí)，比對(duì)耗時(shí)：19 毫秒 #1W
元素個(gè)數(shù) = 100000時(shí)，比對(duì)耗時(shí)：28 毫秒 #10W
元素個(gè)數(shù) = 1000000時(shí)，比對(duì)耗時(shí)：96 毫秒 #100W
元素個(gè)數(shù) = 10000000時(shí)，比對(duì)耗時(shí)：5320 毫秒 #1000W
removeAll耗時(shí)分析
最后，來(lái)分析下為什么在大數(shù)組元素比較時(shí)，removeAll 性能較差。
removeAll方法中，先進(jìn)行判空，然后調(diào)用batchRemove()方法
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
batchRemove()方法中，使用 for 循環(huán)對(duì)集合進(jìn)行遍歷。第 1 層循環(huán)需要執(zhí)行listA.size()次。循環(huán)體中調(diào)用了contains()方法來(lái)確定集合 B 是否含有該元素。
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
contains()方法的實(shí)現(xiàn)如下，內(nèi)部又調(diào)用了indexOf()方法。indexOf()方法內(nèi)部又進(jìn)行了一層 for 循環(huán)遍歷。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
- 至此，可以看到，按照平均每次遍歷要進(jìn)行
list.size() / 2次計(jì)算，假設(shè)集合 A 的元素個(gè)數(shù)為 m，集合 B 的元素個(gè)數(shù)為 n，則兩重 for 循環(huán)下，會(huì)執(zhí)行m*n/2次。對(duì)于兩個(gè)千萬(wàn)量級(jí)的數(shù)組，將執(zhí)行 100 億次計(jì)算?。。?/li>
由此給出一個(gè)結(jié)論，對(duì)于大數(shù)組元素差異比較，不建議使用 removeAll，可以借助 Map 實(shí)現(xiàn)。
參考 http://m.fzitv.net/article/261737.htm
以上就是大數(shù)組元素差異removeAll與Map效率對(duì)比的詳細(xì)內(nèi)容，更多關(guān)于removeAll Map效率對(duì)比的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
詳解手把手Maven搭建SpringMVC+Spring+MyBatis框架(超級(jí)詳細(xì)版)
本篇文章主要介紹了手把手Maven搭建SpringMVC+Spring+MyBatis框架(超級(jí)詳細(xì)版),具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-12-12
大家好，本篇文章主要講的是Java給PDF加水印并合并多個(gè)文件，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下2022-02-02
IDEA中添加xml配置文件時(shí),顯示file問(wèn)題
這篇文章主要介紹了IDEA中添加xml配置文件時(shí),顯示file問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12
簡(jiǎn)單了解Spring Web相關(guān)模塊運(yùn)行原理
這篇文章主要介紹了簡(jiǎn)單了解Spring Web相關(guān)模塊運(yùn)行原理,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-06-06
這篇文章主要介紹了Java中包的概念和用法,結(jié)合具體案例形式分析了java包的概念、原理、使用方法及相關(guān)操作注意事項(xiàng),需要的朋友可以參考下2019-09-09
springboot使用webservice發(fā)布和調(diào)用接口的實(shí)例詳解
本文介紹了如何在Springboot中使用webservice發(fā)布和調(diào)用接口,涵蓋了必要的依賴(lài)添加和代碼示例,文中提供了服務(wù)端和客戶端的實(shí)現(xiàn)方法,以及如何設(shè)置端口和服務(wù)地址,幫助讀者更好地理解和應(yīng)用Springboot結(jié)合webservice的技術(shù)2024-10-10
這篇文章主要介紹了java拋出異常與finally實(shí)例解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-10-10
kafka 重新分配partition和調(diào)整replica的數(shù)量實(shí)現(xiàn)
當(dāng)需要提升Kafka集群的性能和負(fù)載均衡時(shí),可通過(guò)kafka-reassign-partitions.sh命令手動(dòng)重新分配Partition,增加節(jié)點(diǎn)后,可以將Topic的Partition的Leader節(jié)點(diǎn)均勻分布,以提高寫(xiě)入和消費(fèi)速度,感興趣的可以了解一下2022-03-03
在MyBatis中實(shí)現(xiàn)一對(duì)多查詢(xún)和多對(duì)一查詢(xún)的方式詳解(各兩種方式)
今天通過(guò)兩種方法分別給大家介紹在MyBatis中實(shí)現(xiàn)一對(duì)多查詢(xún)和多對(duì)一查詢(xún)的方式，每種方式通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友參考下吧2022-01-01
這篇文章主要介紹了Java編程思想對(duì)象的容納實(shí)例詳解，內(nèi)容比較詳細(xì)，涵蓋的東西也比較多，具有參考價(jià)值，需要的朋友了解下。2017-09-09