Estoy programando en Kotlin y tengo una MutableList de la que me gustaría eliminar los primeros n elementos de esa instancia de lista específica . Esto significa que funciones como MutableList.drop(n) están fuera de discusión.
Por supuesto, una solución sería hacer un bucle y llamar a MutableList.removeFirst() n veces, pero esto se siente ineficiente, siendo O( n ). Otra forma sería elegir otro tipo de datos, pero preferiría no saturar mi proyecto implementando mi propio tipo de datos para esto, si puedo evitarlo.
¿Hay una manera más rápida de hacer esto con MutableList? Si no, ¿hay otro tipo de datos incorporado que pueda lograr esto en menos de O( n )?
En mi opinión, la mejor manera de lograr esto es abstract fun subList(fromIndex: Int, toIndex: Int): List<E> .
https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/sub-list.html
Bajo el capó, crea una nueva instancia de lista (clase SubList para AbstractClass) con elementos entre los índices seleccionados.
Utilizando:
val yourList = listOf<YourType>(...) val yourNewList = yourList.subList(5, yourList.size) // return list from 6th elem to lastUn método que parece ser más rápido si n es suficientemente grande parece ser el siguiente:
listSize - n bytes para mantener en una lista temporal,Aquí hay un punto de referencia rápido para algunos valores de ejemplo que se ajustan a mi caso de uso:
val numRepetitions = 15_000 val listSize = 1_000 val maxRemove = listSize val rnd0 = Random(0) val rnd1 = Random(0) // 1. Store the last `listSize - n` bytes to keep in a temporary list, // 2. Clear original list // 3. Add temporary list to original list var accumulatedMsClearAddAll = 0L for (i in 0 until numRepetitions) { val l = Random.nextBytes(listSize).toMutableList() val numRemove = rnd0.nextInt(maxRemove) val numKeep = listSize - numRemove val startTime = System.currentTimeMillis() val expectedOutput = l.takeLast(numKeep) l.clear() l.addAll(expectedOutput) val endTime = System.currentTimeMillis() assert(l == expectedOutput) accumulatedMsClearAddAll += endTime - startTime } // Iteratively remove the first byte `n` times. var accumulatedMsIterative = 0L for (i in 0 until numRepetitions) { val numRemove = rnd1.nextInt(maxRemove) val l = Random.nextBytes(listSize).toMutableList() val expectedOutput = l.takeLast(listSize - numRemove) val startTime = System.currentTimeMillis() for (ii in 0 until numRemove) { l.removeFirst() } val endTime = System.currentTimeMillis() assert(l == expectedOutput) accumulatedMsIterative += endTime - startTime } println("clear+addAll removal: $accumulatedMsClearAddAll ms") println("Iterative removal: $accumulatedMsIterative ms")Producción:
Clear+addAll removal: 478 ms Iterative removal: 12683 ms