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

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

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

Если у вас есть List игроков и вы хотите эффективно получить еще один List игроков с обновленным элементом, то одно прямое решение – скопировать список в MutableList , обновить нужный элемент и затем сохранить только ссылку на результирующий список, используя Kotlin's «доступ только для чтения» Интерфейс 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 } 

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

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

 @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 элементах мы имеем 2x регрессию, и на 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 более медленное выполнение, что довольно круто, но на небольших коллекциях 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 

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


Если вы используете mutableListOf или обычные конструкторы, такие как ArrayList() чтобы создать экземпляр, вы можете просто перечислить List to 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