了解crossfilter.js有点笨拙的黑客攻击

Question

我在crossfilter.js 描述中找到了它,并试图理解这条线的含义

Crossfilter使用已排序的索引(以及一些有点麻烦的黑客攻击)来实现这一点,从而大大提高了实时直方图和top-K列表的性能.

我认为,排序索引是指在数据库中使用索引.避免进行全表扫描.每个维度都有一个完成过滤的索引.这导致增量过滤(逐个过滤每个索引),最后在最终生成过滤数据时,触发事件.

但是查看代码我无法理解黑客是什么,它用于什么以及如何使用.任何人都可以在这里解释苦涩的目的吗？

Answer 1

一开始就有这个宣言:

m = 0, // a bit mask representing which dimensions are in use

"位掩码"是一种简单有效的方法来跟踪真/假选项列表.假设您创建了待售汽车列表,并且您希望为列出的每辆车设置四个额外参数:4x4,ABS,ESP,climatronic.您可以像这样定义一个汽车对象:

MyCar = { brand : "Mercedes", 
          extras : {
              "4x4" : false,
              "ABS" : true,
              "ESP" : false,
              "climatronic" : true
          }
        }

这些额外的东西很容易设置和检索:if( MyCar.extras['4x4'] ){ /* display a ? */ }.它简单,易读,但在某些情况下可能需要太多资源来处理(想想:在大型集合上嵌套循环).

所以我们可以创建一个数组,其中每个索引对应一个特征,对吧？

MyCar = {  brand : "Mercedes",
           // 1: 4x4, 2: ABS, 3: ESP, 4: climatronic
           extras : [ false, true, false, true ]
        }

现在检查给定的汽车是否需要使用4x4 if( MyCar.extras[0] ){ /* display a ? */ }.它的可读性较差(您需要查阅文档以了解哪个功能在哪个索引下),但可能更快,需要更少的内存.

位掩码的概念类似,但使用数字而不是数组.extras : [ false, true, false, true ]可以缩短为extras : [ 0, 1, 0, 1 ]并且0101是数字的二进制表示5.因此,带有描述其功能的位掩码的Car对象可能如下所示:

MyCar = {  brand : "Mercedes",
           extras : 5
        }

这看起来完全不直观,但应该非常快速和轻量级.你怎么检查汽车是否有4x4？好吧,4x4表示为1000(二进制表示8),所以:

if( !!(MyCar.extras & 8) ){ /* display a ? */ }

所以,是的,现在我们只是通过这个代码的外观谈论hacks.它非常简单,但如果您之前没有使用过按位运算符,那么看起来很神秘.进一步解释:我们的汽车的extras属性设置为5,二进制是0101,我们想检查最左边的位是否设置为1.按位AND运算返回一个1's只有两个操作数都有的数字1.

    0101  // 5
AND 1000  // 8
  = 0000 

现在让我们检查ABS,它是左边的第2位(0100,即ie 4).

var hasABS = !!( MyCar.extras & 4 ); // true

因为

    0101  // 5
AND 0100  // 4
  = 0100 

如何将ESP设置为true？简单:

MyCar.extras |= 3;  // now extras == 7

发生了什么事？二进制OR返回一个数字,1's其中任何一个操作数都有一个1位.

5 | 3= 0101 | 0010= 0111= 7;

现在将ABS设置为false,即可使用

MyCar.extras ^= 4;

我将把二进制的工作留给XOR读者作为练习,但我希望你能得到使用位掩码和现在"有点蠢蠢欲动"的要点.