Databases
StackOverflow2013
Postsdbo
POBit interleaving optimized for Ruby
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBit interleaving optimized for Ruby
    text
    copied!<p>Granted, optimizing bit twiddling in Ruby is a bit of a mismatch to begin with. That aside, I'm looking for a snippet or a gem that can interleave two arbitrary integer coords optimized as best can be for MRI (1.9) or a native gem.</p> <p>Some approaches in C are: <a href="http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious" rel="nofollow">http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious</a></p> <p>As an example or starting point, here's "Interleave bits the obvious way" in Ruby, somewhat uglified to keep it from creating temp arrays (which increase the runtime by about 2X per array) and with a binary length method inlined for a further 6% decrease (If you know neither input is ever zero, you can omit that check for a few percent more..)</p> <pre><code>def interleave(y) z = 0 bl = self &gt; 0 ? Math.log2(self) : 1 ybl = y &gt; 0 ? Math.log2(y) : 1 ((((bl &lt;=&gt; ybl) == -1) ? ybl : bl).floor + 1).times{|i| z |= (self &amp; 1 &lt;&lt; i) &lt;&lt; i | (y &amp; 1 &lt;&lt; i) &lt;&lt; (i + 1)} return z end </code></pre> <p>Results from a 2.66Ghz i5 with 1.9.2p180:</p> <pre><code>x = y = 0b11111111_11111111_11111111_11111111 Benchmark.bm{|bm| bm.report{1000000.times{x.interleave(y)}}} user system total real 18.360000 0.010000 18.370000 ( 18.356196) </code></pre> <p>Surely there's a better way?</p> <hr> <h3>Update</h3> <p>I included the zero fix from @Wayne Conrad, albeit far uglier than his and only marginally faster. Also moved the floor and + 1 so as to be executed once instead of twice per.</p> <p>Here is a <a href="https://gist.github.com/846454" rel="nofollow">Gist of this with matching de-interleave</a>.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload