android - 提高 for each 循环的性能，每个循环都有一个内部 for each 循环

Question

AS 4.1.1
Kotlin 1.4.10

编写一个带有内部 for 循环的 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

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

(O(n) 从 cartList 项目创建 map ，O(m) 迭代 currentSkuQuantity列表)

要实现这一点，有两个有益的收集操作:

• associateBy:从列表创建 map
• 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()
}

请注意，上面的代码 fragment 在三个方面具有优势:

1. 将总体时间复杂度从 O(n*m) 降低到 O(n+m)。
2. any 在遍历列表方面是高效的。因此，它不一定会检查所有项目并在至少有一个元素符合条件时返回。
3. 如果 cartList 为 null，hasStockShortage 将变为 false 并且时间复杂度降低为 O(1) (即常量)。