如何在一个非常大的2D阵列上循环,而不会对性能造成重大影响?

我喝了几杯酒,所以请耐心等待。

首先,我会做类似的事情 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名,等等等等,然后得到我们的结果。这通常是谷歌和其他搜索巨头进行搜索的方式。他们花费大量时间进行预计算,这样他们的搜索引擎就可以按数量级对候选人进行筛选,并发挥他们的魔力。

下面是一个示例片段。这需要大量的工作(请记住,我一直在喝酒),但它在>中运行了一百万条记录;。3ms。我通过生成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万个结果减少到100个左右。这个 search 函数具有一些后置过滤功能 intersection 这可能不是你想要的,但在这一点上,你做什么并不重要,因为结果太小了。