用于筛选无模式集合的最快数据结构

Fastest datastructure for filtering schema-less collections

本文关键字：数据结构 集合 筛选 模式 用于      更新时间：2023-09-26

假设我有一个集合

var data = [
  { fieldA: 5 },
  { fieldA: 142, fieldB: 'string' },
  { fieldA: 1324, fieldC: 'string' },
  { fieldB: 'string', fieldD: 111, fieldZ: 'somestring' },
  ...
];

假设字段在元素之间不统一，但我事先知道唯一字段的数量，并且集合不是动态的。

我想用_.findWhere之类的东西来过滤它。这很简单，但如果我想优先考虑速度而不是轻松呢？是否有一种更好的数据结构可以始终最大限度地减少将要检查的元素数量？也许是某种树？

是的，如果您的查询类型为"给我所有fieldX=valueY的记录"，那么会更快。然而，它确实有开销。

对于每个字段，构建一个反向索引，列出所有具有每个值的记录ID（=原始data中的行位置）：

var indexForEachField = {
    fieldA: { "5": [0], "142": [1], "1324": [2]},
    ...
}

当有人要求"字段X=值Y的记录"时，您会返回

indexForEachField["fieldX"]["valueY"]; // an array with all results

因此，查找时间是恒定的（并且只需要在表中进行2次查找），但您确实需要保持索引的最新状态。

这是搜索引擎用来查找带有特定术语的网页的策略的概括；在这种情况下，它被称为反向指数。

编辑：如果您想查找fieldX=valueX和fieldY=valueY的所有记录，该怎么办？

您将使用以下代码，它需要所有的输入数组待分拣：

var a = indexForEachField["fieldX"]["valueX"];
var b = indexForEachField["fieldY"]["valueY"];
var c = []; // result array: all elements in a AND in b
for (var i=0, j=0; i<a.length && j<b.length; /**/) {
    if (a[i] < b[j]) {
       i++;
    } else if (a[i] > b[j]) {
       j++;
    } else {
       c.push(a[i]);
       i++; j++;
    }
}

你可以看到，在最坏的情况下，总复杂度恰好是a.length + b.length；在最好的情况下，是一半。您可以使用非常类似的东西来实现OR。

相关文章：