Kotlin: Обновление элемента неизменяемого списка

Новичок Котлин здесь. Как взять список и не изменять его, создать второй (неизменный) список с одним обновленным элементом по определенному индексу?

Я думаю о двух путях, которые кажутся похожими на то, что они могут понести удары производительности, мутировать базовый объект или и то, и другое.

data class Player(val name: String, val score: Int = 0)

val players: List<Player> = ...

// Do I do this?
val updatedPlayers1 = players.mapIndexed { i, player ->
    if (i == 2) player.copy(score = 100)
    else player
}

// Or this?
val updatedPlayer = players[2].copy(score = 100)
val mutable = players.toMutableList()
mutable.set(2, updatedPlayer)
val updatedPlayers2 = mutable.toList()

Если нет возможности выполнить этот способ, существует ли более подходящая структура данных в stdlib или другой библиотеке Kotlin? Котлин, похоже, не имеет векторов.

Ответы

Ответ 1

Для меня очевидно, что второй путь должен быть быстрее, но сколько?

Итак, я написал несколько тестов здесь

@State(Scope.Thread)
open class ModifyingImmutableList {

    @Param("10", "100", "10000", "1000000")
    var size: Int = 0

    lateinit var players: List<Player>

    @Setup
    fun setup() {
        players = generatePlayers(size)
    }

    @Benchmark fun iterative(): List<Player> {
        return players.mapIndexed { i, player ->
            if (i == 2) player.copy(score = 100)
            else player
        }
    }

    @Benchmark fun toMutable(): List<Player> {
        val updatedPlayer = players[2].copy(score = 100)
        val mutable = players.toMutableList()
        mutable.set(2, updatedPlayer)
        return mutable.toList()
    }

    @Benchmark fun toArrayList(): List<Player> {
        val updatedPlayer = players[2].copy(score = 100)
        return players.set(2, updatedPlayer)
    }
}

И получил следующие результаты:

$ java -jar target/benchmarks.jar -f 5 -wi 5 ModifyingImmutableList
Benchmark                            (size)   Mode  Cnt         Score        Error  Units
ModifyingImmutableList.iterative         10  thrpt  100   6885018.769 ± 189148.764  ops/s
ModifyingImmutableList.iterative        100  thrpt  100    877403.066 ±  20792.117  ops/s
ModifyingImmutableList.iterative      10000  thrpt  100     10456.272 ±    382.177  ops/s
ModifyingImmutableList.iterative    1000000  thrpt  100       108.167 ±      3.506  ops/s
ModifyingImmutableList.toArrayList       10  thrpt  100  33278431.127 ± 560577.516  ops/s
ModifyingImmutableList.toArrayList      100  thrpt  100  11009646.095 ± 180549.177  ops/s
ModifyingImmutableList.toArrayList    10000  thrpt  100    129167.033 ±   2532.945  ops/s
ModifyingImmutableList.toArrayList  1000000  thrpt  100       528.502 ±     16.451  ops/s
ModifyingImmutableList.toMutable         10  thrpt  100  19679357.039 ± 338925.701  ops/s
ModifyingImmutableList.toMutable        100  thrpt  100   5504388.388 ± 102757.671  ops/s
ModifyingImmutableList.toMutable      10000  thrpt  100     62809.131 ±   1070.111  ops/s
ModifyingImmutableList.toMutable    1000000  thrpt  100       258.013 ±      8.076  ops/s

Итак, этот тест показывает, что перебор коллекции примерно в 3-6 раз медленнее, чем копирование. Также я предоставляю свою реализацию: toArray, которая выглядит более производительной.

На 10 элементах метод toArray имеет пропускную способность 33278431.127 ± 560577.516 операций в секунду. Это медленно? Или это очень быстро? Я пишу "базовый" тест, который показывает стоимость копирования Players и мутирующего массива. Интересные результаты:

@Benchmark fun baseline(): List<Player> {
    val updatedPlayer = players[2].copy(score = 100)
    mutable[2] = updatedPlayer;
    return mutable
}

Где изменчиво - просто MutableList, то есть ArrayList.

$ java -jar target/benchmarks.jar -f 5 -wi 5 ModifyingImmutableList
Benchmark                            (size)   Mode  Cnt         Score         Error  Units
ModifyingImmutableList.baseline          10  thrpt  100  81026110.043 ± 1076989.958  ops/s
ModifyingImmutableList.baseline         100  thrpt  100  81299168.496 ±  910200.124  ops/s
ModifyingImmutableList.baseline       10000  thrpt  100  81854190.779 ± 1010264.620  ops/s
ModifyingImmutableList.baseline     1000000  thrpt  100  83906022.547 ±  615205.008  ops/s
ModifyingImmutableList.toArrayList       10  thrpt  100  33090236.757 ±  518459.863  ops/s
ModifyingImmutableList.toArrayList      100  thrpt  100  11074338.763 ±  138272.711  ops/s
ModifyingImmutableList.toArrayList    10000  thrpt  100    131486.634 ±    1188.045  ops/s
ModifyingImmutableList.toArrayList  1000000  thrpt  100       531.425 ±      18.513  ops/s

На 10 элементах мы имеем 2-кратную регрессию, а на 1 миллион около 150000x!

Похоже, что ArrayList не лучший выбор для неизменных структур данных. Но есть много других коллекций, одна из которых - pcollections. Давайте посмотрим, что они получили в нашем сценарии:

@Benchmark fun pcollections(): List<Player> {
    val updatedPlayer = players[2].copy(score = 100)
    return pvector.with(2, updatedPlayer)
}

Где находится pvector pvector:PVector<Player> = TreePVector.from(players).

$ java -jar target/benchmarks.jar -f 5 -wi 5 ModifyingImmutableList
Benchmark                             (size)   Mode  Cnt         Score         Error  Units
ModifyingImmutableList.baseline           10  thrpt  100  79462416.691 ± 1391446.159  ops/s
ModifyingImmutableList.baseline          100  thrpt  100  79991447.499 ± 1328008.619  ops/s
ModifyingImmutableList.baseline        10000  thrpt  100  80017095.482 ± 1385143.058  ops/s
ModifyingImmutableList.baseline      1000000  thrpt  100  81358696.411 ± 1308714.098  ops/s
ModifyingImmutableList.pcollections       10  thrpt  100  15665979.142 ±  371910.991  ops/s
ModifyingImmutableList.pcollections      100  thrpt  100   9419433.113 ±  161562.675  ops/s
ModifyingImmutableList.pcollections    10000  thrpt  100   4747628.815 ±   81192.752  ops/s
ModifyingImmutableList.pcollections  1000000  thrpt  100   3011819.457 ±   45548.403  ops/s

Хорошие результаты! В случае с 1 миллионом мы выполняем только в 27 раз медленнее, что довольно круто, но в небольших коллекциях pcollections немного медленнее, чем в реализации ArrayList.

Обновление: как упоминалось @mfulton26, в toMutable тесте toList нет необходимости, поэтому я удалил его и перезапустил тесты. Также я добавил бенчмарк по стоимости создания TreePVector из существующего массива:

$ java -jar target/benchmarks.jar  ModifyingImmutableList
Benchmark                                 (size)   Mode  Cnt         Score         Error  Units
ModifyingImmutableList.baseline               10  thrpt  200  77639718.988 ± 1384171.128  ops/s
ModifyingImmutableList.baseline              100  thrpt  200  75978576.147 ± 1528533.332  ops/s
ModifyingImmutableList.baseline            10000  thrpt  200  79041238.378 ± 1137107.301  ops/s
ModifyingImmutableList.baseline          1000000  thrpt  200  84739641.265 ±  557334.317  ops/s

ModifyingImmutableList.iterative              10  thrpt  200   7389762.016 ±   72981.918  ops/s
ModifyingImmutableList.iterative             100  thrpt  200    956362.269 ±   11642.808  ops/s
ModifyingImmutableList.iterative           10000  thrpt  200     10953.451 ±     121.175  ops/s
ModifyingImmutableList.iterative         1000000  thrpt  200       115.379 ±       1.301  ops/s

ModifyingImmutableList.pcollections           10  thrpt  200  15984856.119 ±  162075.427  ops/s
ModifyingImmutableList.pcollections          100  thrpt  200   9322011.769 ±  176301.745  ops/s
ModifyingImmutableList.pcollections        10000  thrpt  200   4854742.140 ±   69066.751  ops/s
ModifyingImmutableList.pcollections      1000000  thrpt  200   3064251.812 ±   35972.244  ops/s

ModifyingImmutableList.pcollectionsFrom       10  thrpt  200   1585762.689 ±   20972.881  ops/s
ModifyingImmutableList.pcollectionsFrom      100  thrpt  200     67107.504 ±     808.308  ops/s
ModifyingImmutableList.pcollectionsFrom    10000  thrpt  200       268.268 ±       2.901  ops/s
ModifyingImmutableList.pcollectionsFrom  1000000  thrpt  200         1.406 ±       0.015  ops/s

ModifyingImmutableList.toArrayList            10  thrpt  200  34567833.775 ±  423910.463  ops/s
ModifyingImmutableList.toArrayList           100  thrpt  200  11395084.257 ±   76689.517  ops/s
ModifyingImmutableList.toArrayList         10000  thrpt  200    134299.055 ±     602.848  ops/s
ModifyingImmutableList.toArrayList       1000000  thrpt  200       549.064 ±      15.317  ops/s

ModifyingImmutableList.toMutable              10  thrpt  200  32441627.735 ±  391890.514  ops/s
ModifyingImmutableList.toMutable             100  thrpt  200  11505955.564 ±   71394.457  ops/s
ModifyingImmutableList.toMutable           10000  thrpt  200    134819.741 ±     526.830  ops/s
ModifyingImmutableList.toMutable         1000000  thrpt  200       561.031 ±       8.117  ops/s

Ответ 2

Интерфейс Kotlin List предназначен для доступа "только для чтения" к спискам, которые не обязательно являются неизменяемыми. Неизменность не может быть обеспечена через интерфейсы. Kotlin stdlib текущая реализация для toList вызывает, в некоторых случаях, toMutableList и возвращает свой результат как "доступ только для чтения" List.

Если у вас есть List игроков и вы хотите получить еще одного List игроков с обновленным элементом, то одно простое решение - скопировать список в MutableList, обновить нужный элемент, и только затем сохраните ссылку на результирующий список, используя интерфейс "только для чтения" Kotlin List:

val updatedPlayers: List<Player> = players.toMutableList().apply {
    this[2] = updatedPlayer
}

Если это то, что вы собираетесь делать часто, вы можете подумать о создании функции расширения для инкапсуляции деталей реализации:

inline fun <T> List<T>.copy(mutatorBlock: MutableList<T>.() -> Unit): List<T> {
    return toMutableList().apply(mutatorBlock)
}

Затем вы можете более свободно копировать списки с обновлениями (аналогично копированию классов данных) без необходимости явно указывать тип результата:

val updatedPlayers = players.copy { this[2] = updatedPlayer }

Ответ 3

Edit: С вашим обновленным вопросом я бы сказал, что использование map -подобных операций - самый эффективный способ сделать это, поскольку он копирует список только один раз.

Если вы используете mutableListOf или обычные конструкторы типа ArrayList() для создания экземпляра, вы можете просто нарисовать List до MutableList:

val mp = players as MutableList<Player>
mp[2] = mp[2].copy(score = 100)

toList/toMutableList будет дублировать элементы списка, поэтому вы правы с воздействием на производительность.

Однако идея состоит в том, что если вам нужна изменчивость, вы объявляете свойство MutableList. Вы можете использовать такую ​​конструкцию - используя два свойства - если вам нужно открыть список для другого объекта:

private val _players = mutableListOf<Player>()
val players: List<Player> 
       get() = _players.toList()

Для переменной score она похожа - если вам нужно ее изменить, это ОК, чтобы объявить ее как var:

data class Player(val name: String, var score: Int = 0)

В этом случае вы также можете просто сохранить неизменяемый список и просто обновить значение:

players[2].score = 100

Более подробную информацию о коллекциях в документах можно найти https://kotlinlang.org/docs/reference/collections.html