Алгоритм метода js indexOf () в JAVASCRIPT

Question

При решении проблемы https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ я обнаружил, что использование метода indexOf дает нам преимущество полиномиальной производительности. Но, как уже упоминалось здесь , если мы используем этот polyfill для определения индекса элемента, он генерирует ошибку ограничения времени. Меня интересует, какова точная реализация метода indexOf, для которого он может работать в постоянное время, которое я предполагаю близким или равным (0[1])?

Answer 1

indexOf не работает в постоянное время. Ожидается, что он работает намного быстрее, чем реализация полифилла в JavaScript. Это связано с тем, что функции, являющиеся частью языка JavaScript (EcmaScript), обычно написаны на языке более низкого уровня, например C или C ++.

Вот тест, который иллюстрирует, что indexOf делает не работает в постоянное время:

// create a very long string aaaa...ab...bc...cd (etc)
let alpha = "abcdefghijklmnopqrstuvwxyz";
let s = Array.from(alpha, c => c.repeat(10000000)).join("");
// find each of the letters in this long string
for (let c of alpha) {
    let start = performance.now();
    s.indexOf(c);
    let end = performance.now();
    console.log(end-start);
}

См. На каком языке написано JavaScript? для каких языков используются для реализации JavaScript, включая такие функции, как indexOf.

Answer 2

Ваша проблема - это просто проблема с минимальным диапазоном запросов, которая может быть решена с постоянной сложностью времени с использованием разреженных таблиц. Но с учетом того, что существует только 4 различных значения, существует более простой способ ее решения:

Предварительно вычислить количество раз, когда каждая буква появляется в каждом префиксе (первые n символов). Эта предварительная обработка будет выполняться за линейное время. Затем для вашего диапазона проверьте, существует ли, например, буква A следующим образом: если количество букв до начала равно количеству букв до конца - тогда в этом диапазоне нет буквы A. Сделайте то же самое для всех 4 букв и выберите минимум.