Hadn’t run across this “accidentally quadratic” blog before, but it’s pretty interesting reading. Lots of pretty subtle ways something can end up unintentionally quadratic.
Python 3 does an interesting thing with its unicode objects which means that codepoint lookup is always O(1). It’s similar to the mentioned “Ruby knows if it doesn’t have anything that requires more than 7 bits” thing but more general. Basically it always represents unicode objects as if they were a fixed width representation, but decides the representation based on the max codepoint: So if you only need one byte, it only uses one byte. If you need two, it uses two, etc.
The semantics of Python unicode strings are a fair bit different from Ruby ones though - they’re immutable and they don’t have any implication of an associated byte representation, they’re just an abstract sequence of code points and you have to encode them to get bytes.
Hadn’t run across this “accidentally quadratic” blog before, but it’s pretty interesting reading. Lots of pretty subtle ways something can end up unintentionally quadratic.
Python 3 does an interesting thing with its unicode objects which means that codepoint lookup is always O(1). It’s similar to the mentioned “Ruby knows if it doesn’t have anything that requires more than 7 bits” thing but more general. Basically it always represents unicode objects as if they were a fixed width representation, but decides the representation based on the max codepoint: So if you only need one byte, it only uses one byte. If you need two, it uses two, etc.
The semantics of Python unicode strings are a fair bit different from Ruby ones though - they’re immutable and they don’t have any implication of an associated byte representation, they’re just an abstract sequence of code points and you have to encode them to get bytes.