In C, I can declare a large boolean array filled with 0, like this:

_Bool* sieve = malloc(limit   1);

And in Python:

sieve = bytearray({False}) * (limit   1)

In Ruby, I could do it like this:

sieve = [false] * (limit   1)

But this seems to take up a lot of memory; the Python version takes len(sieve) 57 bytes, but the Ruby one takes sieve.length * 8 40 bytes.
Is there any way to have a shorter array just for booleans? I'm fine with something like the Python version, so it doesn't have to be sieve.length bytes like C, and I would prefer simpler code if it achieves something like the Python version.

CodePudding user response：

You are probably looking for a binary String or a new Ruby 3.1 feature called IO::Buffer. To even further compress the bits (8 bits per byte) you will want to do something like this:

class BitString
  include Enumerable

  def initialize(size)
    @size = size
    @str = "\0".b * (size / 8.0).ceil
  end

  attr_reader :size
  alias length size

  def [](bit)
    (@str[bit / 8].ord >> (7 - bit % 8) & 1) == 1
  end

  def []=(bit, val)
    @str[bit / 8] = case val
    when true
      @str[bit / 8].ord | (1 << (7 - bit % 8))
    when false
      @str[bit / 8].ord & ~(1 << (7 - bit % 8))
    else
      raise ArgumentError, "can only set a boolean value on a BitString"
    end.chr
  end

  def each(&block)
    return enum_for(:each) { @size } unless block_given?

    @size.times { |i| yield self[i] }
  end

  def to_s
    @str
  end
end

bs = BitString.new(10)
bs.length
# => 10
bs[3] = true
bs.to_s
# => "\x10\x00"
bs[3]
# => true
bs.map { |i| i ? 1 : 0 }
# => [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
bs.any?
# => true
bs[3] = false
bs.any?
# => false