javascript - 快速搜索集合中的项目

Question

我有一个操作 Item 对象的脚本。每个项目都有一组独特的属性(a、b 和 c)，我们称它们为坐标。

我创建了包含items数组的Collection对象。现在我可以通过索引快速找到它们。

而且我想通过坐标找到它们。我实现了使用散列的 findByAbc 方法。如果指定了所有三个坐标，则效果很好。

但现在我想通过一两个坐标实现搜索，因此它应该返回项目数组。我创建了 findCustom 方法，该方法迭代所有项目并比较它们的坐标。但这个实现速度很慢。

可以快速搜索吗？

参见示例:http://jsfiddle.net/29zguzs5/

我想通过两个坐标来实现搜索，如下所示:

findByAb: (a, b)->
  aItems = @findByA(a)
  bItems = @findByB(b)
  items = findCommonItems(aItems, bItems)

但我认为比较两个数组也很慢。

那么，您对如何实现它有什么想法吗？

UPD。

我认为集合是一个多维(3d)数组(或散列)。如果您只指定两个索引，它应该返回一行项目。也许有一些现有的实现？

Answer 1

我认为使用 JavaScript 实现这一点的最简单方法是:为每个属性组合创建索引，如下所示:

// Somewhere in constructor
this.indexA = {};
this.indexB = {};
this.indexAB = {};
an so on...

然后用值填充索引。您可以在循环中或在 insert() 操作时执行此操作:

Collection.prototype.reindex = function(){
    for(var i=0;i<this.items.length;i++) {
        this.indexA[this.items[i].a] = this.items;
        this.indexB[this.items[i].b] = this.items;
        this.indexAB[this.items[i].a+'~'+this.items[i].b] = this.items;
    }
};

Collection.prototype.insert = function(val) {
    this.items.push(val);
    this.indexA[val.a] = val;
    this.indxB[val.a] = val;
    this.indexAB[val.a+'~'+val.b] = val;
}

Collection.prototype.getAB = function(a,b) {
    return this.indexAB[a+'~'+b];
}

这只是函数草案，它们并不通用(想法多于现成的解决方案)，但我们在 JavaScript SQL 数据库库中使用了这种方法，因为它速度很快。

要创建索引值，您可以使用以下内容:

function createKey(coordArray) {
    return coordArray.join('~');
}

这里的'~'只是不常见的字符，它可以替换为任何其他UNICODE字符，例如String.fromCharCode(0)

PS。抱歉，是 JS，不是 CoffeeScript。