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

Question

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

当然，一种解决方案是循环并调用MutableList.removeFirst()n次，但这感觉效率很低，是O(n(。另一种方法是选择另一种数据类型，但如果我能避免的话，我宁愿不通过实现我自己的数据类型来扰乱我的项目

有没有一种更快的方法可以用MutableList做到这一点？如果没有，是否有其他内置数据类型可以在小于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

在引擎盖下，它创建了一个列表的新实例(AbstractClass的SubList类(，其中元素位于所选索引之间。

使用：

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

Answer 2

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

1. 将最后一个CCD_ 9字节存储在临时列表中
2. 清除原始列表实例
3. 将临时列表添加到原始列表

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

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