Ruby の C拡張で約数を求めるメソッドを書いた
なぜか Ruby 本体には、約数を求めるメソッドがないようですので、C拡張で作ってみました。
以前書いた Utilsc への機能追加です。コードは必要な部分だけ載せます。全体のコードはここ です。
#include "utilsc.h" #include "math.h" VALUE divisors(VALUE self) { int a; long i, se; VALUE ar; se = FIX2LONG(self); ar = rb_ary_new(); a = (int)sqrt(se); for (i = 1; i <= a; i++) { if (!(se % i)) { rb_ary_push(ar, INT2FIX(i)); rb_ary_push(ar, INT2FIX(se / i)); } } return rb_funcall(ar, rb_intern("uniq"), 0); } void Init_utilsc(void){ VALUE fix; fix = rb_const_get(rb_cObject, rb_intern("Fixnum")); rb_define_method(fix, "totient", totient, 0); rb_define_method(fix, "divisors", divisors, 0); }
メソッドは Fixnum#divisors です。以前 Ruby で書いたもの(参照)とほぼ同じですが、返される配列はソートされていません。例:
require 'bundler/setup' require 'utilsc' p 150.divisors #=>[1, 150, 2, 75, 3, 50, 5, 30, 6, 25, 10, 15]
ベンチマーク
require 'bundler/setup' require 'utils' 100_0000.times do |i| (i + 1).divisors_int end
これでおよそ 117秒 かかりました。
C拡張版。
require 'bundler/setup' require 'utilsc' 100_0000.times do |i| (i + 1).divisors.sort end
かかったのはおよそ 11秒です。
10倍高速化されたということですね。まずまずだと思います。
※追記
GitHub の使い方で参考になったページ:
git pushがrejectされたときの解決の手順 - 今日もスミマセン。
今さら聞けない!GitHubの使い方【超初心者向け】 | TechAcademyマガジン