javascript - 如何在不对性能造成重大影响的情况下遍历非常大的二维数组？

Question

我正尝试在一个 ionic 应用程序中用 JavaScript 迭代一个非常大的二维数组，但这主要使我的应用程序陷入困境。

一点背景，我用 StencilJS 创建了自定义搜索组件，它在键入时提供建议。您为组件提供一个字符串数组(搜索建议)。每个单独的字符串逐字标记并拆分为数组和小写

例如，“红翅黑鸟”变为

['red','winged','blackbird']

因此，对字符串数组进行分词看起来像这样:

[['red','winged','blackbird'],['bald','eagle'], ...]

现在，我在一个大阵列中有 10,000 多个这样的小阵列。

然后，我将用户在每次键入时输入的搜索词标记化。

然后，我将每个标记化搜索词数组与较大数组中的每个标记化建议数组进行比较。

因此，我有 2 个嵌套的 for-of 循​​环。

此外，我使用 Levenshtein 距离将每个搜索词与每个建议数组的每个元素进行比较。

Answer 1

我喝了几杯所以请耐心等待我解决这个问题。

要启动 id，请执行类似于 reverse index 的操作(信息量不大)。它与您已经在做的非常接近，但多了一些额外的步骤。

首先检查所有结果并标记化、提取、删除停用词、去盖、合并等。看起来您已经完成了此操作，但我正在添加一个完成示例。

const tokenize = (string) => {
  const tokens = string
    .split(' ') // just split on words, but maybe rep
    .filter((v) => v.trim() !== '');
    
  return new Set(tokens);
};

接下来我们要做的是生成一个以单词为键的映射，并向我们返回出现该单词的文档索引列表。

const documents = ['12312 taco', 'taco mmm'];
const index = {
  '12312': [0],
  'taco': [0, 1],
  'mmm': [2]
};

我想您可以看到这将把我们带到哪里...我们可以标记我们的搜索词并找到每个标记所属的所有文档，施展一些排名魔法，进入前 5 名，等等等等，然后得到我们的结果。这通常是谷歌和其他搜索巨头进行搜索的方式。他们花费大量时间进行预计算，以便他们的搜索引擎可以按数量级筛选候选人并发挥他们的魔力。

下面是一个示例片段。这需要大量工作(请记住，我一直在喝酒)但它在 >.3 毫秒内运行一百万条记录。我通过生成 2 个字母的单词和短语来作弊，只是为了证明有时会发生冲突的查询。这真的无关紧要，因为查询时间平均与记录数成正比。请注意，此解决方案会返回包含所有搜索词的记录。它不关心上下文或其他任何内容。您将必须计算出排名(如果您此时关心的话)以获得您想要的结果。

const tokenize = (string) => {
  const tokens = string.split(' ')
    .filter((v) => v.trim() !== '');
    
  return new Set(tokens);
};

const ri = (documents) => {
  const index = new Map();
  
  for (let i = 0; i < documents.length; i++) {
    const document = documents[i];
    const tokens = tokenize(document);
    
    for (let token of tokens) {
      if (!index.has(token)) {
        index.set(token, new Set());
      }
      
      index.get(token).add(i);
    }
  }
  
  return index;
};

const intersect = (sets) => {
  const [head, ...rest] = sets;
  
  return rest.reduce((r, set) => {
    return new Set([...r].filter((n) => set.has(n)))
  }, new Set(head));
};

const search = (index, query) => {
  const tokens = tokenize(query);
  const canidates = [];
  
  for (let token of tokens) {
    const keys = index.get(token);
    
    if (keys != null) {
        canidates.push(keys);
    }
  }
  
  return intersect(canidates);
}

const word = () => Math.random().toString(36).substring(2, 4);
const terms = Array.from({ length: 255 }, () => word());

const documents = Array.from({ length: 1000000 }, () => {
  const sb = [];
  
  for (let i = 0; i < 2; i++) {
    sb.push(word());
  }
  
  return sb.join(' ');
});

const index = ri(documents);
const st = performance.now();
const query = 'bb iz';
const results = search(index, query);
const et = performance.now();

console.log(query, Array.from(results).slice(0, 10).map((i) => documents[i]));
console.log(et - st);

如果需要，您可以进行一些改进。比如……排名!这个例子的全部目的是展示我们如何将 100 万个结果减少到大约一百个候选者。 search 函数通过 intersection 进行了一些后期过滤，这可能不是您想要的，但在这一点上，您做什么并不重要，因为结果是这么小。