kotlin 在不可变列表中替换元素的最好方法是什么?

y0u0uwnf  于 2022-12-13  发布在  Kotlin
关注(0)|答案(4)|浏览(302)

更新不可变列表中特定项的最佳方法是什么?例如,我有Item的列表。我有几种方法来更新列表:
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
        }
    }

第二个选项看起来更简洁,我更喜欢它,但是,在第二个选项中,我们将遍历列表中的每个元素,这对我来说很糟糕,因为列表可以包含很多元素。
拜托,有没有更好的办法来满足我的要求?

ygya80vv

ygya80vv1#

您有几种选择-您已经在使用 “制作可变副本并更新它” 方法,以及 “通过Map每个项目并更改所需内容来制作副本” 方法。
另一种典型的方法是对半复制,复制你需要的部分,然后插入你想修改的部分。你可以这样做,例如,围绕你想修改的元素分割列表,然后从这些部分构建你的最终列表:

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

通过这种方式,您可以利用底层列表复制方法的效率,而map必须“转换”每个项,即使它最终通过原始项。
但是,与往常一样,最好进行基准测试,看看这些方法的实际执行情况如何!Here's a playground example-当然不是进行基准测试的最佳位置,但如果您运行几次,它可能会作为一个大致的指导方针:

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

一般来说,Map比切片合并多花60-100%的时间,而切片比直接的可变复制和更新多花2- 3倍的时间。
考虑到你在这里真正需要做的(获取列表的副本并更改(最多)一项内容)最后一种方法似乎是最合适的!其他方法的优点取决于您希望如何操作列表以产生最终结果,但由于您在这里几乎没有做任何事情,它们只会增加不必要的开销,当然这取决于您的用例-例如,切片方法比Map方法使用更多的中间列表,这可能是除了原始速度之外的一个问题。
如果第一个示例中的冗长内容让您感到困扰,您可以将其编写为:

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

pdkcd3nj2#

第二个看起来在性能上稍微好一点,但是它们都是O(n),所以差别不大,不值得担心。我会选择第二个,因为它更容易阅读。
第一个迭代最多迭代列表2次,但第二个迭代在找到项后就提前中断了(第一个迭代是复制列表,但JVM可能对其进行了优化,以便在幕后进行快速数组复制)。
第二个函数只迭代列表一次,但它必须对列表中的每个项进行ID比较。
旁注:“不可变”并不是List的正确术语。它们被称为“只读”列表,因为接口不保证不可变性。例如:

private val mutableList = mutableListOf<Int>()

val readOnlyList: List<Int> get() = mutableList

对于一个外部类,这个List是只读的,但不是不可变的。它的内容可能在拥有这个列表的类内部被改变。这是一种脆弱的设计,但这是可能的。在某些情况下,出于性能原因,您可能希望使用MutableList,并将其传递给其他只需要只读List的函数。只要您不使用“当它被其他类使用时,不要改变它,这样就可以了。

dkqlctbz

dkqlctbz3#

你可以尝试的另一件事是,每个项目都有一个id字段,你可以用它来标识项目,从它创建一个Map,在那个Map上执行所有的替换,然后将它转换回列表。不过,这只在你可以批量处理所有需要做的替换时有用。它可能还会改变列表中项目的顺序。

fun List<Item>.getList(newItem: Item) =
    associateBy(Item::id)
        .also { map ->
            map[newItem.id] = newItem
        }
        .values

此外,还可以将列表转换为Sequence:这样,它将被惰性地评估;用.map添加的每一个替换都将创建一个新的Sequence,它引用旧的Map和新的Map,并且在运行一个实际上必须读取整个内容的操作(如toList())之前,不会对任何一个Map进行求值。

kmpatx3s

kmpatx3s4#

另一种解决方案:如果该列表是真正不可变的并且不仅仅是只读的;或者它的内容可能会改变,而您希望在结果列表中看到这些改变,那么您也可以将原始列表 Package 到另一个列表中。这在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 = this@getList.size
        override fun get(index: Int) = if (index == found) newItem else this@getList[index]
    }
}

data class Item(val id: Int, val name: String)

如果你不打算反复修改结果列表,这对性能是非常好的。用O(1)来替换一个条目,几乎不使用任何额外的内存。但是,如果你打算在结果列表上反复调用getList(),每次创建一个新列表时,都会创建一个列表链。降低对数据的访问速度并阻止垃圾收集器清理替换的项(如果您不再使用原始列表)您可以通过检测您在特定实现上调用了getItem()来部分地优化它,但更好的是,您可以使用已经存在的库来执行此操作。
这个模式叫做persistent data structure,由kotlinx.collections.immutable库提供,可以像这样使用它:

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

顺便说一句,用物品的ID来识别物品似乎很奇怪。你有没有考虑过用Map来代替?

相关问题