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

问：

在 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
б

所以我想，当我尝试从字符串中获取第 i 个字符时，我有 O（n）运算，其中 n 是字符串的长度。这是对的吗？我在官方文档中找不到有关此内容的一些信息。在我看来，这非常重要。

Ruby 字符串 UTF-8 时间复杂度

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

请注意，当然，它并不止于此。例如，我的名字可以用两种方式书写： + + + ，这是四个字符，在 UTF-8 中编码为五个八位字节。或者，它可以写成 + + 组合字符 diaeresis + + ，即编码为六个八位字节的五个字符。JörgJorg

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

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

“在其他语言中，它具有 O（1）时间复杂度”——这是不可能的。UTF-8 不支持随机访问。这是 UTF-8 的局限性，而不是语言的局限性。事实上，这是每个可变宽度传输编码的限制。没有一种语言能比 O（n）更好地提供 UTF-8 中的随机字符访问，除非它们具有非常复杂的字符串类型，并且它们保留了单独的字符索引列表。（但是构建此列表也是 O（n）时间，并且该列表具有 O（n）空间。

1赞 justew 12/17/2020

有可能。因为 UTF-8 编码的字符串文本被转换为 UTF-16 以在内部存储。随机访问在大多数情况下都可以正常工作，代理项对除外。代理对的情况没有专门处理。在一般情况下，访问是 O（1）。Ruby 是我所知道的唯一一种 UTF-8 不会转换为 UTF-16 的语言。这是非常糟糕的解决方案，因为 O（n）字符访问并不明显。

0赞 justew 12/17/2020

我知道 UTF-8 编码是如何工作的。我自己编写了 UTF-8 转换为 UTF-16 的算法。也许是因为我英语不好。但问题不在于编码，而在于 Ruby。为什么 Ruby 允许随机访问字符，但没有说明操作很慢？

上一个：在电子邮件正文中发送加重字符，如何解决编码问题

下一个：使用批处理脚本 curl 获取 UTF-8 JSON 文件而不是 UTF-16 LE BOM

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

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

评论

评论