Самая быстрая строка содержит проверку в массиве для огромных данных в JS - PullRequest
Новая
       9

Самая быстрая строка содержит проверку в массиве для огромных данных в JS

0 голосов
/ 27 марта 2020

Мне нужно проверить строку 2.000, если строка не существует в массиве с 650.000 элементов строки. Метод findIndex с помощью regex находит элементы, но он слишком медленный для ответа. Мне нужен самый быстрый способ сделать это. Я думаю, что если я смогу использовать regex в методе indexOf, я смогу достичь своего, потому что, как я знаю, метод indexOf - самый быстрый способ искать строку в массиве. 

//for example
let array1=["exa","val","har","esd","elf"]
let array2=["example","defvalue","harder","klein","rapper","doesnt"]

for (let index = 0; index < array1.length; index++) {
      if (array2.findIndex(value =>
         new RegExp(array1[index]).test(value)) == -1) {
        diffArray.push(muavinArray[index])
      }
    }
 //diffArray should be ["esd","elf"]

Это рабочий код, но слишком медленный

Ответы [ 2 ]

0 голосов
/ 27 марта 2020

Я понятия не имею, будет ли это намного быстрее, чуть быстрее, примерно таким же, чуть медленнее или намного медленнее, чем ваш первоначальный подход. Но есть основания полагать, что это может ускорить процесс. По сути, это реализация barebones tr ie. 

const simpleTrie = (words) => {
  const root = {}
  const addCharToNode = (node, char) => node [char] || (node[char] = {})
  const addChars = (node, [c = undefined, ...cs]) => 
    c == undefined ? node : addChars (addCharToNode (node, c), cs)
  const addSuffixes = (node, chars, [c = undefined, ...cs] = chars) =>
    c == undefined ? node : addChars(node, chars) && addSuffixes (node, cs)
  const findChars = (node, [c = undefined, ...cs]) =>
    c == undefined ? true : c in node ? findChars (node [c], cs) : false
  words .forEach (word => addSuffixes (root, word .split ('')))
  return (word) => findChars (root, word .split (''))
}

const findWord = simpleTrie (["example", "defvalue", "harder", "klein", "rapper", "doesnt"]);

const result = ["exa", "val", "har", "esd", "elf"] .filter (word => ! findWord (word))
 
console .log (result)

Это неправильный tr ie, так как он находит любые подстроки добавленных слов. Это как предназначено для проблемы, хотя. Это также не позволяет добавлять или удалять слова из дерева; сложение было бы довольно просто. Удаление может быть сложнее. Но опять же, это не нужно для этой проблемы.

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

0 голосов
/ 27 марта 2020

Фильтруйте array1 и итерируйте array2 с Array.some(), чтобы проверить, включена ли текущая строка в любую строку array2. Если это так, отфильтруйте его. 

const array1=["exa","val","har","esd","elf"]
const array2=["example","defvalue","harder","klein","rapper","doesnt"]

const result = array1.filter(s1 => 
  !array2.some(s2 => s2.includes(s1))
)

console.log(result)
...