This repository was archived by the owner on Nov 26, 2024. It is now read-only.
Repository navigation
This repository was archived by the owner on Nov 26, 2024. It is now read-only.
Runtime of List.length #343
Description
Can the runtime of List.length be added to the Remarks section of its documentation?
The standard implementation for a linked list would have linear runtime, but maybe F#'s list caches the length in the "head node" so that a constant runtime is possible. Since F#'s list is immutable, this is a textbook example of a time-space tradeoff: either choice has advantages over the other.
I briefly looked at the F# code to see if I could determine for myself what the implementation (and thus runtime) is. If someone wants to "teach me how to fish" in addition to "giving me a fish", that too would be greatly appreciated.
Activity
TysonMN commentedon Oct 17, 2019
Based on these runtime tests, it appears to be a linear-time computation.
abelbraaksma commentedon Nov 13, 2019
That is correct, lists are implemented as singly linked lists and determining the length requires iteration over it until the last item, performance is O(n). Conversely, arrays have a fixed length and getting this length is O(1). While at it, sequences need to be evaluated in full, which can have side effects, but apart from that, getting their length is O(n).
I agree that the docs should have info on performance characteristics, I think there's a more general item open somewhere.