 # Improving the runtime of recursions using `List.subList`

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 + 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` 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` in `foo`) improves to constant time. In consequence, the runtime of `foo` would be linear.

2 Likes

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