字符串类内部-缓存字符偏移到字节关系（使用UTF-8时）
在编写一个自定义字符串类时，如果内部使用的是 UTF-8 格式（这样可以节省内存），而不是从头开始使用 UTF-16，那么在一定程度上缓存字节偏移和字符偏移之间的关系，是否能提高在随机访问时的性能呢？
Perl 是否有做这种字符偏移和字节偏移关系的缓存？Python 的字符串内部是怎么工作的呢？
那 Objective-C 和 Java 呢？它们内部使用的是 UTF-8 吗？
编辑
我找到了一些关于 Perl 5 使用 UTF-8 的资料：
"$flag = utf8::is_utf8(STRING)
(自 Perl 5.8.1 起) 测试 STRING 是否内部使用 UTF-8。功能上与 Encode::is_utf8() 相同。"
在这个页面上：
http://perldoc.perl.org/utf8.html
编辑
我想到的应用中，字符串包含 1-2K 的 XML 段落在 XMPP 流中。大约 1% 的消息预计会有多达 50%（按字符计）是 Unicode 值大于 127 的（这就是 XML）。在服务器上，消息会经过规则检查，并根据一小部分字段（按字符量）进行条件路由。这些服务器是运行在农场中的 Wintel 机器。在客户端，数据来自并输入到 UI 工具包中。
编辑
但这个应用不可避免地会发展，并且也想要进行一些随机访问。当这种情况发生时，性能损失能否最小化？我也对是否存在更通用的类设计感兴趣，比如管理字符偏移和字节偏移关系的 b 树，用于处理大型 UTF-8 字符串（或者其他在一般情况下被发现高效的算法）。
3 个回答
我觉得答案是：一般来说，尝试这样做其实没什么价值。不过在你特定的情况下，可能会有用。
如果你大部分的字符都是普通的ASCII字符，而且你很少用到UTF序列，那么构建一种稀疏数据结构来存储偏移量可能是值得的。
但在一般情况下，每个字符可能都是非ASCII的，而且你可能需要存储很多很多的偏移量。最通用的做法是创建一个字节字符串，它的长度正好和你的Unicode字符字符串一样，每个字节的值就是下一个字符的偏移量。但这样每个字符就要占用一个完整的字节，所以每个Unicode字符实际上只节省了一个字节；这样做可能不太划算。而且这意味着在你的字符串中查找字符的操作变成了O(n)，因为你需要遍历这些偏移量并累加才能找到实际的索引。
如果你真的想尝试稀疏数据结构，我建议使用一个值对数组，第一个值是Unicode字符串中字符的索引，第二个值是这个字符在字节序列中实际出现的索引。然后在每个UTF8转义序列后，你可以把这两个值加起来，以找到字符串中的下一个字符。最后，当你给出一个Unicode字符的索引时，你的代码可以对这个数组进行二分查找，以找到稀疏数组中小于请求索引的最大索引，然后用这个索引找到表示所需字符起始位置的实际字节。
如果你需要节省内存，可以考虑使用数据压缩库。先把Unicode字符串作为完整的Unicode字符串读入，然后进行压缩；接着在索引字符串时，先解压缩这个字符串。这确实能节省内存，而且编写正确的代码让它工作起来也比较简单和快速；不过可能会增加过多的CPU开销，让人觉得不太划算。
Java中的字符串内部使用的是UTF-16格式：
一个字符串在UTF-16格式中表示，其中一些特殊字符是通过成对的方式来表示的（想了解更多，可以查看Character类中的Unicode字符表示部分）。在字符串中，索引值是指字符代码单元，所以一个特殊字符会占用字符串中的两个位置。
Perl区分了Unicode字符串和非Unicode字符串。Unicode字符串在内部是用UTF-8格式来实现的。非Unicode字符串并不一定是7位的ASCII字符，它可以是当前地区设置中用一个字节表示的任何字符。