从 MutableList 中删除前 n 个元素的最快方法

Question

我正在使用 Kotlin 编程，并且有一个 MutableList，我想从该特定列表实例中删除前 n 个元素 。这意味着像 MutableList.drop(n) 这样的函数是不可能的。

一个解决方案当然是循环并调用 MutableList.removeFirst() n 次，但这感觉效率低下，为 O(n)。另一种方法是选择另一种数据类型，但如果可以避免的话，我不希望为此实现我自己的数据类型而使我的项目混乱。

使用 MutableList 有更快的方法吗？如果没有，是否有另一种 built-in 数据类型可以在不到 O(n) 的时间内实现这一点？

Answer 1

在我看来，最好的方法是 abstract fun subList(fromIndex: Int, toIndex: Int): List<E>.

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/sub-list.html

在底层，它创建了一个新的列表实例（SubList class for AbstractClass），其中包含所选索引之间的元素。

使用：

val yourList = listOf<YourType>(...)
val yourNewList = yourList.subList(5, yourList.size) 
// return list from 6th elem to last

Answer 2

如果 n 足够大，一种方法似乎更快：

存储最后 listSize - n 个字节以保存在临时列表中，
清除原始列表实例
将临时列表添加到原始列表

这是一些恰好适合我的用例的示例值的快速基准：

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

输出：

Clear+addAll removal: 478 ms
Iterative removal:    12683 ms

从 MutableList 中删除前 n 个元素的最快方法

Fastest way to remove first n elements from MutableList

list

kotlin

time-complexity

big-o

mutablelist