UTF8 String: простая идея сделать поиск index () O (1)

Question

Фон

Я использую класс UTF8-CPP.Подавляющее большинство моих строк используют набор символов ASCII (0-127).Проблема со строками на основе UTF8 заключается в том, что индексная функция (т. Е. Для извлечения символа определенной позиции) является медленной.

Идея

Простой метод заключается в использованиифлаг как свойство, которое в основном говорит, является ли строка чистым ASCII или примечанием (isAscii).Этот флаг будет обновляться всякий раз, когда изменяется строка.

Это решение кажется слишком простым, и могут быть вещи, которые я пропускаю.Но если это решение является жизнеспособным, разве оно не обеспечивает лучшее из обоих миров (т.е. Unicode при необходимости и производительности в подавляющем большинстве случаев), и не будет ли оно гарантировано O (1) для циклических циклов индекса?

ОБНОВЛЕНИЕ

Я собираюсь приложить диаграмму, чтобы уточнить, что я имею в виду.Я думаю, что многие люди неправильно понимают, что я имею в виду (или я неправильно понимаю основные понятия).Все хорошие ответы.

Answer 1

Я думаю, что здесь дело в том, что хотя ваше подавляющее большинство строк - это ASCII, в общем, разработчик библиотеки UTF-8 должен ожидать общие строки UTF-8.И там, проверка и установка этого флага - ненужные издержки.

В вашем случае, возможно, стоит потратить усилия на то, чтобы обернуть или изменить класс UTF8 соответствующим образом.Но прежде чем сделать это, спросите своего любимого профилировщика, стоит ли оно того.

Answer 2

Если вы хотите ускорить случай UTF8 ...

Сначала рассмотрите возможность последовательной индексации кодовых точек, чтобы избежать повторного подсчета их с самого начала строки.Реализуйте и используйте подпрограммы для индексации следующей и предыдущей кодовых точек.

Во-вторых, вы можете встроить массив индексов в кодовые точки строки UTF8 и использовать его в качестве первого шага при поиске, это даст вамприблизительное местоположение искомой кодовой точки.
Вы можете иметь его (массив) фиксированного размера, и в этом случае вы все равно получите время поиска ~ O (n) с O (1) стоимостью памяти, или оно будет иметьсодержат одинаково расположенные индексы (то есть индексы в каждой m-й кодовой точке, где m некоторая константа), и в этом случае вы получите время поиска ~ O (m + log (n)) со стоимостью памяти O (n).

Вы также можете встраивать индексы в данные кодовой точки, кодирующие их как зарезервированные / неиспользуемые / и т. Д. Кодовые точки, или использовать недопустимое кодирование (скажем, сначала байт является 11111110 двоичным, а затем, например, 6 10xxxxxx байтов, содержащихуказатель или что угодно).

Answer 3

«Это зависит» от ваших потребностей в безопасности потоков и обновлениях, а также от длины ваших строк и от того, сколько у вас есть. Другими словами, только профилирование вашей идеи в реальном приложении покажет вам, будет ли это лучше или хуже.