ArrayList或獨特密鑰的Map，更快？

Question

示例： -

列表A包含N個對象。
列表B包含M個對象。

列表A中的一個對象將僅匹配列表B中的一個對象。 匹配條件由我定義，假設它是項目編號，從日期和區域代碼。如果這些值匹配，那麼我會將列表B的對象中的所有其他值複製到列表A的對象中。

解決方案： -有兩種解決方案，哪一種更好或更快？

溶膠1： -只需執行一個循環，以匹配列表B的名單A.對象

溶膠2： -
步驟1： -要創建一個HashMap <字符串，對象>從列表B中刪除。
第2步： -使用該映射來獲取匹配記錄並設置列表A中的值。 如果我創建映射，那麼每個對象的鍵將不同。 假設列表B有1000個對象，那麼如果我想創建HashMap，將會有1000個不同的鍵。

Answer 1

您的第二個解決方案更高效。

解決方案1需要通過n對象（列表B）帶有內部循環的對象（列表B）的循環。因此這是O(n*m)或更準確地說是O(n^2)。

溶液2需要建立時間（構建Map），其是O(m)接着列表A的一次掃描（和名單B查找的成本爲零，因爲HashMap查找是O(1)。因此，這是O(m)+O(n)這相當於O(n)。這是一個更好解決

有一種情況m比n大多的邊緣情況。 - 設置時間和存儲成本可能顯著在這種情況下

Answer 2

第一個解決方案的複雜度爲O（N * M）。

第二個O（N）+ O（M），但消耗更多的內存。

第二種算法速度更快。

Answer 3

讓我回顧一下：（？短）

• 列表的
• 長名單B
• 列表A有一個項目可能符合某些條件的條目B中
• 當該找到B條目，將B中的所有其他條目複製到A中。
• 問題：B上的Map（索引的標準鍵）可以幫助嗎？

您可以從A製作標準的HashSet，然後通過B直到第一個匹配。

也應該好，也快。

但是，一定要使用Map/Set。也許取決於N < < M.