提高每个循环的性能，每个循环都有一个内部循环

Question

AS 4.1.1
Kotlin 1.4.10

编写一个带有内部 forloop 的 for 循环来检查库存项目数量。检查购物车中商品的数量是否大于当前库存商品的数量。

使用内部 for 循环似乎是一种非常幼稚的方法，即使它有效。

只是想知道是否有更好的方法来做到这一点：

对于 curentSkuQuantity 我有一个这样的数据类：

data class CurrentSkuQuantity(
    val sku: String,
    val quantity: Int)

在 RxJava 以当前库存水平返回成功后，我检查 sku 是否与购物车项目相同。然后比较它们的数量，看看是否足够。

onSuccess = { currentSkuQuantity ->
                    val cartList = cartProvider.cdsCart?.items
                    var hasStockShortage = false

                    currentSkuQuantity.forEach { currentStockItem ->
                        cartList?.forEach { cartItem ->
                            // Check that we are checking the correct sku item
                            if(currentStockItem.sku == cartItem.sku) {
                                // Check the quantity is enough
                                if(cartItem.qty > currentStockItem.quantity) {
                                    // Not enough stock
                                    hasStockShortage = true
                                }
                            }
                        }
                    }

                    if(!hasStockShortage) {
                        gotoCheckout()
                    }
                    else {
                        gotoCart()
                    }
                }

Answer 1

正如您所说，嵌套循环的性能可能会更好。匹配两个列表的项目的最佳方法是将其中一个转换为地图，就像Tenfour04在他的回答中提到的那样。这样，操作的时间复杂度从 降低O(n*m)到O(n+m)（即线性），其中n和m是列表大小的顺序。

（O(n)用于从cartList项目创建地图并O(m)迭代currentSkuQuantity列表）

为了实现这一点，有两个有益的收集操作：

• associateBy: 从列表创建地图
• any: 检查列表项的条件

以上两个功能都很O(n)复杂，帮助我们以O(n+m)更简单的方式实现。

onSuccess = { currentSkuQuantity ->
    val cartList = cartProvider.cdsCart?.items

    val hasStockShortage = cartList?.associateBy({ it.sku }, { it.qty })?.let { map ->
        currentSkuQuantity.any { it.quantity < map[it.sku] ?: 0 }
    } ?: false

    if(!hasStockShortage) gotoCheckout()
    else gotoCart()
}

请注意，上述代码段在三个方面具有优势：

1. 将整体时间复杂度从 降低O(n*m)到O(n+m)。
2. any在迭代列表方面是有效的。因此，如果至少有一个元素与条件匹配，它不一定会检查所有项目并返回。
3. 如果为cartList空，hasStockShortage将成为false，时间复杂度减少到O(1)（即常数）。