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?
CodePudding user response：
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)
}
CodePudding user response：
The second one looks ever so slightly better for performance, but they are both O(n), so it's not a big difference, and hardly worth worrying about. I would go for the second one because it's easier to read.
The first one iterates the list up to 2 times, but the second iteration breaks early once it finds the item. (The first iteration is to copy the list, but it is possibly optimized by the JVM to do a fast array copy under the hood.)
The second one iterates the list a single time, but it does have to do the ID comparison for each item in the list.
Side note: "immutable" is not really the right term for a List. They are called "read-only" Lists because the interface does not guarantee immutability. For example:
private val mutableList = mutableListOf<Int>()
val readOnlyList: List<Int> get() = mutableList
To an outside class, this List is read-only, but not immutable. Its contents might be getting changed internally in the class that owns the list. That would be kind of a fragile design, but it's possible. There are situations where you might want to use a MutableList for performance reasons and pass it to other functions that only expect a read-only List. As long as you don't mutate it while it is in use by that other class, it would be OK.
CodePudding user response：
Another thing you could try is, as apparently each item has an id field that you are using to identify the item, to create a map from it, perform all your replacements on that map, and convert it back into a list. This is only useful if you can batch all the replacements you need to do, though. It will probably also change the order of the items in the list.
fun List<Item>.getList(newItem: Item) =
associateBy(Item::id)
.also { map ->
map[newItem.id] = newItem
}
.values
And then there’s also the possibility to convert your list into a Sequence: this way it will be lazily evaluated; every replacement you add with .map will create a new Sequence that refers to the old one plus your new mapping, and none of it will be evaluated until you run an operation that actually has to read the whole thing, like toList().
CodePudding user response：
Another solution: if the list is truly immutable and not only read-only; or if its contents could change and you would like to see these changes in the resulting list, then you can also wrap the original list into another one. This is fairly easy to do in Kotlin:
fun main() {
val list = listOf(
Item(1, "1-orig"),
Item(2, "2-orig"),
Item(3, "3-orig"),
)
val list2 = list.getList(Item(2, "2-new"))
println(list2)
}
fun List<Item>.getList(newItem: Item): List<Item> {
val found = indexOfFirst { it.id == newItem.id }
if (found == -1) return this
return object : AbstractList<Item>() {
override val size = [email protected]
override fun get(index: Int) = if (index == found) newItem else this@getList[index]
}
}
data class Item(val id: Int, val name: String)
This is very good for the performance if you don't plan to repeatedly modify resulting lists with further changes. It is O(1) to replace an item and it almost doesn't use any additional memory. However, if you plan to invoke getList() repeatedly on a resulting list, each time creating a new one, that would create a chain of lists, slowing down access to the data and preventing garbage collector to clean up replaced items (if you don't use the original list anymore). You can partially optimize this by detecting you invoke getItem() on your specific implementation, but even better, you can use already existing libraries that does this.
This pattern is called a persistent data structure and it is provided by the library kotlinx.collections.immutable. You can use it like this:
fun main() {
val list = persistentListOf(
Item(1, "1-orig"),
Item(2, "2-orig"),
Item(3, "3-orig"),
)
val list2 = list.set(1, Item(2, "2-new"))
println(list2)
}
By the way, it seems strange to keep a list of items where we identify them by their ids. Did you consider using a map instead?