Hi, I've been posing dumb question on ruby-talk for so long now that I think its about time I contribute something; here is a fairly extensive BitVector extension. I know a lot of you has submitted similar extensions but IMHO this one is more "complete" so I hope someone finds it useful. You can find the README below and download it from RAA. If you try it out then I'd be esepcially interested in any violations to the "principle of Least Surprise" you might encounter. One main goal with the extension is that it should be truly Ruby-ish... Note that its an alpha release so there will likely be bugs. Please read the README and the TODO to see what is missing or not fully implemented. Documentation is thin as of now but please take a look at the unit tests since they give a good picture of how to use the extension. Regards, Robert ============================================================= = BitVector - Effecient bit vector class extension for Ruby = = version 0.1.5 (This is an alpha release) = ============================================================= Release date: 2000-11-21 Available from: http://www.ce.chalmers.se/~feldt/ruby/extensions/bitvector/ Author: Robert Feldt, feldt / ce.chalmers.se What is it? ----------- A fairly extensive and fast BitVector class for Ruby. Handles sequences of up to 2**32-1 bits (about 500 Mb)[FOOTNOTE 1]. Implemented as a wrapper around Bit::Vector version 6.0 by Steffen Beyer. Bit::Vector is a C library of fast routines for handling bit vectors. See steffen_beyers_bit_vector/README.txt for Steffen's intro to Bit::Vector. Installation? ------------- 1. unpack tarball (if you haven't already) 2. ruby extconf.rb 3. make 4. ruby tests/unittest_bitvector.rb runs the tests (OPTIONAL) 5. ruby install.rb Example of use? --------------- require 'bitvector' b = BitVector.new(100000).randomize # 1e5 random bits a = BitVector.new(100000).randomize # another 1e5 random bits c = a^b # exclusive or of 2*1e5 rand bits File.open("mybits", "w") {|f| # Dump bit vector to file f.write Marshal.dump(c) } BitVector.new(8, "10011011").ones # => [0,1,3,4,7] puts c.to_i # Print *large* number... Requirements? ------------- None known, but hey there are no garantuees here (see LICENSE). I've successfully compiled and used BitVector with Ruby 1.6.2 (2000-11-16) and cygwin 1.1.4 on Windows 2000 Professional Workstation and Windows NT 4.0 Workstation. If it works for you on other platforms/setups I'd appreciate if you drop me a note. However, it should work on most Ruby-enabled platforms. NOTE THAT THIS IS AN ALPHA RELEASE SO THERE WILL LIKELY BE BUGS. I've only used a small subset of all the methods in my own projects... Documentation? -------------- No Ruby-specific documentation yet but Ruby class very similar to the Perl class Bit:Vector, see http://www.engelschall.com/u/sb/download/Bit-Vector/ for more info. Also take a look in the unit tests which give examples of use, see file tests/unittest_bitvector.rb. License? -------- Same as the underlying Bit::Vector ie. LGPL. See LICENSE. If this is too strict then please contact me and we can work something out with Steffen Beyer. Special things to note? ----------------------- Methods randomize, * (multiply), / (divide), to_uint, to_i are *SLOW* and calling them for large bit vectors can take prohibitively *LONG* time. Run 'ruby tests/perftest_bitvector.rb' to get some timing data. Note: randomize is much faster if you use a probability of 0.5, ie. the default value. Plans for the future? --------------------- See TODO. This is an alpha release so there might be (some) changes to the interface. What is bitvector_extra.rb? --------------------------- Ruby file adding some lesser used methods to BitVector class. Might migrate to "main" class in the future or might be moved away. It is installed when you do "ruby install.rb". See tests/unittests_bitvector_extra.rb for some examples of use. Do you have comments or questions? ---------------------------------- I'd appreciate if you drop me a note if you're successfully using BitVector. If there are some known users I'll be more motivated to packing up additions / new versions and post them to RAA. Happy coding! Robert Feldt, feldt / ce.chalmers.se FOOTNOTE 1. The limit is actually the largest number that can be represented in an "unsigned long" in C. If you have a 64-bit machine the BitVectors are limited to >2e5 TeraByte so that'll probably be enough... ;-)