Эффективные способы поиска элемента в массиве Javascript

Question

Я использую массив с заголовками.Каждый индекс заголовков соответствует идентификатору в базе данных, которая содержит HTML для данного заголовка.

Допустим, у меня есть строка, содержащая один из заголовков.

title = "why-birds-fly";
titles[] // an array which contains all the titles

Чтобы использовать строку «title» для получения соответствующего идентификатора, я мог бы сделать:

for (i = 0; i < titles.length-1; i++) {
  if (titles[i] == title)
    return i+1;
}

Другой метод, который я мог бы использовать, — это создать ассоциативный массив вместе с массивом заголовков, что является полной противоположностью заголовков.То есть он использует строку в качестве индекса и возвращает число.

titles_id {blah:0,why-birds-fly:1,blah2:2}

Затем я мог бы получить доступ к идентификатору:

return titles_id[title]+1;

Что было бы наиболее эффективным с учетом процессора, памяти и т. д.?

Также, пожалуйста, дайте мне знать, если моя логика неверна.

Спасибо, Виллем

Answer 1

Подход линейного поиска имеет сложность O(n), и я думаю, что худшим случаем для подхода с ассоциативными массивами, вероятно, является O(log n), ( лучший возможно, O(1), если движок JS использует хэши и не получает коллизий).Это будет зависеть от того, как обычно реализуется движок JS. ассоциативные массивы/объекты, но вы можете быть уверены, что он превзойдет O(n).

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

Answer 2

Также важно учитывать количество пар «ключ-значение», которые вам нужно будет хранить.Если оно меньше ~50 (в зависимости от реализации), то выполнение линейного поиска будет столь же эффективным, как поиск по хеш-таблице, из-за затрат на вычисление хеш-значения и разрешение коллизий.Исключением является механизм JavaScript Google Chrome v8, который хранит своего рода кэшированную версию всех объектов, что позволяет ему выполнять прямой поиск свойства объекта, поэтому использование класса Object в качестве хеш-таблицы может быть быстрее, хотя я Я не уверен, что стоимость создания этой кэшированной версии перевесит выгоду от небольших списков.

Answer 3

Вы можете использовать функцию indexOf Array в своем первом методе.

Ниже приведена информация от разработчика Mozilla:https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference:Objects:Array:indexOf

indexOf — это расширение JavaScript стандарта ECMA-262;как таковой он может отсутствовать в других реализациях стандарта.Вы можете обойти это, вставив следующий код в начало ваших сценариев, позволяющий использовать indexOf в реализациях ECMA-262, которые не поддерживают его изначально.Этот алгоритм аналогичен тому, который используется в Firefox и SpiderMonkey.

if (!Array.prototype.indexOf)
{
  Array.prototype.indexOf = function(elt /*, from*/)
  {
    var len = this.length >>> 0;

    var from = Number(arguments[1]) || 0;
    from = (from < 0)
         ? Math.ceil(from)
         : Math.floor(from);
    if (from < 0)
      from += len;

    for (; from < len; from++)
    {
      if (from in this &&
          this[from] === elt)
        return from;
    }
    return -1;
   };
}

Answer 4

Массивы Javascript могут использовать для индекса такое значение, как заголовок «Why-birds-fly».

Пример:var title = "почему-птицы летают";

вар TitleArray[] = новый массив();

TitleArray[title] = идентификатор;

Тогда у вас есть прямой доступ к идентификатору по заголовку:

вернуть TitleArray[название];