Эффективные способы поиска элемента в массиве 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;

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

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

Спасибо Willem

Answer 1

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

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

Answer 2

Вы можете использовать функцию 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 3

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

Answer 4

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

Exmaple: var title = "Why-birds-fly";

var TitleArray [] = new Array ();

TitleArray [title] = id;

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

return TitleArray [title];