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

Question

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

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

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

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

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} 

я мог бы получить доступ к ID по:

return titles_id[title]+1; 

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

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

Благодаря Willem

Answer 1

Линейный поиск подход имеет complexity О (п), и я думаю, что в худшем случае для ассоциативного подхода массива, вероятно, O (журнал N), (лучшего случай может быть, O (1), если двигатель JS использует хэши и не вызывает столкновений). Это будет зависеть от того, как движок JS обычно реализует associative arrays/objects, но вы можете быть уверены, что он будет бить O (n).

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

Answer 2

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

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

var TitleArray [] = new Array();

TitleArray [title] = id;

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

возвращение TitleArray [TITLE];

Answer 3

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

Answer 4

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

Ниже представлена ​​информация от разработчиков 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; 
    }; 
}