What is time complexity of random indexing characters access in UTF-8 encoded string in Ruby?

user_14132808 0
Viewed 168

What is time complexity of random indexing characters access in UTF-8 encoded string in Ruby?

When i run this code in command line interpreter:

s = "абв"
puts s.encoding.name
print s.bytes
puts
puts s.length
puts s[1]

it outputs:

UTF-8
[208, 176, 208, 177, 208, 178]
3
б

so i guess, when i try to get ith character from string, i have O(n) operations, where n is length of the string. Is it correct? I couldn't find some information about this in official documentation. In my opinion it's very important.

utf-8 time-complexity ruby string
1 Answers

UTF-8 does not support random indexing of characters. A character can be encoded as anything from one to four octets. Therefore, to find the ith character, you have to read all octets from the beginning of the string until you arrive at the ith character. That means, to find the ith character you have to read anywhere between i and 4*i octets.

Note that, of course, it doesn't stop here. For example, my name can be written in two ways: J + ö + r + g, which is four characters that are encoded as five octets in UTF-8. Or, it can be written as J + o + combining character diaeresis + r + g, which is five characters encoded as six octets.

So, without knowing whether the string is normalized or not and which normalization form it is using, if any, you don't even know whether r is the third or fourth character of my name.

If you index into the string to get the third character, you might get the combining character diaeresis which doesn't even make sense on its own, because it needs to be combined with a previous character to form a glyph. However, you also cannot assume that the previous character is "useful" because combining characters can be "stacked", so the previous character could again be a combining character.

user_29880
Related