Самый быстрый способ определить, находится ли значение в группе значений в Javascript

Question

У меня есть группа строк в Javascript, и мне нужно написать функцию, которая определяет, принадлежит ли к этой группе другая конкретная строка.

Какой самый быстрый способ достичь этого? Можно ли поместить группу значений в массив, а затем написать функцию для поиска в массиве?

Я думаю, что если я сохраню отсортированные значения и выполню бинарный поиск, он должен работать достаточно быстро. Или есть какой-то другой умный способ сделать это, который может работать быстрее?

Answer 1

Используйте хеш-таблицу и сделайте следующее:

// Initialise the set

mySet = {};

// Add to the set

mySet["some string value"] = true;

...

// Test if a value is in the set:

if (testValue in mySet) {
     alert(testValue + " is in the set");
} else {
     alert(testValue + " is not in the set");
}

Answer 2

Вы можете использовать объект так:

// prepare a mock-up object
setOfValues = {};
for (var i = 0; i < 100; i++)
  setOfValues["example value " + i] = true;

// check for existence
if (setOfValues["example value 99"]);   // true
if (setOfValues["example value 101"]);  // undefined, essentially: false

Это использует тот факт, что объекты реализованы в виде ассоциативных массивов. Как быстро это зависит от ваших данных и реализации движка JavaScript, но вы можете легко провести тестирование производительности, чтобы сравнить его с другими вариантами выполнения.

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

Answer 3

Комментарий к вышеупомянутым хеш-решениям. На самом деле {} создает объект (также упомянутый выше), который может привести к некоторым побочным эффектам. Одним из них является то, что ваш «хэш» уже предварительно заполнен объектными методами по умолчанию.

То есть "toString" in setOfValues будет true (по крайней мере, в Firefox). Вы можете добавить другой символ, например, "" к вашим строкам, чтобы обойти эту проблему или использовать объект Hash, предоставленный библиотекой «prototype».

Answer 4

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

Например:

> let set = new Set();
> set.add('red')

> set.has('red')
true
> set.delete('red')
true
> set.has('red')
false

См. Этот пост SO для получения дополнительных примеров и обсуждения: Способы создания набора в JavaScript?

Answer 5

Возможный способ, особенно эффективный, если набор является неизменным, но все еще может использоваться с набором переменных:

var haystack = "monday tuesday wednesday thursday friday saturday sunday";
var needle = "Friday";
if (haystack.indexOf(needle.toLowerCase()) >= 0) alert("Found!");

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

Более надежный вариант может включать границы, чтобы гарантировать, что ни "день свадьбы", ни "день" не могут совпадать положительно:

var haystack = "!monday!tuesday!wednesday!thursday!friday!saturday!sunday!";
var needle = "Friday";
if (haystack.indexOf('!' + needle.toLowerCase() + '!') >= 0) alert("Found!");

Может не понадобиться, если ввод введен точно (например, из базы данных и т. Д.).

Я использовал это в скрипте Greasemonkey, с преимуществом использования стога сена непосредственно из хранилища GM.

Answer 6

Вы можете использовать ES6 , включая .

var string = "The quick brown fox jumps over the lazy dog.",
  substring = "lazy dog";

console.log(string.includes(substring));

Answer 7

Я знаю, что это старый пост. Но чтобы определить, находится ли значение в наборе значений, мы можем манипулировать через массив indexOf(), который ищет и обнаруживает настоящее значение

var myString="this is my large string set";
var myStr=myString.split(' ');
console.log('myStr contains "my" = '+ (myStr.indexOf('my')>=0));
console.log('myStr contains "your" = '+ (myStr.indexOf('your')>=0));

console.log('integer example : [1, 2, 5, 3] contains 5 = '+ ([1, 2, 5, 3].indexOf(5)>=0));

Answer 8

Зависит от того, сколько существует значений.

Если есть несколько значений (менее 10-50), поиск в массиве может быть нормальным Хеш-таблица может быть излишней.

Если у вас много значений, лучше всего использовать хеш-таблицу. Это требует меньше работы, чем сортировка значений и выполнение бинарного поиска.

Answer 9

Использование хеш-таблицы может быть более быстрым вариантом.

Какой бы вариант вы ни выбрали, он определенно стоит проверить его производительность на фоне альтернатив, которые вы рассматриваете.