[TS] Set、flatMap 優化資料搜尋
最近在工作中遇到需要從複雜的資料結構中提取特定資料的問題，面對這種多層結構的資料直接暴力搜尋效能明顯不太理想，正確的方式應該是先將資料做「扁平化處理」，再透過更高效的搜尋策略來提升效能。
情境與實作
最近工作上碰到需要從一個多層結構的資料中撈出特定資料，然後從另一筆資料中撈出 id 互相匹配後，再組合出一個乾淨的資料做渲染。
假設現在需要從 product_variation 的 categories 中先撈出 giveaways，其中會夾雜不同資料，你需要透過 isGiveaway 去判斷。
結構可能會長這樣：
{
"categories": [
{
"id": 1,
"name": "優惠活動",
"subcategories": [
{
"id": 11,
"name": "滿額贈品",
"products": [
{
"product_id": 102456,
"name": "高級禮盒",
"isGiveaway": true,
"details": {
"price": 0,
"attributes": {
"color": "紅色",
"size": "大"
},
"availability": {
"inStock": true,
"limitedEdition": false
}
}
},
{
"product_id": 102457,
"name": "豪華贈品",
"isGiveaway": true,
"details": {
"price": 0,
"attributes": {
"color": "金色",
"size": "中"
},
"availability": {
"inStock": false,
"limitedEdition": true
}
}
}
]
}
]
},
{
...
}
]
}
另外一個 product_id 已經提供，只需要從 selectedProducts 中撈出即可。
{
"selectedProducts": [
{
"product_id": 102780,
"name": "智能手機",
"isGiveaway": false
},
{
"product_id": 102457,
"name": "豪華贈品",
"isGiveaway": true
},
],
}
大致看一下結構有三層，至少需要先用三個迭代，再透過搜尋撈出特定資料後進行匹配。
const giveaways = productTable.categories.map((category) =>
category.subcategories.map((subcategory) =>
subcategory.products.filter((product) =>
productSelected.selectedProducts?.some((selectedProduct) =>
selectedProduct.product_id === product.product_id && selectedProduct.isGiveaway
)
)
)
).flat(2) // 使用 flat 將資料扁平化成二維
結果可能會像這樣
但這樣的寫法效能是很差的，過程中使用了兩個 map 又一個 filter 和 some，雖然最後有使用了 flat 將資料攤平，但還有很大的優化空間。
-
盡量避免嵌套式結構，必要時寫成一個 constants
-
flat 和 map 可以整合成 flatMap
-
搜尋策略可以改用效能更高的 set
優化後的結果：
const selectedProductIds = new Set(
productSelected.selectedProducts.map((selectedProduct) => selectedProduct.product_id)
)
const subcategoriesMap = productTable.categories.flatMap((category) => category.subcategories)
const allProducts = subcategoriesMap.flatMap((subcategory) => subcategory.products)
const giveaways = allProducts.filter((product) =>
selectedProductIds.has(product.product_id) && product.isGiveaway
)
來說說這段優化的過程中做了什麼
-
將 selectedProducts 的 product_id 抽出來到 Set 中，Set 有更高的搜尋效率（後續會解釋），減少查找 product_id 的時間成本。
-
使用 flatMap 來將每個 category 中的 subcategories 做扁平化處理，這樣我們就得到了所有的子類別資料，而不需要在內部多次嵌套 map。
-
接著再使用 flatMap 來將每個 subcategory 中的 products 提取出來，這樣所有產品都在一個扁平化的陣列中，避免了多次遍歷和過多的嵌套（這邊 flatMap 其實也可以寫在一起，讓扁平化只做一次，不過抽出來的可讀性與維護性更高）。
-
最後使用 filter 來檢查每個產品是否在 selectedProductIds 中，並且判斷是否為贈品。
這樣優化過後程式碼也變得更簡潔易讀，且在資料量更大時能有更高的效能。
關於 Set 和 flatMap
為何 Set 相較 some 或 find 的效能更高？
Set 的優勢
首先 Set 是一種「無重複的集合」，在搜尋以及去重複的情境具高效能。
它的底層是使用「Hash Table」來實作資料儲存，其搜尋的時間複雜度最高為 𝑂(1)。
而 some 或 find 是基於 Array 實現的，這表示說它們是線性搜尋 𝑂(n) 的，會一個個地遍歷陣列中的元素，直到找到符合條件的元素為止，或者遍歷完整個陣列。
因此在大數據集合中，檢查某個元素是否存在的速度，Set 會比遍歷整個陣列的 some 或 find 快得非常多。
應用情境：
-
去重複：
const setA = [1, 2, 3, 4]; const setB = [3, 4, 5, 6]; const combinedData = new Set([...setA, ...setB]); console.log([...combinedData]); // [1, 2, 3, 4, 5, 6]這段也可以使用 filter 和 indexOf 實作，但 Set 去重複效能比兩者來的更高其時間複雜度從 𝑂(𝑛^2)（基於 filter + indexOf）降低到 𝑂(𝑛)。
flatMap 的優勢
flatMap 是一個合併了 map 和 flat 操作的方法，如果是分別使用 flat 和 map 就需要遍歷兩次，合併後通過一次遍歷就能完成兩個操作，提高效能。
較適合需要對陣列進行多層處理及扁平化處理的情境。
例如：
const employees = [
{ department: 'IT', members: ['Alice', 'Bob'] },
{ department: 'HR', members: ['Carol', 'David'] },
];
const allMembers = employees.flatMap((employee) => employee.members);
// ['Alice', 'Bob', 'Carol', 'David']
總結
遇到複雜的資料結構可以先嘗試將資料攤平，做扁平化處理後再透過更高效的搜尋策略來過濾出對應的資料。
-
Set：
- 底層使用 Hash Table 實作，善於處理重複數據和集合操作，時間複雜度更低。
- 適合需要頻繁搜尋和比較的情境。
-
flatMap：
- 合併 flat 和 map 方法，在單次遍歷中同時完成映射和扁平化，降低記憶體和時間的消耗。
- 適合處理嵌套結構的資料，將資料映射並進行扁平化處理，從而有效簡化處理過程。