Comments 6
Корректное решение -это не использовать c = charAt(s, i) и charLength(s), a сделать i = nextChar(i), который прибавляет к индексу 1 или 2. И не надо никаких отдельных случаев и всегда линия будет вместо квардрата.
Нагородили какие-то кеши ответов. При чем только с двумя слотами, потому что код работает с двумя строками. Так почему-бы тогда в вызывающем коде и не запомнить результат isPlain для каждой строки в локальной переменной?
Слишком переусложненное и накрученное решение тривиальной проблемы.
На js для посимвольного обхода лучше вообще не изобретать что-то, как в статье, а использовать строковый итератор, он из коробки умеет в эмодзи.
Вообще вопрос проверки ассимптотики в тестах довольно важен и мало освещён. Хотя соглашусь, что пример в статье довольно неудачен.
На эту тему есть интересные тесты в rust-analyzer: раз, два. Они собирают статистику времени исполнения из 5-10 разных размеров для входа. На этой статистике строят регрессии. И если регрессия не выглядит линейной — тест считается упавшим (чуть сложнее, но суть такая).
Edit: хабр съел первый абзац =/
Решение "быстренько проверить вхождение суррогатной пары и затем дефолтиться к константному или линейному забегу"...
Начнём с того, что если подсунуть гигантский текст, в котором в самом конце будет суррогатная пара, - то этот код всё равно задефолтится к линейному забегу. Ну, да, isPlain при аккуратном (очень!!! очень аккуратном!!!) использовании будет кешироваться. Но она же нужна не просто так, а для выбора способа произвольного доступа.
Так что квадратный маляр Шлемюэль никуда не делся, только спрятался поглубже.
Код, который проходил тесты на маленьких датасетах, затем на большущих датасетах, а потом в продакшен залетел одинокий дятел, подклеил флажочек к полному собранию сочинений, и бабах.
Почему бы для длинных текстов не использовать не голую строку, а специальный класс, который эффективно решает задачи прямого доступа (хотя бы за логарифмическое время, с помощью интервальных деревьев и ленивости). И кешировать-ленивить исключительно саму эту обёрнутую строку, а не делать глобальный кеш из двух элементов!!!
Собственно, задача быстрого доступа к фрагментам текста (разбивка на страницы, абзацы и слова) - это типичная задача любых текстовых редакторов. А тут всего лишь добавился ещё один уровень иерархии, композитные буковки.
Понятно, что для программиста это шок. Работал с "просто строкой", и вдруг понадобилось сделать полноценный вьювер. (Эмм, а зачем надо было работать со строкой с прямым доступом к ней? Похоже, изначально вьювер нужен был).
Но все эти велосипеды были изобретены ещё в далёких 1970-х, наверное.
Тест проходил за миллисекунды. На настоящем файле тот же код думал минуту