Выбор ответа Middle Коллекции и строки обновлено
Почему String.count в Swift работает за O(n)
Вопрос
Почему string.count у String может быть O(n)?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Нужно пройти строку и сгруппировать скаляры в графемные кластеры. Character в Swift это расширенный графемный кластер: флаг или «е» с ударением может состоять из нескольких скаляров и байтов.
Варианты ответа
- Нужно пройти строку и сгруппировать скаляры в графемные кластерыправильный ответ
- Строка хранится связным списком символов, и его приходится обходить
- Счётчик пересчитывается при каждом вызове ради потокобезопасности
- Это O(1): число символов хранится в заголовке строки
Разбор
Character в Swift это расширенный графемный кластер: флаг или «е» с ударением может состоять из нескольких скаляров и байтов. Число символов нельзя узнать, не пройдя строку, поэтому count линеен. В заголовке хранится длина в байтах UTF-8, а не число символов. Отсюда совет: не вызывать count в цикле и для проверки пустоты писать isEmpty.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Ещё по теме «Коллекции и строки»
- Сложность append у Array в Swift
- ContiguousArray и мост с NSArray
- Подсчёт частот в словаре
- Порядок ключей в Dictionary
- Сложность операций коллекций Swift
- String и NSString: длина и индексы
- Как взять n-й символ строки в Swift
- Сколько символов в строке с флагом