Какова сложность времени выполнения функции countElements при подсчете символов String?Сложность времени выполнения countElements, если T.Index - RandomAccessIndexType?
В документации сказано:
O (1), если T.Index является RandomAccessIndexType; O (N) в противном случае.
Что такое RandomAccessIndexType? Есть String a RandomAccessIndexType?
В соответствии с документацией:
индекс, который может быть компенсировано произвольным числом позиций, и может измерять расстояние до любого достижимого значения в O (1)
Swift строки (к сожалению) не реализуют его. Вместо этого они используют BidirectionalIndexType, что в основном делает строку двунаправленным связанным списком, что означает, что для достижения символа в позиции n с позиции m он перемещается по всем элементам между ними. В результате функция countElements для строк имеет сложность O (n)
Чтобы добавить дополнительную информацию, String не является RandomAccessIndexType, потому что String поддерживает расширенные кластеры grapheme, что означает, что строка должна быть итерирована, чтобы найти «элемент», который представляет собой целый кластер графем, а не только одну графему (например, сочетание символов/акцентов и т. д.). –
Также, поскольку String реализована в символах UTF-16 в плоскости 1 и выше, требуется два кодовых блока UTF-16. Большинство Emoji находятся в плоскости 1. Это действительно ничем не отличается от 'NSString'. Свойство 'length' NSString было переименовано в' utf16Count' при доступе к нему в строке Swift. Свойство '' NSString' length' возвращает количество кодовых единиц UTF-16 ('unichar'), а не количество символов. – zaph