javascript - 了解 crossfilter.js 位旋转黑客

Question

我在 crossfilter.js description 上找到了它我试图理解这条线的含义

Crossfilter uses sorted indexes (and a few bit-twiddling hacks) to make this possible, dramatically increasing the perfor­mance of live histograms and top-K lists.

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

但是看着code我无法理解黑客是什么，它的用途和方式。任何人都可以在这里解释比特旋转的目的吗？

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 ✓ */ }
所以，是的，现在我们仅通过这段代码的外观来讨论黑客。如果您以前没有使用过按位运算符，这真的很简单，但看起来很神秘。进一步解释:我们的车有extras属性设置为 5 , 二进制是 0101我们要检查最左边的位是否设置为1 .按位 AND操作返回一个具有 1's 的数字仅当两个操作数都有 1 时.

    0101  // 5
AND 1000  // 8
  = 0000 

现在让我们检查 ABS，它是左起第二位( 0100 ，即 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 的工作原理作为对读者的练习，但我希望你现在掌握了使用位掩码和“bit twiddling”的要点。