Каков самый быстрый способ сравнить строки в JavaScript?

Question

У меня две строки, и мне нужно знать, равны ли они.

Я ранее делал это: str1 === str2, но мне интересно, есть ли более быстрый способ сравнить две строки.

Строки довольно короткие, длиной 15-25 символов. Моя проблема в том, что я повторяюсь через множество строк, и это занимает довольно много времени.

У меня есть много сравнений в структуре, как это:

If(str === str1) 
{ 
    do something 
} 
else if(str === str2) 
{ 
    do something 
} 
else if(str === str3) 
{ 
    do something 
} 

Строки не имеют какой-либо общей структуры или группировки.

Answer 1

Сравнение строк с a === b - это самый быстрый способ сравнить родников.

Однако, если бы вы могли создавать объекты String, такие как new String("test"), используйте их и используйте их в сравнениях, что было бы еще быстрее, потому что движку JS нужно было бы всего лишь выполнить сравнение указателя, небольшое количество) быстрее, чем сравнение строк.

См http://jsperf.com/string-vs-object-comparisons

Answer 2

Если ваш «делать нечто» разделяет подобную форму с разными значениями, вы можете поместить значения в карту и использовать строку в качестве ключа. Ради пример, в представьте, что вы должны обрабатывать много чисел с различными единицами длины, и вы хотите, чтобы преобразовать их все в метры:

var conversionToMeters = { 
    "inch": 0.0254, 
    "inches": 0.0254, 
    "foot": 0.3048, 
    "feet": 0.3048, 
    "cubit": 0.4572, 
    "cubits": 0.4572, 
    "yard": 0.9144, 
    "yards": 0.9144, 
    "kilometer": 1000, 
    "kilometers": 1000, 
    "mile": 1609.344, 
    "miles": 1609.344, 
    "lightyear": 9.46e15, 
    "lightyears": 9.46e15, 
    "parsec": 3.09e16, 
    "parsecs": 3.09e16, 
} 

(аббревиатуры (например, «км») и международные варианты написания (например, «км») опущены для краткости.) Вы можете заранее подготовить эту карту, чтобы избежать накладных расходов на создание. Теперь, с учетом переменной length, такие как length = "80 miles", вы можете сделать:

var magnitude = length.replace(/[\D]/g, ""); 
var unit = length.replace(/[\d\s]/g, ""); 
var lengthInMeters = magnitude * conversionToMeters[unit]; 
alert(lengthInMeters + " meters"); // Ta-da! 

Если ваш «делать нечто» не общий код вы можете использовать карту, но это будет карта функций (или в основном , класс JavaScript):

var actions = { 
    "eat": function() { 
     if (spareFood > 0) { 
      spareFood--; 
      energy += 10; 
      health++; 
      alert("Yum!"); 
     } 
    }, 
    "walk": function() { 
     if (energy > 0) energy--; 
     // ... 
    }, 
    "attack": function() { 
     if (energy > 0) { 
      if (Math.random() < 0.25) { 
       health--; 
       alert("Ouch!"); 
      } 
      energy--; 
     } 
    }, 
    // ... 
}; 

Это немного глупый пример, но я надеюсь, что он объяснит основную идею. Эти действия могут в равной степени представлять собой теги XML или имена инструкций CPU на виртуальной машине или имена продуктов, которые имеют особые требования к доставке, или что-то еще. После того, как вы получили вашу action переменную, выполняя это так же просто, как:

actions[action](); 

карта не единственный способ сделать такого рода вещи. Ваш исходный пример if/else можно легко оптимизировать, вставив ifs внутри дополнительных ifs, которые являются , предназначенные для быстрого устранения большинства строк-кандидатов.

Критерии, на которые вы введете ответ, будут зависеть от точных строк, с которыми вы работаете.Это может быть длина строки, или первая буква, или пару самых буквенные:

if (str.length === 3) { 
    // test all length 3 strings here 
    if (str === strA) doSomething(); 
    else if (str == strB) doSomething(); 
} else if (str.length === 4) { 
    // test all length 4 strings here 
    if (str === strC) doSomething(); 
    else if (str === strD) doSomething(); 
} 

Или:

var first = str[0]; // first character 
if (first >= "0" && first <= "9") { 
    // test all strings that start with digits here 
if (first >= "a" && first <= "l") { 
    // test all strings that start with letters 
    // in the first half of the alphabet here 
} else if (first >= "m" && first <= "z") { 
    // test all strings that start with letters 
    // in the latter half of the alphabet here 
} 

Вы можете вложить эти виды испытаний внутри друг друга в независимо от степени, подходящей для просеивания через определенные строки, с которыми вы работаете. Это своего рода разворачивается binary search, хотя критерии, на которые вы введете ответ, не должны разделить строки-кандидаты ровно на две группы.

Кроме того, когда вы используете, если/ElseIf как это, часто стоит организовать строки в порядке убывания частоты. I.e., проверьте те, которые происходят чаще всего, во-первых. Если есть только несколько строк, которые составляют большинство данных, вытащите их вверх и даже поставьте их вне любых предварительных тестов, основанных на длине или первой букве.

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

P.S. Я не знаю JavaScript достаточно хорошо, чтобы точно знать, как эти методы будут выполняться, но я сделал аналогичные вещи в Java. В Java подход к карте непобедим, когда «делать что-то» требует разных значений, но может использовать один и тот же код. В другой программе мне нужно было switch на целочисленное значение, выполняющее около 400 разнородных действий (это было ужасно). У клиентской виртуальной машины HotSpot есть отвратительная неэффективная реализация инструкции switch, которая представляет собой просто много elseifs, и она была слишком медленной. Массив функций (которые технически были объектами с переопределенными виртуальными методами) был быстрее, но служебные данные вызова функции были слишком велики по сравнению с простотой каждого действия. В этом случае я нашел, что смешанный бинарный четвертичный поиск эффективен. Это означает: внешние тесты были, если/elses разделили входные значения равномерно на две группы. Они были вложены до тех пор, пока во внутренних группах не осталось всего четыре возможных значения. Затем я использовал if/elseif/elseif/else, чтобы отличить оставшиеся четыре значения. Поскольку это было так долго, я написал код, чтобы написать его для меня, но он по-прежнему стоит усилий для этого конкретного приложения.

P.P.S. Есть подход, который я пропустил выше, но я включу его для полноты: если ваши строки редко нуждаются в изменении, вы можете использовать perfect hash function. Существуют служебные программы, которые проектируют эти функции для вас: просто поставьте им список всех ваших строк. Идеальная хеш-функция будет вычислять целочисленный хэш-код из строки и гарантировать, что две строки из вашего набора не имеют одинакового хэш-кода. Затем вы можете использовать целочисленный хэш-код для поиска действия в массиве. Это полезно для таких вещей, как синтаксический анализ ключевых слов языков программирования. Это может быть быстрее на языке, который ближе к металлу, но в JavaScript я подозреваю, что это не будет стоить того. Я упоминаю это на всякий случай.

Answer 3

Самый быстрый V8 способ будет использовать переключатель заявление так:

var str = '' + prompt('Enter cat or enter in dog'); 
 
switch(''+str){ // make it clear you are switching on a string 
 
    case 'cat': 
 
    console.log('you selected cat!'); 
 
    break; 
 
    case 'dog': 
 
    console.log('you selected dog!'); 
 
    break; 
 
    default: 
 
    console.log('you selected something else!'); 
 
}

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

Однако, если вы выполняете сравнения if-else, оптимизатор JIST может или не сможет оптимизировать эти сравнения во что-то эффективное.

Причина, по которой оптимизатор JIST может выполнять собственные оптимизации в операторе switch, может быть быстрее, потому что, когда он просто сравнивает длину, он сможет сортировать длины строк, которые он сравнивает. Это значительно упростит сравнение числовой длины (см. Proccessing Sorted VS Unsorted Array).