Project

General

Profile

Actions

Bug #14391

closed

Integer#digitsが遅い

Added by tompng (tomoya ishida) about 6 years ago. Updated over 2 years ago.

Status:
Closed
Target version:
-
ruby -v:
ruby 2.5.0p0 (2017-12-25 revision 61468) [x86_64-darwin16]
[ruby-dev:50427]
Tags:

Description

Integer#digitsが遅い

大きなIntegerのdigitsがto_sと比べてかなり遅い(計算量のオーダーが違う)ようです。

(9999**9999).to_s.chars.map(&:to_i).reverse # 0.030225秒
(9999**9999).digits # 1.187126秒 (40倍)

(99999**99999).to_s.chars.map(&:to_i).reverse # 1.888218秒
(99999**99999).digits # 195.594539秒 (100倍)

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

# example for 123456789.digits
[123456789]                 # initial
[23456789, 1]               # divmod with 100000000
[6789, 2345, 1]             # divmod with 10000
[89, 67, 45, 23, 1]         # divmod with 100
[9, 8, 7, 6, 5, 4, 3, 2, 1] # divmod with 10, done

to_sと共通の処理を使う方が良いとは思ったのですがかなり大変そうだったのでそうはなっていない(digits専用のコードを書いての)パッチです

# ベンチマーク(変更前、変更後、to_sの速度比較)
[99**99, 999**999, 9999**9999, 99999**99999].each do |num|
  t=Time.now; num.to_s(10); puts Time.now-t
  t=Time.now; num.digits(10); puts Time.now-t
  puts
end
__END__
          99**99  999**999  9999**9999  99999**99999
to_s      0.00001 0.0001    0.013         1.850
patched   0.00005 0.0011    0.020         2.269
original  0.0003  0.009     1.252       211.126

Files

digits_performance.patch (2.2 KB) digits_performance.patch tompng (tomoya ishida), 01/24/2018 12:45 PM

Updated by akr (Akira Tanaka) about 6 years ago

厳密にいえばこの提案とは独立な話な気もしますが、
base が 2の累乗の場合は乗除算は不要で、
さらに高速に処理できるだろうと思います。
(rb_integer_pack を使える気がする)

Updated by akr (Akira Tanaka) about 6 years ago

  • Status changed from Open to Assigned
  • Assignee set to mrkn (Kenta Murata)

Updated by jeremyevans0 (Jeremy Evans) almost 3 years ago

This issue still exists in the master branch. I've submitted a pull request for @tompng's patch: https://github.com/ruby/ruby/pull/4584

Actions #4

Updated by jeremyevans (Jeremy Evans) over 2 years ago

  • Status changed from Assigned to Closed

Applied in changeset git|9931e2f5091e95dd947de3b3a00167ae2fd5194a.


Improve performance of Integer#digits

This speeds up performance by multiple orders of magnitude for
large integers.

Fixes [Bug #14391]

Co-authored-by: tompng (tomoya ishida)

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0