Improving the runtime of recursions using `List.subList`

Libraries
1

With the current implementation of AbstractList.SubList, taking sublists of sublists recursively results in a long chain of SubList instances, where each instance is linked to the previous (sub)list it was taken from. For example, consider the following recursive extension function summing up the elements of the list:

fun List<Int>.foo(): Int = if (isEmpty()) {
    0
} else {
    this[0] + subList(1, size).foo()
}

(for demonstration purposes; I am aware that this concrete example of primitive recursion could also be solved by iteration and that there even already exists fun Iterable<Int>.sum())

At depth k of the recursion, accessing element this[0] of the sublist must traverse through all k instances of SubList until it reaches the original list. Hence, the runtime of foo is asympotically quadradic in the size of the list.

I propose to override subList in AbstractList.SubList:

public abstract class AbstractList<out E> protected constructor() : AbstractCollection<E>(), List<E> {
    ...
    private class SubList<out E>(private val list: AbstractList<E>, private val fromIndex: Int, toIndex: Int) : AbstractList<E>(), RandomAccess {
        ...
        override fun subList(fromIndex: Int, toIndex: Int): List<E> = SubList(list, this.fromIndex + fromIndex, this.fromIndex + toIndex)
    }
}

As a result, each new instance of SubList is only one link away from the original list, hence accessing an element (such as this[0] in foo) improves to constant time. In consequence, the runtime of foo would be linear.

2 Likes
2

I think that’s a good idea. Also, I think it would bring another fine side-effect: we would be able to add a circuit-breaker on equality test :

private class SubList<out E>(private val list: AbstractList<E>, private val fromIndex: Int, toIndex: Int) : AbstractList<E>(), RandomAccess {
        ...
        override fun subList(fromIndex: Int, toIndex: Int): List<E> = SubList(list, this.fromIndex + fromIndex, this.fromIndex + toIndex)

        override fun equals(other: Any?): Boolean {
            if (this === other) return true
            // Circuit breaker here: if both are sublists of the same slice, no need to check elements.
            if (other is SubList) {
                if (list === other.list && fromIndex == other.fromIndex && _size == other._size) return true
            }
            return super<AbstractList>.equals(other)
        }
    }
2 Likes