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

[Momon]

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

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

[theKingOfJava]

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

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

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

[MallSerg]

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

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

[theKingOfJava]

Сортировка

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

Нечеткий поиск

Это че такое?

[theKingOfJava]

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

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

[theKingOfJava]

Нечеткий поиск

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

[laimas]

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

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

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

[theKingOfJava]

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

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

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

просчитываться каждый раз

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

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

Без разницы. К началу исполнения цикла длина массива уже известна.

[laimas]

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

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

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

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

[theKingOfJava]

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

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

обязывает получать количество элементов массива.

см выше

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

я выполнил на V8 и сравнил время. Практически, идентично.