Fastest way to remove first n elements from MutableList

Question

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

Answer 1

One method which seems to be faster if n is sufficiently large seems to be the following:

1. Store the last listSize - n bytes to keep in a temporary list,
2. Clear original list instance
3. Add temporary list to original 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