使用位数组节省空间

2016年8月23日，作者：David Farrell

"大数据"是一个被过度使用的术语，但当你真正处理大数据时，每个比特都很重要。从每天使用数十亿次的数据结构中削减几个比特可以节省大量空间。几个月前，我正在处理一个工作分配系统；它每天会发送数百万个工作。我们希望捕捉到系统做出的每一个决策，以便用户可以稍后查询系统以了解工作为什么没有被发送给合作伙伴。

问题是，系统每天做出数十亿次决策，因此我们需要一种方法来尽可能有效地打包这些决策。我的一个同事想到了一个绝妙的想法，即使用位数组，它效果非常好——我们能够将数据压缩18倍以上。如果你不熟悉位数组，或者对代码有些生疏，请继续阅读，我将向你展示如何使用Perl来使用它们。

位数组基础

位数组是一种将多个布尔值存储在单个数字中的方式。考虑数字0，它作为一个字节/八位表示为比特

00000000

我们不是将其当作数字来处理，而是使用位运算符，我们可以将每个比特当作一个单独的列来处理。由于这是一个8比特数字，我们可以在其中存储多达8个布尔值

0|0|0|0|0|0|0|0

要将布尔值存储在数组的第一个比特中，我们可以使用位或等于（|=）。以下是如何在C伪代码中实现的示例

short bit_array = 0;
bit_array |= 1 << 6;

让我们一步一步来。首先，我初始化一个名为bit_array的8比特整数。接下来，我创建一个二进制数字，该数字设置了我在bit_array中希望设置的比特。我是通过左移位代码1 << 6来做的。这意味着，“将数字中的比特左移6位”，这是这样做的

00000001 << 6;
01000000

这被称为掩码。接下来，我使用或等于来使用掩码更新bit_array为01000000。位或（|）通过将其左操作数中设置为1的比特设置为1来工作，这些比特在其右操作数中也设置为1。在末尾添加一个等号简单地将其结果赋给bit_array。

如果我们想将布尔值存储在第四个比特中，我们会这样做

bit_array |= 1 << 3;

所以现在bit_array看起来是这样的

01001000

要测试特定的比特是否已设置，我可以使用位与（&）

if (bit_array & (1 << 6)) {
  /* the seventh column is true */
}

位与返回一个数字，其左操作数中每个比特都设置为0，如果其在右操作数中也设置为0。所以代码1 << 6左移一个只有特定比特设置为1的数字（01000000）。这是掩码。如果位数组中有该比特设置为1，它将返回非零（true），否则返回零（false）。

Perl中的位数组

我将使用一个虚构的例子来展示位数组在Perl中的工作方式。想象我们在一家比萨饼店工作，处理一个订餐系统。我们需要存储比萨饼所需的全部配料。在Perl中，我们将数字存储在标量中，标量通常是32或64位长；这意味着我们可以将大量的配料打包到一个数字中！

以下是类

package Pizza::Order;
use utf8;

my %toppings = (
  tomato        => 1 << 0,
  cheese        => 1 << 1,
  onion         => 1 << 2,
  sausage       => 1 << 3,
  pepperoni     => 1 << 4,
  ham           => 1 << 5,
  chicken       => 1 << 6,
  bbq_chicken   => 1 << 7,
  olives        => 1 << 8,
  vegetables    => 1 << 9,
  jalapeńo      => 1 << 10,
  ranch         => 1 << 11,
  eggplant      => 1 << 12,
  garlic        => 1 << 13,
);

sub new {
  my $class = shift;
  my $self = 0;
  return bless \$self, $class;
}

sub print_state {
  my $self = shift;
  printf "%014b\n", $$self;
}

sub available_toppings {
  return keys %toppings;
}

sub add_topping {
  my ($self, $topping) = @_;
  # bitwise OR equals to set a bit field
  return $$self |= $toppings{ $topping };
}

sub remove_topping {
  my ($self, $topping) = @_;
  # bitwise NOT to invert a field and bitwise AND equals to unset it
  return $$self &= ~$toppings{ $topping };
}

sub get_toppings {
  my $self = shift;
  my @ordered_toppings = ();
  for my $topping (keys %toppings) {
    push @ordered_toppings, $topping
      # bitwise AND to test if this bit is set
      if $$self & $toppings{ $topping };
  }
  return @ordered_toppings;
}
1;

我创建了一个名为 Pizza::Order 的类。%toppings 哈希表存储披萨配料名称及其关联的位掩码。我只能想到14种配料，留下了18个备用插槽供将来使用（如果我们想坚持使用32位整数）。new 子例程是一个构造函数，它创建一个被祝福的标量作为 Pizza::Order 对象。

print_state 方法使用 printf 来打印披萨订单对象的状态作为二进制数。这是 printf 的一个非常有用的功能，许多其他语言都没有（例如C和Python）。add_topping 和 get_toppings 都使用了前面描述的技术来设置和检查设置的位。

更有趣的可能的是 remove_topping 方法。它使用位非（~）来反转位掩码，然后使用位与（&）来将其清除。很酷，对吧？这里有一个快速脚本来测试它

#!/usr/bin/perl
use Pizza::Order;

my $order = Pizza::Order->new();
$order->add_topping('cheese');
$order->add_topping('eggplant');
$order->remove_topping('cheese');
$order->add_topping('tomato');
$order->print_state();
print "$_\n" for $order->get_toppings();

这会打印出

01000000000001
eggplant
tomato

第一行是 $order 对象的当前状态。它显示了第一个和第二个到最后一个设置的位，分别对应于番茄和茄子位掩码。然后它会打印出那些配料。太棒了，它工作得很好！

位数组限制

在将位数组存储到磁盘上时要注意的一件事是代码更改。想象一下，如果我已经在数据库中保存了几年的披萨订单。然后有一天，我们停止提供烧烤鸡肉。更新配料哈希表会很诱人

my %toppings = (
  tomato        => 1 << 0,
  cheese        => 1 << 1,
  onion         => 1 << 2,
  sausage       => 1 << 3,
  pepperoni     => 1 << 4,
  ham           => 1 << 5,
  chicken       => 1 << 6,
  olives        => 1 << 7, # deleted bbq_chicken
  vegetables    => 1 << 8,
  jalapeńo      => 1 << 9,
  ranch         => 1 << 10,
  eggplant      => 1 << 11,
  garlic        => 1 << 12,
);

我删除了 bbq_chicken 条目，并将剩余的配料位掩码向上调整。问题是兼容性：在所有历史披萨订单中，olives（例如）的位掩码为 00000010000000，但在新代码中，它的位掩码要低一个。所以如果我尝试使用这个类加载历史订单，配料数据就会出错。处理这种情况的一种方法是在删除条目时删除而不是重新使用位掩码。

my %toppings = (
  tomato        => 1 << 0,
  cheese        => 1 << 1,
  onion         => 1 << 2,
  sausage       => 1 << 3,
  pepperoni     => 1 << 4,
  ham           => 1 << 5,
  chicken       => 1 << 6,
  # reserved
  olives        => 1 << 8,
  vegetables    => 1 << 9,
  jalapeńo      => 1 << 10,
  ranch         => 1 << 11,
  eggplant      => 1 << 12,
  garlic        => 1 << 13,
);

这种限制使得位掩码对于长期存储数据来说不那么有用，除非现有的位掩码不太可能更改。请注意，添加额外的配料和位掩码是可以的，只是重新使用现有的位掩码会导致问题。

还要考虑的是上限（更新 - 查看使用大整数的位数组）。如果你想让你的Perl代码与32位和64位Perl兼容，你可能会坚持使用32位位掩码（使用类似 bigint 的模块可能不会工作，因为地址内存限制）。你可以在命令行中输入 perl -V | grep longsize 来查看你的Perl编译的设置。longsize值是Perl可以原生存储在整数n中的字节数。

最后，为了从位数组中提取数据，需要用所有可用的位掩码进行测试。考虑 Pizza::Order 中的 get_toppings 方法。为了找出设置了哪些配料，代码必须检查每个配料的位掩码。这非常低效。所以位掩码对于紧凑的数据存储很有用，但不是快速访问。

参考

维基百科有关于位数组和位运算符的有用条目
Perl的官方操作符文档覆盖了位运算符。你可以在终端中使用命令 perldoc perlop 读取它
使用Perl的内置函数 sprintf （perldoc -f sprintf）和 printf （perldoc -f printf）来检查二进制值
将数字转换为二进制字符串打印不是Perl比其他语言更喜欢的二进制特性之一。另一个是能够像八进制和十六进制数字一样内联写入二进制数，例如：0b00001000。这对于比较二进制数来说很好
bigint 是CPAN上用于处理大整数的几个模块之一，请参阅使用大整数的位数组