I am programming in Kotlin and have a MutableList from which I would like to remove the first n
elements from that specific list instance. This means that functions like MutableList.drop(n)
are out of the question.
One solution would of course be to loop and call MutableList.removeFirst()
n
times, but this feels inefficient, being O(n
). Another way would be to choose another data type, but I would prefer not to clutter my project by implementing my own data type for this, if I can avoid it.
Is there a faster way to do this with a MutableList? If not, is there another built-in data type that can achieve this in less than O(n
)?
One method which seems to be faster if n
is sufficiently large seems to be the following:
listSize - n
bytes to keep in a temporary list,Here is a quick benchmark for some example values that happen to fit my use case:
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")
Output:
Clear+addAll removal: 478 ms
Iterative removal: 12683 ms