Swift的String.count的BigO是什么? [英] What is the BigO of Swift's String.count?

问题描述

当swift使用String.count时是

O(n)，每次调用该函数时，我们都会遍历整个String以便对其进行计数

O(n) where each time we call it we iterate through the entire String in order to count it

或

O(1)，其中swift先前已存储了该数组的大小并可以对其进行访问.

O(1) where swift has previously stored the size of this array and simply accesses it.

推荐答案

绝对是O(n).从

结果是，如果不对字符串进行迭代来确定其扩展的字形簇边界，就无法计算字符串中的字符数.如果要使用特别长的字符串值，请注意，count属性必须遍历整个字符串的Unicode标量，才能确定该字符串的字符.

As a result, the number of characters in a string can't be calculated without iterating through the string to determine its extended grapheme cluster boundaries. If you are working with particularly long string values, be aware that the count property must iterate over the Unicode scalars in the entire string in order to determine the characters for that string.

这有一些含义，其中最大的含义是标准库中没有整数下标(即str[5]).在内部，String使用ASCII或UTF-16编码(从Swift 5开始，它使用仅适用于UTF-8 ).如果字符串仅使用ASCII字符，则count可以为O(1)，但是ASCII仅包含127个字符，因此应将其视为例外而不是规则.

This has a few implications, the biggest of which is integer subscripting (i.e. str[5]) is not available through the standard library. Internally, String uses ASCII or UTF-16 encoding (from Swift 5, it uses UTF-8 only). If the string only uses ASCII characters then count can be O(1) but ASCII only has 127 characters so consider this an exception rather than the rule.

NSString始终使用UTF-16，因此访问其length为O(1).另外请记住，NSString.length != String.count(尝试使用带有表情符号的字符串，您将看到).

NSString, on the other hand, always uses UTF-16 so accessing its length is O(1). And also keep in mind that NSString.length != String.count (try strings with emojis and you'll see).

关于第二个问题，它不为后续呼叫缓存count.因此，即使字符串未更改，对count的每次调用也都是O(n). Foundation 存储库中的代码也证实了这一点.

As for your second question, it does not cache count for subsequent calls. Every call to count is thus O(n), even if the string has not changed. The code in the Foundation repo also confirms that.

这篇关于Swift的String.count的BigO是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！