ruby-dev (Japanese) list archive (unofficial mirror)
 help / color / mirror / Atom feed
* [ruby-dev:51066] [Ruby master Bug#14391] Integer#digitsが遅い
       [not found] <redmine.issue-14391.20180124125758.10330@ruby-lang.org>
@ 2021-06-17 19:39 ` merch-redmine
  0 siblings, 0 replies; only message in thread
From: merch-redmine @ 2021-06-17 19:39 UTC (permalink / raw)
  To: ruby-dev

Issue #14391 has been updated by jeremyevans0 (Jeremy Evans).


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

----------------------------------------
Bug #14391: Integer#digitsが遅い
https://bugs.ruby-lang.org/issues/14391#change-92581

* Author: tompng (tomoya ishida)
* Status: Assigned
* Priority: Normal
* Assignee: mrkn (Kenta Murata)
* ruby -v: ruby 2.5.0p0 (2017-12-25 revision 61468) [x86_64-darwin16]
* Backport: 2.3: UNKNOWN, 2.4: UNKNOWN, 2.5: UNKNOWN
----------------------------------------
Integer#digitsが遅い

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

~~~ ruby
(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倍)
~~~

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

~~~ ruby
# 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専用のコードを書いての)パッチです


~~~ ruby
# ベンチマーク(変更前、変更後、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)


-- 
https://bugs.ruby-lang.org/

^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2021-06-17 19:39 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <redmine.issue-14391.20180124125758.10330@ruby-lang.org>
2021-06-17 19:39 ` [ruby-dev:51066] [Ruby master Bug#14391] Integer#digitsが遅い merch-redmine

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).