如何在 Erlang 二进制文件中一次高效地设置一位而不需要命令式？

Question

作为练习，我正在研究埃拉托斯特尼筛法的并行实现。作为其中的一部分，我正在实现一系列位图，每个数字使用一位来节省内存。一次读取一位似乎工作正常，但设置它们很慢，特别是当我使用大型二进制文件时。

getBit(Bin, N, Size)->
    R=Size-N-1,
    <<_:N,Bit:1,_:R>> = Bin,
    Bit.

setBit(Bin, N, Size)->
    R=Size-N-1,
    <<A:N,_:1,B:R>> = Bin,
    <<A:N,1:1,B:R>>.

有没有办法在函数式 Erlang 中很好地做到这一点，也许类似于数组的工作方式？ 我已经阅读过有关 hipe_bifs:bytearray_update 的内容，但更愿意保持我的编码风格正常运行。

Answer 1

您可以将位图存储为整数（如果它们不长于〜1000位）：

-module(z).
-export([get_bit/2, set_bit/2]).

get_bit(N, B) -> N band bit_to_int(B) > 0.
set_bit(N, B) -> N bor bit_to_int(B).

bit_to_int(B) -> 1 bsl B.

---

您可以尝试您的版本，不传递大小，并填充到字节：

getBit(Bin, N)->
    <<_:N/bitstring,Bit:1,_/bitstring>> = Bin,
    Bit.

setBit(Bin, N)->
    <<A:N,_:1,B/bitstring>> = Bin,
    <<A:N,1:1,B>>.

%OR:
setBit(Bin, N)->
    PSize = 8 - ((N + 1) rem 8),
    <<A:N,_:1, Pad:PSize,B/bytes>> = Bin,
    <<A:N,1:1,Pad:PSize,B>>.

可能更好或更差:-)

Answer 2

一般来说，对于 get 和 set 操作来说，复杂度都为 O(log(n)) ，这是再好不过的了，因为 Erlang 是函数式的语言。您可以使用某种类型的树来归档O(log(n))。 array、dict、gb_trees 和 gb_sets 模块执行此操作。

因此，如果您需要使其尽可能快，则必须使用命令式 - 您可以尝试 hipe_bifs 模块、流程字典和 ets 表。