Поиск подстроки в большом массиве строк javascript
 

Есть большой массив строк состоящий из 100000 элементов, каждый элемент представляет собой строку длиной около 20 символов. Как реализовать наиболее быстрый поиск подстроки в таком большом массиве? Необходимо найти все подходящие элементы. Сейчас использую простой цикл for и поочередно сравниваю каждый элемент. Подтормаживает. Может быть есть какое нибудь хитрое решение?

for (var i = 0; i < arr.length; i++) {
     var str = arr[i];
     if (reg.test(str)) {
         // добавляю в массив с результатами ...
     }
}

Momon,
первое что приходит в голову - убери присваивание

for (var i = 0; i < arr.length; i++) {  
     if (reg.test(arr[i])) {
         // добавляю в массив с результатами ...
     }
}

что еще -- хз, вроде for достаточно шустрый. Попробуй переписать на while. Тормозить может также и регулярка, выложи регулярку сюда.

1. Сортировка
2. Нечеткий поиск
3. Индексирование
4. Хеширование
+
Гугл

Задача мутно описана но думаю что в твоем случае хватит не четкого поиска

А сортировка тут причем?Это че такое?

Кстати, провел небольшой эксперимент, возможно, вариант решения твоей проблемы

str=fs.readFileSync("tmp", "ascii")
arr=str.split(" ")
console.log("length of string: "+str.length, "length of array: "+arr.length )

re=/\bfoo[^ ]+/g
results1=[]
results2=[]

console.time("cycle")
 for(var i=0; i<arr.length; i++) if(re.test(arr[i])) results1.push(arr[i])
console.timeEnd("cycle")


console.time("match")
 results2=str.match(re)
console.timeEnd("match")


//>>>> length of string: 7598519 length of array: 1396503
//>>>> cycle: 184ms
//>>>> match: 11ms

посмотрел щас про него, и напрашивается вопрос: зачем ты употребляешь слова, значение которых не знаешь ит не понимаешь? У нечеткого поиска совершенно другие задачи. Основное его назначение -- поиск похожих слов. Это не может положительно повлиять на производительность обычного поиска, естественно. Про сортировку -- тоже не совсем понятно. Насчет кэширования и индексации, я бы сказал, спасибо кэп, конечно, но никто не говорил, что поиск происходит многократно на одних и тех же данных. Ну, насчет гугла, пожалуй, спорить не буду.

В цикле с большим количеством элементов

var i = 0, k = arr.length; i < k; i++

так как при i < arr.length;, arr.length будет просчитываться каждый раз заново при каждой итерации.

laimas,
тогда уж, по вашей логике вот так

k = arr.length
var i = 0,  i < k; i++

за цикл выносим. Но вряд ли это может дать прирост существенный, оптимизатор компилятора сам это делает обычно.
Там все "просчитывание" заключается в проверке, не изменилось ли свойство length массива. Или ты думаешь, что каждый раз все элементы заново пересчитываются? ПоэтомуБез разницы. К началу исполнения цикла длина массива уже известна.

Ну да, это с чего она вдруг известна?

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

Я не думаю, это выражение i < arr.length обязывает получать количество элементов массива.

Выполните такое же на РНР, используя тики, сравните.

потому что при любой деструктивной операции над массивом, св-во length автоматически обновляется.
см вышея выполнил на V8 и сравнил время. Практически, идентично.

А что значит получить свойство length массива?

это значит, например, обратится к объекту массива (послать сообщение), запросив его длину: array.length. Эта длина, на момент обращения статична, мы просто получаем число по ссылке. В момент обращения длина не вычисляется, она уже вычислена, это статичное св-во

Да, не правильно мыслил, это же свойство корректируется автоматически.

1. бинарный поиск
2. воркеры
3. "порционный" поиск (например, обрабатывать не более 1000 элементов за цикл браузера)

nerv_,
По-моему бинарный поиск здесь не возможен, т.к. мне нужно находить элементы массива (строки) по частичному соответствию, т.е. находить строку не только в случае 100% соответствия, но и в случае совпадения 1 слова или даже начальной части слова в строке.

Если важно, чтобы не тормозило, то я вижу только три решения и они уже тут были озвучены:
- кеш
- WebWorkers
- "порционный" поиск с помощью таймеров setTimeout/setInterval

WebWorkers не ускорит никак скорость (нагрузку да снимет)
порционный поиск(Устройство Даффа) здесь также не поможет для увеличения скорости
for будет самым быстрым, возможно ускорить если выбрать определенную структуру данных пусть это будет не массив а маркированный текст к примеру(это мысль без практического подтверждения)

Poznakomlus,
вот этот пример:
http://javascript.ru/forum/misc/5521...tml#post367262
подтверждает Вашу мысль, даже без маркировок, а просто по регекпу. Маркировка, конечно, позволит упростить регулярку.

Всем спасибо за помощь. Прирост производительности более чем в два раза дала замена test на indexOf :)

чтобы не тратить время на точный поиск, лично я преобразую один раз массив в объект и использую for (var key in obj). При этом в obj[key] можно хранить любые потенциально необходимые характеристики, индексы массива, количество одинаковых элементов и прочее. Разница с переборкой массива уже при десятке элементов...

Интересуюсь подобными штуками. Momon, можно ли глянуть на результат?