Project

General

Profile

Feature #14401

Integer#digitsの逆の動作をするメソッドが欲しい

Added by tompng (tomoya ishida) 4 months ago.

Status:
Open
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-dev:50432]

Description

Integer#digitsの逆の動作をするメソッドがあると良いと思うのですがどうでしょうか?

inverse_of_digits([5,4,3,2,1]) # => 12345
inverse_of_digits([1,0,1,1], 2) # => 13
inverse_of_digits(num.digits(base), base) == num #=> true

以下のようなケースで便利です

# colors
rgba = [0xff, 0x00, 0x00, 0x80]
color_int = inverse_of_digits(rgba, 256)

# encoder, decoder
module Base52
  CHARS = [*(?A..?Z),*(?a..?z)]
  def self.encode str
    num = inverse_of_digits(str.bytes, 256)
    num.digits(52).map{|i|CHARS[i]}.join
  end

  def self.decode str
    digits = str.chars.map { |c| CHARS.index c }
    num = inverse_of_digits(digits, 52)
    num.digits(256).map(&:chr).join
  end
end

また、rubyでこのメソッドを以下のように作ると実行速度が非常に遅いので、ruby本体に効率的な方法で実装されていると良いのではと思います。

def inverse_of_digits digits, base = 10
  num = 0; digits.reverse_each { |n| num = num * base + n }; num
end
inverse_of_digits [9]*1_000_000 # takes about 5 minutes
([9]*1_000_000).join.reverse.to_i; # ends within a second

メソッド名

Integer.from_digits(digits, base = 10)

が良いと思うのですがどうでしょう?

他思いついた名前:

Array#revert_digits(base = 10)
Integer(string, base=10) を Integer(string_or_digits, base=10) に変える

実装

以下のアルゴリズムでパッチを作りました。

# converting [9, 8, 7, 6, 5, 4, 3, 2, 1] to 123456789
[9, 8, 7, 6, 5, 4, 3, 2, 1] # first, dup the given array
[89, 67, 45, 23, 1, 0, ...] # collapse two adjacent numbers with `base * right + left`,  base=10
[6789, 2345, 1, 0, 0,  ...] # with base=100
[23456789, 1, 0, 0, 0, ...] # with base=10000
[123456789, 0, 0, 0,   ...] # with base=100000000, done. return the first value

ベンチマーク(to_iとの比較)

[1_000, 10_000, 100_000, 1000_000].each do |n|
  d = [9] * n
  s = '9' * n
  puts "n=#{n}"
  t=Time.now; Integer.from_digits(d); puts "digits: #{Time.now-t}"
  t=Time.now; s.to_i; puts "to_i:   #{Time.now-t}"
  puts
end
__END__
n      1000     10000     100000    1000000
digits 7.2e-05  0.001104  0.017904  0.453604
to_i   5.0e-05  0.000594  0.015725  0.451933

他に考慮すべき点

範囲外の数字(負数やbase以上の数)が含まれてる場合はエラー扱いすべきか?

inverse_of_digits([-1,11,0,1], 10) #=> 1109 or Error?

個人的にはエラー扱いせず計算してしまっていいんじゃないかと思います。

  • エラーださなくてもあまり害はなさそう
  • あらかじめ繰り上がり繰り下がり処理をした上で渡すという手間が省けるので便利
inverse_of_digits.patch (3.04 KB) inverse_of_digits.patch tompng (tomoya ishida), 01/25/2018 12:43 PM

Also available in: Atom PDF