Сравнение производительности равенства строк строки JavaScript

У меня есть вопрос javascript noob. Скажем, у нас есть две очень большие строки (~ миллион символов или более), которые равны - они имеют одинаковую длину и один и тот же контент. Пусть говорят, что у нас есть эти две функции, которые делают то же самое (сравнивают строки):

function equals1(a, b) {
    return a === b;
}

function equals2(a, b) {
    if (a.length !== b.length) {
           return false;
    }
    for (var i = 0; i < a.length; ++i) {
        if (a[i] !== b[i]) {
            return false;
         }
    }
    return true;
}

Почему первая функция (equals1()) почти в два раза быстрее, чем вторая? Как можно улучшить вторую, чтобы она выполнялась так же хорошо, как первая?

Ответ 1

Первое делает то же самое. Если строки имеют разные длины, они вернут false. Затем он проверяет, совпадают ли символы с одинаковыми индексами. Однако он реализован на уровне реализации JS, поэтому он работает так же быстро, как C, С++, Java или на любом другом языке, на котором написана реализация JavaScript.

Ответ 2

Первая функция быстрее, потому что ей не нужно проверять, если i < a.length миллион раз, и выполнить операцию увеличения в i миллион раз.

Ответ 3

Скорее всего, Javascript выполняет интернирование строк (Выполняют ли обычные реализации JavaScript использование интернирования строк?) в соответствии с тем, кто находится в комитете ECMAScript. Я думал, что тогда === будет O (1), но на основе теста производительности исходного плаката это O (n), поскольку удвоение строки удваивает время для равенства. Это действительно печально, что интернирование строк не используется они так и должны быть.

Обновление: JSPerf

Оригинальные заявки на плакаты должны быть скопированы для сложности O (N) Из http://jsperf.com/eqaulity-is-constant-time Кажется, что даже если у меня есть 16-кратная большая строка, время не меняется более 1-2%

Поэтому, пожалуйста, пересмотреть те вещи, которые я пробил и ваши вниз голоса

Другими словами:

когда вы делаете

var str1 = "stringwithmillionchars"; //stored in address 51242
var str2 = "stringwithmillionchars"; //stored in address 12313

"stringwithmillionchars" будет сохранен один раз, если скажем в адресе 201012 памяти и оба str1 и str2 будут "указывать в этом адресе 201012. Этот адрес можно определить с помощью какого-либо хэширования для сопоставления с определенными местоположениями в памяти.

Поэтому при выполнении

"stringwithmillionchars"==="stringwithmillionchars"

будет выглядеть как

getContentOfAddress(51242)===getContentOfAddress(12313)

или 201012 === 201012

который принимает O (1)/постоянное время

Цикл for в вашем примере (equals2()) имеет время O (N), где N - длина обеих строк. Это потому, что он должен выполнять N сравнений между каждой парой символов и N сравнениями между я и str.length.

Примечание: номера адресов выбраны случайным образом для иллюстрации.

Важно. На основе сопоставлений производительности с моим вопросом (Почему Javascript ===/== равенство строк иногда имеет постоянную временную сложность и несколько раз имеет линейный временная сложность) интернирование происходит только тогда, когда строки назначаются напрямую с кавычками, иначе сравнение будет принимать линейное время вместо константы, поскольку происходит сравнение char -to- char.