Ruby:计算二进制数中 1 的个数

Question

我有一个表示为字符串“01100011....”的二进制数(52 位)

计算 1 的个数最快的方法是什么？

"01100011....".count("1") 

显然有效，但如果此操作需要执行数千次，则非常耗时。

好的，还有更多信息。我正在尝试为单词创建位向量，如下所示

def bit_vec(str)
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    bv = ""
    alphabet.each_char do |a|
        if str.include?(a)
            bv += "1"
        else
            bv += "0"
        end
    end
        bv
end

bit_vec 方法被调用了大约 17 万次。我将位向量存储在哈希中，并使用它们通过对位向量进行异或运算并计算 1 的数量(更多 1 == 相似度更低)来查找给定单词的相似单词。如果计数方法不使用 String#scan，还有什么可以使用它？

我知道 Ruby 比 C 或 Java 慢。我只是想尽我所能改进算法。我不是在寻找原始速度。

也许包括？方法是瓶颈？

Answer 1

请注意，计算 1 位的问题称为“人口计数”。

至少在 Ruby 中，坚持通过 count 方法将它们作为字符串处理，除非您有令人信服的理由使用整数。

计数:

基准:10,000,000 次迭代需要 78.60 秒(每秒 127,225.63 次迭代)

对于整数数学，

如果您不关心 2**32 以上的值，

def popcount(x)
  m1 = 0x55555555
  m2 = 0x33333333
  m4 = 0x0f0f0f0f
  x -= (x >> 1) & m1
  x = (x & m2) + ((x >> 2) & m2)
  x = (x + (x >> 4)) & m4
  x += x >> 8
  return (x + (x >> 16)) & 0x3f
end

基准:10,000,000 次迭代需要 105.73 秒(每秒 94,579.03 次迭代)

如果您确实关心高于 2**32 的值，

def popcount(x)
  b = 0
  while x > 0
    x &= x - 1
    b += 1
  end
  return b
end

基准:10,000,000 次迭代需要 365.59 秒(每秒 27,353.27 次迭代)

附录:

您的代码:

基准:1,000,000 次迭代需要 78.25 秒(每秒 12,779.56 次迭代)

这段代码:

def bit_vec(str)
  # alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
  bv = "0" * 52
  str.each_char do |c|
    ord = c.ord
    next unless (ord >= 65 && ord <= 90) || (ord >= 97 && ord <= 122)
    index = ord - 65
    index -= 6 if index > 25
    bv[index] = "1"
    break if bv == "1111111111111111111111111111111111111111111111111111"
  end
  bv
end

注意:您说您正在处理一个 52 位数字，所以我假设您关心大小写字母 (26 + 26 = 52)。我选择首先检查大写字母，因为这是它们出现在几乎所有字符集中的方式，使计算更容易一些。

基准:1,000,000 次迭代需要 24.86 秒(每秒 40,231.60 次迭代)

3.14 倍加速。