Javascript / jQuery более быстрая альтернатива $ .inArray, когда строки соответствуют шаблону - PullRequest
Новая
       1

Javascript / jQuery более быстрая альтернатива $ .inArray, когда строки соответствуют шаблону

2 голосов
/ 19 ноября 2011

У меня есть большой массив слов в Javascript (~ 100 000), и я хотел бы иметь возможность быстро возвращать подмножество их на основе текстового шаблона.

Например, яЯ хотел бы вернуть все слова, начинающиеся с шаблона, поэтому при наборе hap в результате получится ["happy", "happiness", "happening", etc, etc].

Если возможно, я бы хотел сделать это без итерации по всему массиву.

Что-то вроде этого работает недостаточно быстро: 

// data contains an array of beginnings of words e.g. 'hap'
$.each(data, function(key, possibleWord) {
 found = $.inArray(possibleWord, words);
 // do something if found
}

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

Ответы [ 6 ]

3 голосов
/ 19 ноября 2011

Если вы просто хотите искать префиксы, для этого есть структуры данных, такие как Trie и деревья троичного поиска

Быстрый Поиск Google ипоявляются некоторые многообещающие реализации Javascrit Trie и автозаполнения:

http://ejohn.org/blog/javascript-trie-performance-analysis/

Автозаполнение с использованием трех

http://odhyan.com/blog/2010/11/trie-implementation-in-javascript/

1 голос
/ 19 ноября 2011

Я абсолютно не знаю, если это будет быстрее ( jsperf test , вероятно, в порядке ...), но вы можете сделать это с одной гигантской строкой и RegExpпоиск вместо массивов: 

var giantStringOfWords = giantArrayOfWords.join(' ');
function searchForBeginning(beginning, str) {
    var pattern = new RegExp('\\b' + str + '\\w*'),
        matches = str.match(pattern);
    return matches;
}

var hapResults = searchForBeginning('hap', giantStringOfWords);
0 голосов
/ 19 ноября 2011

Действительно простая оптимизация при загрузке страницы, просмотрите массив больших слов и запишите, какие диапазоны индексов применимы к каждой начальной букве.Например, в моем примере ниже слова «a» переходят от 0 до 2, слова «b» переходят от 3 до 4 и т. Д. Затем, когда вы делаете сопоставление с образцом, смотрите только соответствующий диапазон.Хотя очевидно, что в некоторых буквах будет больше слов, чем в других, при заданном поиске нужно будет просмотреть в среднем только 100 000/26 слов.В массиве, когда совпадение найдено, я установил флаг, который указывает, что мы прошли все слова в алфавитном порядке перед шаблоном и теперь пробираемся через совпадающие слова.Таким образом, как только шаблон больше не совпадает, мы можем выйти из цикла.Если шаблон не совпадает вообще, мы все равно в конечном итоге просматриваем все слова для этой первой буквы.

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

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

0 голосов
/ 19 ноября 2011 
var data = ['foo', 'happy', 'happiness', 'foohap'];    
jQuery.each(data, function(i, item) {
      if(item.match(/^hap/))
        console.log(item) 
    });

Если у вас есть данные в массиве, вам придется пройтись по всему циклу.

0 голосов
/ 19 ноября 2011

Полагаю, что использование raw javascript может немного помочь, вы можете сделать: 

var arr = ["happy", "happiness", "nothere", "notHereEither", "happening"], subset = [];
for(var i = 0, len = arr.length; i < len; i ++) {
     if(arr[i].search("hap") !== -1) {
           subset.push(arr[i]);
     }
}
//subset === ["happy", "happiness","happening"]

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

0 голосов
/ 19 ноября 2011

Лучший подход - лучше структурировать данные. Сделайте объект с ключами типа "hap". Этот член содержит массив слов (или суффиксы слов, если вы хотите сэкономить место) или отдельную строку слов для поиска по регулярному выражению.

Это означает, что у вас будут более короткие объекты для итерации / поиска. Другим способом является сортировка массивов и использование шаблона двоичного поиска. Здесь хороший разговор о методах и оптимизации: http://ejohn.org/blog/revised-javascript-dictionary-search/

...