digitalmars.D.bugs - [Issue 10238] New: Various small improvements for std.bitmanip.BitArray
- d-bugmail puremagic.com (97/97) Jun 02 2013 http://d.puremagic.com/issues/show_bug.cgi?id=10238
- d-bugmail puremagic.com (11/11) Jun 02 2013 http://d.puremagic.com/issues/show_bug.cgi?id=10238
http://d.puremagic.com/issues/show_bug.cgi?id=10238 Summary: Various small improvements for std.bitmanip.BitArray Product: D Version: D2 Platform: All OS/Version: All Status: NEW Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nobody puremagic.com ReportedBy: bearophile_hugs eml.cc Split from Issue 4124. I suggest to add some useful methods to BitArray: - reset all bits - set all bits - are all bit set? - are all bit reset? - set n-th bit (this can be a little more efficient than bs[n]=1;) - reset n-th bit (this can be a little more efficient than bs[n]=1;) - flip n-th bit After Issue 4124 "%b" (unlike "%s") produces a string output that's not usable to build a new BitArray, this is another enhancement request (underscores and leading-trailing whitespace should be ignored): import std.stdio, std.bitmanip, std.conv, std.string; void main() { BitArray b1; b1.init([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); writefln("%b", b1); // Prints: 00001111_00001111 BitArray b2; // Error: function std.bitmanip.BitArray.init (bool[] ba) // is not callable using argument types (string) b2.init("00001111_00001111"); } - - - - - - - - - - The usefulness of isSet(), set(), and reset() methods is visible with two benchmarks. They implement the same algorithm (a simple sieve), the first uses a BitArray, and the second a manually implemented bit array. On my 32 bit system the second program is about two times faster than the first one. import std.stdio, std.algorithm, std.range, std.math, std.bitmanip, std.datetime; uint[] primes(uint n) { if (n < 2) return []; BitArray F; F.length = n + 1; F[0] = true; F[1] = true; foreach (i; 2 .. cast(uint)sqrt(n)) if (!F[i]) for (uint j = i * i; j <= n; j += i) F[j] = true; return array(filter!((i){ return !F[i]; })(iota(n+1))); } void main() { StopWatch sw; sw.start(); primes(30_000_000); sw.stop(); writeln(sw.peek().msecs / 1000.0); } - - - - - - - - - - import std.stdio, std.algorithm, std.range, std.math, std.datetime; size_t[] primes(in size_t n) { enum size_t bpc = size_t.sizeof * 8; auto F = new size_t[n / bpc + 1]; F[] = size_t.max; bool isSet(in size_t i) nothrow { immutable size_t offset = i / bpc; immutable size_t mask = 1 << (i % bpc); return (F[offset] & mask) != 0; } void clear(in size_t i) nothrow { immutable size_t offset = i / bpc; immutable size_t mask = 1 << (i % bpc); if ((F[offset] & mask) != 0) F[offset] = F[offset] ^ mask; } clear(0); clear(1); foreach (i; 2 .. cast(size_t)sqrt(n)) if (isSet(i)) for (uint j = i * i; j <= n; j += i) clear(j); return array(filter!isSet(iota(n + 1))); } void main() { StopWatch sw; sw.start(); size_t n = primes(30_000_000).length; sw.stop(); writeln(sw.peek().msecs / 1000.0); writeln("n primes: ", n); } -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 02 2013
http://d.puremagic.com/issues/show_bug.cgi?id=10238 bearophile_hugs eml.cc changed: What |Removed |Added ---------------------------------------------------------------------------- See Also| |http://d.puremagic.com/issu | |es/show_bug.cgi?id=10238 See also Issue 10239 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 02 2013