Enhancing the performance of a for each loop that has an inner for each loop

user_70942 0
Viewed 260
AS 4.1.1
Kotlin 1.4.10

Writing a for loop with an inner forloop to check stock items quantities. Checking if the item in the cart's quantity is greater than the current stock item's quantity.

Using a inner for loop seems to be a very naive approach even though it works.

Just wondering if there is a better way to do this:

For the curentSkuQuantity I have a data class like this:

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

After RxJava return success with the current stock levels I check that the sku's are the same as the cart item. And then compare their quantities to see there is enough.

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()
                    }
                }
kotlin android
3 Answers

As you said, the performance of nested loops could be better. The best way to match items of two lists is to convert one of them to a map, like what Tenfour04 mentioned in his answer. In this way, the time complexity of the operation is reduced from O(n*m) to O(n+m) (i.e linear), where n and m are the order of lists sizes.

(O(n) for creating a map from cartList items and O(m) for iterating over the currentSkuQuantity list)

To achieve this, there are two beneficial collection operations:

  • associateBy: to create a map from a list
  • any: to check a condition over items of a list

Both of the above functions are of O(n) complexity and help us to achieve O(n+m), in a simpler manner.

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()
}

Note that the above snippet has advantages in three aspects:

  1. reduction of overall time complexity from O(n*m) to O(n+m).
  2. any is efficient in terms of iterating over the list. So, it does not necessarily check all the items and returns if at least one element matches the condition.
  3. if cartList gets null, hasStockShortage will become false and the time complexity reduces to O(1) (i.e. constant).
user_16319670

For performance, you could break out of the loop once there’s a positive, although this doesn’t improve big O complexity. When you use forEach instead of a traditional for loop, you have to use labels to break out of it. But since you’re just resolving a Boolean, you can use the any function to immediately break out once there’s a positive.

val hasStockShortage = (cartList != null) && 
    currentSkuQuantity.any { currentStockItem ->
        cartItem.any { cartItem -> 
            (currentStockItem.sku == cartItem.sku) && cartItem.qty > currentStockItem.quantity 
        }
    }

But if you’re frequently looking items up by SKU, it would be a good idea to change the relevant list to a map of the items by their SKUs. Then you won’t need a nested loop. This would change it from O(n^2) to O(n).

user_5067960

Here's what I do when attempting to-do advanced loops - for (i = 1; i <= 10; i++)

user_104607050
Related