* [ruby-dev:50427] [Ruby trunk Bug#14391] Integer#digitsが遅い
[not found] <redmine.issue-14391.20180124125758@ruby-lang.org>
@ 2018-01-24 12:58 ` tomoyapenguin
2018-01-27 2:04 ` [ruby-dev:50437] " akr
2018-01-27 2:24 ` [ruby-dev:50438] [Ruby trunk Bug#14391][Assigned] Integer#digitsが遅い akr
2 siblings, 0 replies; 3+ messages in thread
From: tomoyapenguin @ 2018-01-24 12:58 UTC (permalink / raw)
To: ruby-dev
Issue #14391 has been reported by tompng (tomoya ishida).
----------------------------------------
Bug #14391: Integer#digitsが遅い
https://bugs.ruby-lang.org/issues/14391
* Author: tompng (tomoya ishida)
* Status: Open
* Priority: Normal
* Assignee:
* Target version:
* 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] 3+ messages in thread
* [ruby-dev:50437] [Ruby trunk Bug#14391] Integer#digitsが遅い
[not found] <redmine.issue-14391.20180124125758@ruby-lang.org>
2018-01-24 12:58 ` [ruby-dev:50427] [Ruby trunk Bug#14391] Integer#digitsが遅い tomoyapenguin
@ 2018-01-27 2:04 ` akr
2018-01-27 2:24 ` [ruby-dev:50438] [Ruby trunk Bug#14391][Assigned] Integer#digitsが遅い akr
2 siblings, 0 replies; 3+ messages in thread
From: akr @ 2018-01-27 2:04 UTC (permalink / raw)
To: ruby-dev
Issue #14391 has been updated by akr (Akira Tanaka).
厳密にいえばこの提案とは独立な話な気もしますが、
base が 2の累乗の場合は乗除算は不要で、
さらに高速に処理できるだろうと思います。
(rb_integer_pack を使える気がする)
----------------------------------------
Bug #14391: Integer#digitsが遅い
https://bugs.ruby-lang.org/issues/14391#change-69877
* Author: tompng (tomoya ishida)
* Status: Open
* Priority: Normal
* Assignee:
* Target version:
* 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] 3+ messages in thread
* [ruby-dev:50438] [Ruby trunk Bug#14391][Assigned] Integer#digitsが遅い
[not found] <redmine.issue-14391.20180124125758@ruby-lang.org>
2018-01-24 12:58 ` [ruby-dev:50427] [Ruby trunk Bug#14391] Integer#digitsが遅い tomoyapenguin
2018-01-27 2:04 ` [ruby-dev:50437] " akr
@ 2018-01-27 2:24 ` akr
2 siblings, 0 replies; 3+ messages in thread
From: akr @ 2018-01-27 2:24 UTC (permalink / raw)
To: ruby-dev
Issue #14391 has been updated by akr (Akira Tanaka).
Status changed from Open to Assigned
Assignee set to mrkn (Kenta Murata)
----------------------------------------
Bug #14391: Integer#digitsが遅い
https://bugs.ruby-lang.org/issues/14391#change-69878
* Author: tompng (tomoya ishida)
* Status: Assigned
* Priority: Normal
* Assignee: mrkn (Kenta Murata)
* Target version:
* 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] 3+ messages in thread
end of thread, other threads:[~2018-01-27 2:24 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <redmine.issue-14391.20180124125758@ruby-lang.org>
2018-01-24 12:58 ` [ruby-dev:50427] [Ruby trunk Bug#14391] Integer#digitsが遅い tomoyapenguin
2018-01-27 2:04 ` [ruby-dev:50437] " akr
2018-01-27 2:24 ` [ruby-dev:50438] [Ruby trunk Bug#14391][Assigned] Integer#digitsが遅い akr
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 read-only IMAP folder(s) and NNTP newsgroup(s).