Рассчитать соотношение байтов в Ruby - PullRequest
Новая
       42

Рассчитать соотношение байтов в Ruby

6 голосов
/ 19 декабря 2010

Как лучше всего рассчитать, имеет ли байт нечетное или четное соотношение в Ruby?У меня работает версия: 

result = "AB".to_i(16).to_s(2).count('1').odd?
=> true

Преобразование числа в строку и подсчет «1» кажется плохим способом вычисления четности.Есть ли лучшие методы?

Я хочу иметь возможность вычислить четность ключа 3DES.В конце концов, я хочу преобразовать четные байты в нечетные.

Спасибо, Дэн

Ответы [ 6 ]

7 голосов
/ 19 декабря 2010

Если то, что у вас есть, недостаточно быстро, сохраняйте это.Он понятен и лаконичен, а его производительность лучше, чем вы думаете.

Мы проведем сравнение всего с поиском по массиву, самым быстрым методом, который я тестировал: 

ODD_PARITY = [
  false,
  true,
  true,
  ...
  true,
  false,
]

def odd_parity?(hex_string)
  ODD_PARITY[hex_string.to_i(16)]
end
  • Вычисления по массивучетность со скоростью 640 000 байтов в секунду.
  • код C Bowsersenior вычисляет четность со скоростью 640 000 байтов в секунду.
  • Ваш код вычисляет четность со скоростью 284 000 байтов в секунду.
  • Собственный код Bowsersenior вычисляет четность со скоростью 171 000 байт в секунду.
  • Сокращенный код Тео вычисляет четность со скоростью 128 000 байт в секунду.
4 голосов
/ 19 декабря 2010

Вы смотрели на библиотеку RubyDES ?Это может избавить вас от необходимости писать собственную реализацию.

Для вычисления четности вы можете использовать что-то вроде следующего: 

require 'rubygems'
require 'inline'  # RubyInline (install with `gem install RubyInline`)

class Fixnum
  # native ruby version: simpler but slow
  # algorithm from: 
  #   http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel      
  def parity_native
    (((self * 0x0101010101010101) & 0x8040201008040201) % 0x1FF) & 1
  end

  class << self
    # inline c version using RubyInline to create c extension
    # 4-5 times faster than native version
    # use as class method: 
    #   Fixnum.parity(0xAB)
    inline :C do |builder|
      builder.c <<-EOC
      int parity_c(int num) {  
        return (
            ((num * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF
          ) & 1;
      }
      EOC
    end
  end

  def parity
    self.class.parity_c(self)
  end

  def parity_odd?
    1 == parity
  end
  def parity_even?
    0 == parity
  end
end

0xAB.parity        # => 1 
0xAB.parity_odd?   # => true 
0xAB.parity_even?  # => false
(0xAB + 1).parity  # => 0

В соответствии с простыми тестами, встроенная версия c равна 3-В 4 раза быстрее родной версии ruby ​​

require 'benchmark'
n = 10000
Benchmark.bm do |x|
  x.report("inline c") do
    n.times do 
      (0..255).map{|num| num.parity}
    end
  end

  x.report("native ruby") do
    n.times do 
      (0..255).map{|num| num.parity_native}
    end
  end
end
# inline c     1.982326s
# native ruby  7.044330s
3 голосов
/ 19 декабря 2010

Возможно, таблица поиска массива с 255 записями будет самым быстрым решением "In Ruby".

В C я бы маскировал и сдвигал. Или, если у меня SSE4, я бы использовал инструкцию POPCNT со встроенным ассемблером. Если вам нужна высокая производительность, напишите собственное расширение на C, которое выполняет любое из указанных выше действий.

http://en.wikipedia.org/wiki/SSE4

2 голосов
/ 19 декабря 2010

Как насчет использования вашего оригинального решения с памяткой?Это будет рассчитываться только один раз для каждого целочисленного значения. 

class Fixnum
  # Using a class variable for simplicity, and because subclasses of
  # Fixnum—while very uncommon—would likely want to share it. 
  @@parity = ::Hash.new{ |h,i| h[i] = i.to_s(2).count('1').odd? }
  def odd_parity?
    @@parity[self]
  end
  def even_parity?
    !@@parity[self]
  end
end

"AB".to_i(16).odd_parity?
#=> true
1 голос
/ 19 августа 2012

Я бы построил одну таблицу из 16 записей (в виде таблицы из 16 символов), соответствующую каждому кусочку (половине) байтов. Записи 0,1,1,2,1,2, .... 4

Для проверки вашего байта,

Замаскируйте левый клев и выполните поиск, запоминая номер. Делать. сдвиньте вправо на 4 и выполните второй поиск, добавив число результата к предыдущему, чтобы получить сумму.

Затем проверьте младший бит из суммы. Если это 1, байт нечетный, если это 0, байт четный. Если результат четный, вы переворачиваете старший бит, используя инструкцию xor. Этот метод поиска намного быстрее, чем сложение битов в байте за одну смену.

напишите мне для простой функции, чтобы сделать паритет для 8 байтов. 3DES использует 3 группы по 8 байтов.

1 голос
/ 19 декабря 2010 
x = 'AB'.to_i(16)
p = 0
until x == 0
  p += x & 1
  x = x >> 1
end
puts p # => 5

, которое можно сократить до 

x = 'AB'.to_i(16)
p = x & 1
p += x & 1 until (x >>= 1) == 0

если вы хотите что-то нечитаемое ☺

...