Kotlin. What is the best way to replace element in immutable list?

Question

What is the best way to update specific item in immutable list. For example I have list of Item. And I have several ways to update list:

1.

  fun List<Item>.getList(newItem: Item): List<Item> {
        val items = this.toMutableList()
        val index = items.indexOf(newItem)
        if (index  != -1) {
            items[index ] = newItem
        }
        return items 
    }

fun List<Item>.getList(newItem: Card): List<Item> {
        return this.map { item ->
            if (item.id == newItem.id) newItem else item
        }
    }

The second option looks more concise and I like it more. However, in the second option, we will go through each element in the list, which is bad for me, because the list can contain many elements.

Please, is there a better way to fulfill my requirement?

Answer 1

You have a few options - you're already doing the "make a mutable copy and update it" approach, and the "make a copy by mapping each item and changing what you need" one.

Another typical approach is to kinda go half-and-half, copying the parts you need, and inserting the bits you want to change. You could do this by, for example, slicing the list around the element you want to change, and building your final list from those parts:

fun List<Item>.update(item: Item): List<Item> {
    val itemIndex = indexOf(item)
    return if (itemIndex == -1) this.toList()
    else slice(0 until itemIndex) + item + slice(itemIndex+1 until size)
}

This way you get to take advantage of any efficiency from the underlying list copy methods, versus map which has to "transform" each item even if it ends up passing through the original.

---

But as always, it's best to benchmark to see how well these approaches actually perform! Here's a playground example - definitely not the best place to do benchmarking, but it can be instructive as a general ballpark if you run things a few times:

Mapping all elements: 2500 ms
Slicing: 1491 ms
Copy and update index: 611 ms

Broadly speaking, mapping takes 60-100% more time than the slice-and-combine approach. And slicing takes 2-3x longer than just a straight mutable copy and update.

Considering what you actually need to do here (get a copy of the list and change (up to) one thing) the last approach seems like the best fit! The others have their benefits depending on how you want to manipulate the list to produce the end result, but since you're barely doing anything here, they just add unnecessary overhead. And of course it depends on your use-case - the slicing approach for example uses more intermediate lists than the mapping approach, and that might be a concern in addition to raw speed.

---

If the verbosity in your first example bothers you, you could always write it like:

fun List<Item>.getList(newItem: Item): List<Item> =
    this.toMutableList().apply {
        val index = indexOf(newItem)
        if (index != -1) set(index, newItem)
    }