Чередование бит оптимизировано для Ruby

Question

Конечно, оптимизация битового твилинга в Ruby - это несоответствие с самого начала. Кроме того, я ищу фрагмент или драгоценный камень, который может чередовать две произвольные целочисленные координаты, оптимизированные наилучшим образом для MRI (1.9) или нативного драгоценного камня.

Некоторые подходы в C: http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious

В качестве примера или отправной точки приведем «Чередование битов очевидным способом» в Ruby, несколько упрощенное, чтобы не создавать временных массивов (которые увеличивают время выполнения примерно в 2 раза на массив), а также метод двоичной длины, встроенный дальнейшее уменьшение на 6% (если вы знаете, что ни один из входов не равен нулю, вы можете пропустить эту проверку еще на несколько процентов ..)

def interleave(y)
  z = 0
  bl = self > 0 ? Math.log2(self) : 1
  ybl = y > 0 ? Math.log2(y) : 1
  ((((bl <=> ybl) == -1) ? ybl : bl).floor + 1).times{|i| z |= (self & 1 << i) << i | (y & 1 << i) << (i + 1)}
  return z
end

Результаты 2,66 ГГц i5 с 1.9.2p180:

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)

Конечно, есть лучший способ?

---

Обновление

Я включил нулевое исправление от @Wayne Conrad, хотя и намного страшнее, чем его, и лишь немного быстрее. Также сдвинул пол и + 1, чтобы выполнить его один раз, а не дважды за.

Вот Суть этого с соответствующим de-interleave .

Answer 1

Вот быстрая и пошлая реализация, которая поможет вам, пока не появится хорошая:

def mortanize(x, y)
  xs, ys = [x, y].map do |n|
    n.to_s(2)
  end
  nbits = [xs, ys].map(&:size).max
  xs, ys = [xs, ys].map do |n|
    ('0' * (nbits - n.size) + n).chars
  end
  ys.zip(xs).join.to_i(2)
end

Как и следовало ожидать, это не скорость, Дэймон. На моем компьютере с MRI 1.8.7 он вычисляет около 35 000 16-битных результатов в секунду. Ваш вычисляет 68 000 16-битных результатов в секунду. Или посмотрите следующий алгоритм для 256 000 16-битных результатов в секунду.

---

Если вы готовы обменять немного памяти и время запуска на скорость, то:

def base_mortanize(x, y)
  xs, ys = [x, y].map do |n|
    n.to_s(2)
  end
  nbits = [xs, ys].map(&:size).max
  xs, ys = [xs, ys].map do |n|
    ('0' * (nbits - n.size) + n).chars
  end
  ys.zip(xs).join.to_i(2)
end

MORTON_TABLE_X = 256.times.map do |x|
  base_mortanize(x, 0)
end

MORTON_TABLE_Y = 256.times.map do |y|
  base_mortanize(0, y)
end

def mortanize(x, y)
  z = []
  while (x > 0 || y > 0)
    z << (MORTON_TABLE_X[x & 0xff] | MORTON_TABLE_Y[y & 0xff])
    x >>= 8
    y >>= 8
  end
  z.reverse.inject(0) do |result, word|
    result << 16 | word
  end
end

Это вычисляет 256 000 16-битных результатов в секунду.

---

В вашем ответе есть ошибка, если любой аргумент равен нулю. Вот одно из возможных исправлений. Сначала определите эту функцию:

def bit_size(x)
  return 1 if x == 0
  Math.log2(x).floor + 1
end

А затем, внутри interleave, заменить:

z, bl, ybl = 0, (Math.log2(self)).floor + 1, (Math.log2(y)).floor + 1

с:

z = 0
bl = bit_size(x)
ybl = bit_size(y)

---

Вот пример теста rspec, который я использовал:

describe "mortanize" do
  it "should interleave integers" do
    mortanize(0, 0).should eql 0
    mortanize(0, 1).should eql 2
    mortanize(1, 0).should eql 1
    mortanize(0xf, 0x3).should eql 0x5f
    mortanize(0x3, 0xf).should eql 0xaf
    mortanize(0xf, 0x0).should eql 0x55
    mortanize(0x0, 0xf).should eql 0xaa
    mortanize(0x3, 0xc).should eql 0xa5
    mortanize(0xf, 0xf).should eql 0xff
    mortanize(0x1234, 0x4321).should eql 0x210e0d12
  end
end

Answer 2

Вот еще одно решение, оцененное примерно на 50% быстрее, чем принятое, и для 16-разрядных целых чисел (где первое делает только 8-разрядное):

Magic = [0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF]

# Interleave lower 16 bits of x and y, so the bits of x
# are in the even positions and bits from y in the odd;
# z gets the resulting 32-bit Morton Number.  
# x and y must initially be less than 65536.
# Rubyfied from http://graphics.stanford.edu/~seander/bithacks.html
def _interleave_bits_16b(x,y)
  x = (x | (x << 8)) & Magic[3]
  x = (x | (x << 4)) & Magic[2]
  x = (x | (x << 2)) & Magic[1]
  x = (x | (x << 1)) & Magic[0]
  y = (y | (y << 8)) & Magic[3]
  y = (y | (y << 4)) & Magic[2]
  y = (y | (y << 2)) & Magic[1]
  y = (y | (y << 1)) & Magic[0]
  z = x | (y << 1)
end

Answer 3

Если у вас уже есть реализация на C, вы можете использовать FFI , в противном случае вы можете написать ее напрямую с помощью RubyInline