ruby - Ruby 中 UTF-8 编码字符串中随机索引字符访问的时间复杂度是多少？

Question

Ruby 中 UTF-8 编码字符串中随机索引字符访问的时间复杂度是多少？

当我在命令行解释器中运行这段代码时:

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

它输出:

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

所以我想，当我尝试从字符串中获取第 ith 个字符时，我有 O(n) 操作，其中 n 是字符串的长度。这是正确的吗？我在官方文档中找不到关于此的一些信息。在我看来，这非常重要。

Answer 1

UTF-8 不支持字符的随机索引。字符可以编码为 1 到 4 个八位字节之间的任何内容。因此，要找到第 i 个字符，您必须读取字符串开头的所有八位字节，直到到达第 i 个字符。这意味着，要找到第 i 个字符，您必须读取 i 和 4*i 八位字节之间的任何位置。

请注意，当然，它并不止于此。比如我的名字可以有两种写法:J + ö + r + g，即在 UTF-8 中编码为五个八位字节的四个字符。或者，可以写成 J + o + 组合字符分音符 + r + g，这是编码为六个八位字节的五个字符。

因此，在不知道字符串是否规范化以及它使用哪种规范化形式(如果有的话)的情况下，您甚至不知道 r 是我名字的第三个还是第四个字符。

如果您索引字符串以获取第三个字符，您可能会得到组合字符分音符，它本身没有任何意义，因为它需要与前一个字符组合形成一个字形。但是，您也不能假设前一个字符“有用”，因为组合字符可以“堆叠”，因此前一个字符可能再次成为组合字符。