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

Question

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

计算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方法被调用大约170K次.我将位向量存储在散列中,并使用它们通过对位向量进行异或并计算1的数量(更多1 = =更少的相似性)来查找给定单词的相似单词.如果count方法不使用String#scan,还有什么可以使用它？

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

也许包括？方法是瓶颈？

Answer 1

O(n)无论如何,你都会有表演.试试这个简单的ruby命令.测量它是否真的是一个问题.

这个简单的脚本,用time ruby test.rb0.058 CPU秒测量.这是一个旧的1.25 Ghz处理器.你真的确定这个操作太慢了吗？

10000.times do
  "0100010000100001111101101000111110000001101001010".count("1")
end

如果这还不够快,请写一个C扩展名.尽量避免使用条件.写这样:

count = 0;
for (i = stringLength; i; i++) {
    count += string[i] - '0';     // no conditional used.
}

但老实说,如果你需要那种速度,红宝石对你来说是错误的语言.有红宝石这么多不同的事情,需要很多比简单的更多的时间.count("1").

Answer 2

注意,计数1位的问题被称为"人口计数".

至少在Ruby中,count除非你有令人信服的理由使用整数,否则坚持通过该方法将这些作为字符串处理.

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倍加速.