17.04.2015, 23:15
|
|
Аспирант
|
|
Регистрация: 02.12.2014
Сообщений: 72
|
|
Поиск подстроки в большом массиве строк javascript
Есть большой массив строк состоящий из 100000 элементов, каждый элемент представляет собой строку длиной около 20 символов. Как реализовать наиболее быстрый поиск подстроки в таком большом массиве? Необходимо найти все подходящие элементы. Сейчас использую простой цикл for и поочередно сравниваю каждый элемент. Подтормаживает. Может быть есть какое нибудь хитрое решение?
for (var i = 0; i < arr.length; i++) {
var str = arr[i];
if (reg.test(str)) {
// добавляю в массив с результатами ...
}
}
Последний раз редактировалось Momon, 17.04.2015 в 23:20.
|
|
17.04.2015, 23:30
|
Кандидат Javascript-наук
|
|
Регистрация: 31.03.2015
Сообщений: 113
|
|
Momon,
первое что приходит в голову - убери присваивание
for (var i = 0; i < arr.length; i++) {
if (reg.test(arr[i])) {
// добавляю в массив с результатами ...
}
}
что еще -- хз, вроде for достаточно шустрый. Попробуй переписать на while. Тормозить может также и регулярка, выложи регулярку сюда.
|
|
17.04.2015, 23:38
|
|
Профессор
|
|
Регистрация: 07.03.2011
Сообщений: 1,138
|
|
1. Сортировка
2. Нечеткий поиск
3. Индексирование
4. Хеширование
+
Гугл
Задача мутно описана но думаю что в твоем случае хватит не четкого поиска
|
|
17.04.2015, 23:43
|
Кандидат Javascript-наук
|
|
Регистрация: 31.03.2015
Сообщений: 113
|
|
Сообщение от MallSerg
|
Сортировка
|
А сортировка тут причем?
Сообщение от MallSerg
|
Нечеткий поиск
|
Это че такое?
|
|
18.04.2015, 00:55
|
Кандидат Javascript-наук
|
|
Регистрация: 31.03.2015
Сообщений: 113
|
|
Кстати, провел небольшой эксперимент, возможно, вариант решения твоей проблемы
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
|
|
18.04.2015, 01:15
|
Кандидат Javascript-наук
|
|
Регистрация: 31.03.2015
Сообщений: 113
|
|
Сообщение от MallSerg
|
Нечеткий поиск
|
посмотрел щас про него, и напрашивается вопрос: зачем ты употребляешь слова, значение которых не знаешь ит не понимаешь? У нечеткого поиска совершенно другие задачи. Основное его назначение -- поиск похожих слов. Это не может положительно повлиять на производительность обычного поиска, естественно. Про сортировку -- тоже не совсем понятно. Насчет кэширования и индексации, я бы сказал, спасибо кэп, конечно, но никто не говорил, что поиск происходит многократно на одних и тех же данных. Ну, насчет гугла, пожалуй, спорить не буду.
|
|
18.04.2015, 05:18
|
Профессор
|
|
Регистрация: 14.01.2015
Сообщений: 12,989
|
|
В цикле с большим количеством элементов
var i = 0, k = arr.length; i < k; i++
так как при i < arr.length;, arr.length будет просчитываться каждый раз заново при каждой итерации.
|
|
18.04.2015, 05:31
|
Кандидат Javascript-наук
|
|
Регистрация: 31.03.2015
Сообщений: 113
|
|
laimas,
тогда уж, по вашей логике вот так
k = arr.length
var i = 0, i < k; i++
за цикл выносим. Но вряд ли это может дать прирост существенный, оптимизатор компилятора сам это делает обычно.
Сообщение от laimas
|
просчитываться каждый раз
|
Там все "просчитывание" заключается в проверке, не изменилось ли свойство length массива. Или ты думаешь, что каждый раз все элементы заново пересчитываются? Поэтому
Сообщение от laimas
|
с большим количеством элементов
|
Без разницы. К началу исполнения цикла длина массива уже известна.
|
|
18.04.2015, 05:57
|
Профессор
|
|
Регистрация: 14.01.2015
Сообщений: 12,989
|
|
Ну да, это с чего она вдруг известна?
Или ты думаешь, что каждый раз все элементы заново пересчитываются?
Я не думаю, это выражение i < arr.length обязывает получать количество элементов массива.
Выполните такое же на РНР, используя тики, сравните.
|
|
18.04.2015, 06:15
|
Кандидат Javascript-наук
|
|
Регистрация: 31.03.2015
Сообщений: 113
|
|
Сообщение от laimas
|
Ну да, это с чего она вдруг известна?
|
потому что при любой деструктивной операции над массивом, св-во length автоматически обновляется.
Сообщение от laimas
|
обязывает получать количество элементов массива.
|
см выше
Сообщение от laimas
|
Выполните такое же на РНР, используя тики, сравните.
|
я выполнил на V8 и сравнил время. Практически, идентично.
|
|
|
|