6

Rubyでバイトのパリティが奇数か偶数かを計算する最良の方法は何ですか? 私は動作しているバージョンを持っています:

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

ただし、数値を文字列に変換して「1」を数えることは、パリティを計算する方法としては不十分です。より良い方法はありますか？

3DES キーのパリティを計算できるようにしたいと考えています。最終的には、偶数バイトを奇数バイトに変換したいと思います。

ありがとう、ダン

4

6 に答える 6

7

あなたが持っているものが十分に速くない限り、それを維持してください。明快で簡潔で、そのパフォーマンスは思ったよりも優れています。

私がテストした最速の方法である配列ルックアップに対してすべてをベンチマークします。

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

def odd_parity?(hex_string)
  ODD_PARITY[hex_string.to_i(16)]
end
  • 配列ルックアップは、1 秒あたり 640,000 バイトの速度でパリティを計算します。
  • Bowsersenior の C コードは、毎秒 640,000 バイトの速度でパリティを計算します。
  • コードは、1 秒あたり 284,000 バイトの速度でパリティを計算します。
  • Bowsersenior のネイティブ コードは、毎秒 171,000 バイトの速度でパリティを計算します。
  • Theo の短縮コードは、毎秒 128,000 バイトの速度でパリティを計算します。
于 2010-12-19T14:31:08.007 に答える
4

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 バージョンはネイティブ Ruby バージョンよりも 3 ～ 4 倍高速です。

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
于 2010-12-19T07:25:41.317 に答える
3

おそらく、255 個のエントリを持つ配列のルックアップ テーブルは、「Ruby で」最も高速なソリューションです。

CI では、マスクしてシフトします。または、SSE4 を使用している場合は、インライン アセンブラーで POPCNT 命令を使用します。これを高パフォーマンスにする必要がある場合は、上記のいずれかを行うネイティブ拡張を C で記述します。

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

于 2010-12-19T07:00:09.657 に答える
2

元のソリューションをメモ化で使用してみませんか？これは、整数値ごとに1回だけ計算されます。

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
于 2010-12-19T17:22:38.493 に答える
1

バイトの各ニブル（半分）に対応する、16エントリの単一のテーブル（16文字のテーブルとして）を作成します。エントリは0、1、1、2、1、2、....4です。

バイトをテストするには、

左のニブルをマスクして、番号を覚えてルックアップを行います。行う。右に4シフトし、2回目のルックアップを実行して、結果番号を前の番号に加算して合計を求めます。

次に、合計から下位ビットをテストします。1の場合、バイトは奇数であり、0の場合、バイトは偶数です。結果が偶数の場合は、xor命令を使用して上位ビットを反転します。このルックアップ方法は、1シフトで1バイトのビットを合計するよりもはるかに高速です。

8バイトのパリティを実行する簡単な関数について私にメールしてください。3DESは、8バイトの3つのグループを使用します。

于 2012-08-18T20:01:37.213 に答える
1 
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

読めないものが欲しい場合 ☺</p>

于 2010-12-19T10:19:40.293 に答える