Run end encoding and constant random access

[remysucre]

According to the doc, run end encoding implements random access with binary search on the position array:

This allows relatively efficient random access from a logical index using binary search.

However wouldn’t this be O(log N) in the worst case and violate the constant-time random access guarantee?

[felipecrv]

This allows relatively efficient random access from a logical index using binary search.

This is said in comparison to run-length encoding which stores the lengths of each run instead of the index of the run-end (i.e. the cumulative sum of the run lengths).

However wouldn’t this be O(log N) in the worst case and violate the constant-time random access guarantee?

Yes, what is this guarantee mentioned so we can point to the exception?

Even though for i in range(n): get(i) is O(n log n), it's possible to scan sequentially without having to run any binary-search. Every time you increment the index, you can check if it still belongs to the current run or the immediate next one.

[remysucre]

Thanks, it’s at the top of the spec:

O(1) (constant-time) random access

[amoeba]

I filed a PR for this, see #46643.

[felipecrv]

Thank you @amoeba!