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 или другой библиотеке? У Kotlin, похоже, нет векторов.


kotlin purely-functional
person Eric    schedule 21.10.2016    source источник
comment
Вы нашли ответ?   -  person Ruslan    schedule 14.11.2016

Ответы (4)


arrow_upward
15
arrow_downward

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

Поэтому я написал несколько тестов здесь

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

Где 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 миллионе примерно в 150000х!

Так что 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 миллионом у нас есть только 27x медленнее выполнение, что довольно круто, но на небольших коллекциях 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
person Ruslan    schedule 23.10.2016
comment
Хорошие тесты, но похоже, что в setup проделана некоторая работа для некоторых тестов, которые должны быть выполнены в самом тесте, чтобы сравнивать яблоки с яблоками. github.com/KotlinBy/kotlin-benchmarks/commit/ - person mfulton26; 24.10.2016
comment
Нет, потому что мы измеряем стоимость не создания коллекций, а их модификации. В этом случае требуется правильная коллекция. В зависимости от того, что делает @Eric, он может создать PVector вместо List, поэтому упаковка не требуется. То же самое для изменяемого случая. Стоимость TreePVector.from может быть еще одним эталоном. - person Ruslan; 24.10.2016
comment
Я понимаю. Спасибо @IRus. Насколько я понял из вопроса Эрика, у него есть список, и он хочет создать его копию с обновленным элементом, поэтому я подумал, что стоимость создания копии должна быть включена в каждый тест. - person mfulton26; 24.10.2016
comment
Обратите внимание, что в тесте toMutable вызов toList не нужен. MutableList уже является List. Копирование списка не требуется, чтобы вернуть List. - person mfulton26; 24.10.2016
comment
Итак, похоже, ваш ответ: для больших коллекций использование PVector для начала (не конвертировать из списка) - единственный способ получить достойную неизменную производительность. Для небольших коллекций используйте PVector, toMutable или toArrayList. Это твой совет? - person Eric; 17.04.2018
comment
@Eric Конечно, для больших неизменяемых структур данных используйте постоянные структуры данных, например pcollections. Для небольших структур данных вы также можете использовать pcollections или такие подходы, как toMutable или toArrayList. - person Ruslan; 18.04.2018
comment
Не могли бы вы добавить что-то вроде резюме в начале или в конце вашего ответа, говоря об этом? Ваш ответ довольно хорош и обстоятелен, поэтому я думаю, что такое резюме было бы полезно. - person Eric; 19.04.2018

arrow_upward
7
arrow_downward

Интерфейс Kotlin List предназначен для "доступа только для чтения" к спискам, которые не обязательно являются неизменяемыми списками. Неизменяемость не может быть реализована через интерфейсы. текущая реализация stdlib Kotlin для вызовов 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 }
person mfulton26    schedule 24.10.2016

arrow_upward
1
arrow_downward

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

person yuranos    schedule 27.12.2019

arrow_upward
0
arrow_downward

Редактировать. Что касается вашего обновленного вопроса, я бы сказал, что использование 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

person Lovis    schedule 21.10.2016
comment
В Котлине список всегда изменчив. Это просто неправда. Вы можете получить исключения, если вызовете мутирующие методы, потому что базовый список может быть чем угодно, например. Пустой список . - person Kirill Rakhman; 22.10.2016
comment
@KirillRakhman, вы правы, на самом деле я имел в виду только списки, созданные с помощью mutableListOf или стандартных конструкторов - обновил ответ - person Lovis; 22.10.2016
comment
и приятно знать: listOf (в настоящее время) вызывает Arrays.asList java, который на самом деле создает этот странный ArrayList, который на самом деле не является ArrayList, поскольку он использует массив в качестве резервного массива по соображениям производительности. - person Lovis; 22.10.2016
comment
Извините, но под обновлением элемента в неизменяемом списке я имел в виду создание второго неизменяемого списка с одним обновленным элементом без изменения оригинала. Я уточнил вопрос. - person Eric; 22.10.2016