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