我有兩個(gè)大型（1000 多個(gè)對(duì)象）ArrayList，我需要比較和操作它們。我基本上需要從 ArrayList A 中獲取一個(gè)值，在 ArrayList B 中尋找一個(gè)匹配的對(duì)象，然后操作 B 中的對(duì)象。我需要在 A 的所有對(duì)象中執(zhí)行此操作。我需要在應(yīng)用程序中經(jīng)常執(zhí)行此操作。訂單未知，尺寸會(huì)有所不同。(pseudocode)ArrayList<myObject> AArrayList<myObject> B我可以遍歷 B 中的每個(gè)項(xiàng)目，為 A 中的每個(gè)實(shí)體尋找與 A 中的實(shí)體匹配的項(xiàng)目。這看起來(lái)效率很低。(pseudocode)for (each object in A){loop through all of B and find it}將 B 轉(zhuǎn)換為 HashMap 是否值得（使用我正在比較的特定值作為鍵，將對(duì)象作為值），然后以這種方式搜索 B，然后在完成處理后將該臨時(shí) HashMap 轉(zhuǎn)換回 ArrayList ？(pseudocode)convert B to HashMap<myObject.myValue,myObject> Cfor (each object in A){look up the value in C}convert C back to an ArrayList這是一個(gè)好主意嗎？或者這是過(guò)早/不必要的優(yōu)化？謝謝你。（背景：數(shù)據(jù)作為 ArrayList 從服務(wù)傳給我——前端需要一個(gè) ArrayList 用于視圖層。我試圖使這個(gè)中間層處理更有效率——但入口和出口對(duì)象必須是 ArrayList（或一些其他列表））
1 回答
森林海
TA貢獻(xiàn)2011條經(jīng)驗(yàn) 獲得超2個(gè)贊
是的，對(duì)于大量的人來(lái)說(shuō)，aHashMap是有益的。
您的初始算法將花費(fèi)很長(zhǎng)時(shí)間，在嵌套的 for 循環(huán)中遍歷兩個(gè)列表。這是一個(gè) O(n 2 ) 算法。A即使假設(shè)和中各有 1000 個(gè)項(xiàng)目，并假設(shè)比較兩個(gè)單獨(dú)的項(xiàng)目（一個(gè)來(lái)自和一個(gè)來(lái)自）B的成本為 1 ，您也會(huì)看到 500k 次比較（避免比較每個(gè)項(xiàng)目?jī)纱危?。?jīng)常這樣做會(huì)導(dǎo)致性能下降。AB
假設(shè)你有一個(gè)很好的對(duì)象哈希碼算法，從 a 中查找一個(gè)值HashMap是 O(1) 訪問。您仍然會(huì)花費(fèi) O(n) 時(shí)間來(lái)構(gòu)建它，但如果您有大量項(xiàng)目，那與 O(n 2 ) 相比就不算什么了。
使用來(lái)自“B”的數(shù)據(jù)構(gòu)建HashMap一次“C”并多次使用它，只要B的信息沒有改變。如果您“需要經(jīng)常這樣做”，那么性能會(huì)更好，因?yàn)镠ashMap它已經(jīng)構(gòu)建好了——只需重用它。
如果需要維護(hù)順序，將B列表索引作為值存儲(chǔ)在哈希映射中。
您不需要“將該臨時(shí)哈希圖轉(zhuǎn)換回?cái)?shù)組列表”，因?yàn)閯?chuàng)建HashMap“C”不會(huì)破壞原始列表“B”。要注意的一件事是，如果列表中的對(duì)象B發(fā)生變化，則強(qiáng)制更新以HashMap保持一致。另一件需要注意的事情是你對(duì)非常大的列表的內(nèi)存使用——你能把對(duì)象、列表和散列圖保存在內(nèi)存中嗎？
你的偽代碼：
for each index in B:
get object b
put in hash map C values (b, index)
for each a in A:
if found in hash map C: do something with found object
對(duì)于較小的數(shù)字，O(n 2 ) 性能時(shí)間將足夠小，以至于HashMap不值得構(gòu)建它。這是您需要做出的決定——您需要決定何時(shí)列表足夠大，以至于構(gòu)建HashMap和使用它值得HashMap構(gòu)建成本。
添加回答
舉報(bào)
0/150
提交
取消