Problem 1 - yokojiの日記

問題

10未満の自然数の中で3 または 5 の倍数の数は 3, 5, 6, 9 であり、これらの合計は 23 である。
同様に、1,000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。

回答

Haskell ※ご指摘頂いたので修正しました。ありがとうございます！

sum [ x | x <- [1..999], rem x 3 == 0 || rem x 5 == 0 ]

Ruby

(1..999).select { |x| x % 3 == 0 || x % 5 == 0 }.inject(&:+)

Python

sum([ x for x in range(1000) if x % 5 == 0 or x % 3 == 0 ])

リストの内包表記と配列のsumを使えるHaskell, Pythonはほぼ同様に書ける。

Rubyにはリストの内包表記とsumがないので、injectを使った。
ActiveSupportにArray#sumがあるが、内部ではinjectを使って実装されているようだ。

activesupport-3.1.3/lib/active_support/core_ext/enumerable.rb

def sum(identity = 0, &block)
  if block_given?
    map(&block).sum(identity)
  else
    inject { |sum, element| sum + element } || identity
  end
end

Array#sumを使うとしたらこうなるか

Ruby w/Array#sum

(1...1000).select { |x| x % 3 == 0 || x % 5 == 0 }.sum

個人的にはHaskellやPythonのリストの内包表記、sumの使い方はどうも処理が追いにくい。
がしがし書かれるとどこから読んでいいか迷いそう。

その点Rubyはリスト操作が左から順に処理を追えるので見やすい。慣れですかね。

[追記]
Pythonの内包表記は不要な要素をappend()しないので速いらしいという記事を見つけた。
参考: http://dsas.blog.klab.org/archives/51742727.html

Rubyの範囲オブジェクトにselect使ったらどうなってるんかいな？と思ったのでちょっと追いかけた

Rangeの継承関係は以下のようになっているらしい。

Range < Enumerable < Object < Kernel < BasicObject

selectはEnumerableから引き継いでいるようだ。CRubyのソースコードをチラ見したところ、ブロックの評価結果が真だと、追加オブジェクト種別に応じたCの配列に追加しているぽい

vmでブロックを評価するコストを追ってみたいなあ。

src/ruby-1.9.2-p290/enum.c

/*
 *  call-seq:
 *     enum.find_all {| obj | block }  -> array
 *     enum.select   {| obj | block }  -> array
 *     enum.find_all                   -> an_enumerator
 *     enum.select                     -> an_enumerator
 *
 *  Returns an array containing all elements of <i>enum</i> for which
 *  <em>block</em> is not <code>false</code> (see also
 *  <code>Enumerable#reject</code>).
 *
 *  If no block is given, an enumerator is returned instead.
 *
 *
 *     (1..10).find_all {|i|  i % 3 == 0 }   #=> [3, 6, 9]
 *
 */

static VALUE
enum_find_all(VALUE obj)
{
    VALUE ary;

    RETURN_ENUMERATOR(obj, 0, 0);

    ary = rb_ary_new();
    rb_block_call(obj, id_each, 0, 0, find_all_i, ary);

    return ary;
}

static VALUE
find_all_i(VALUE i, VALUE ary, int argc, VALUE *argv)
{
    ENUM_WANT_SVALUE();

    if (RTEST(rb_yield(i))) {
	rb_ary_push(ary, i);
    }
    return Qnil;
}

src/ruby-1.9.2-p290/array.c

VALUE
rb_ary_push(VALUE ary, VALUE item)
{
    rb_ary_modify(ary);
    return rb_ary_push_1(ary, item);
}

static VALUE
rb_ary_push_1(VALUE ary, VALUE item)
{
    long idx = RARRAY_LEN(ary);

    if (idx >= ARY_CAPA(ary)) {
	ary_double_capa(ary, idx);
    }
    RARRAY_PTR(ary)[idx] = item;
    ARY_SET_LEN(ary, idx + 1);
    return ary;
}

src/ruby-1.9.2-p290/vm_eval.c

VALUE
rb_yield(VALUE val)
{
    if (val == Qundef) {
	return rb_yield_0(0, 0);
    }
    else {
	return rb_yield_0(1, &val);
    }
}

static inline VALUE
rb_yield_0(int argc, const VALUE * argv)
{
    return vm_yield(GET_THREAD(), argc, argv);
}

src/ruby-1.9.2-p290/vm.c

static inline VALUE
vm_yield(rb_thread_t *th, int argc, const VALUE *argv)
{
    const rb_block_t *blockptr = check_block(th);
    return invoke_block_from_c(th, blockptr, blockptr->self, argc, argv, 0, 0);
}

static inline VALUE
invoke_block_from_c(rb_thread_t *th, const rb_block_t *block,
		    VALUE self, int argc, const VALUE *argv,
		    const rb_block_t *blockptr, const NODE *cref)
{
    if (SPECIAL_CONST_P(block->iseq))
	return Qnil;
    else if (BUILTIN_TYPE(block->iseq) != T_NODE) {
	const rb_iseq_t *iseq = block->iseq;
	const rb_control_frame_t *cfp;
	rb_control_frame_t *ncfp;
	int i, opt_pc, arg_size = iseq->arg_size;
	int type = block_proc_is_lambda(block->proc) ?
	  VM_FRAME_MAGIC_LAMBDA : VM_FRAME_MAGIC_BLOCK;

	rb_vm_set_finish_env(th);

	cfp = th->cfp;
	CHECK_STACK_OVERFLOW(cfp, argc + iseq->stack_max);

	for (i=0; i<argc; i++) {
	    cfp->sp[i] = argv[i];
	}

	opt_pc = vm_yield_setup_args(th, iseq, argc, cfp->sp, blockptr,
				     type == VM_FRAME_MAGIC_LAMBDA);

	ncfp = vm_push_frame(th, iseq, type,
			     self, GC_GUARDED_PTR(block->dfp),
			     iseq->iseq_encoded + opt_pc, cfp->sp + arg_size, block->lfp,
			     iseq->local_size - arg_size);
	ncfp->me = th->passed_me;
	th->passed_me = 0;
	th->passed_block = blockptr;

	if (cref) {
	    th->cfp->dfp[-1] = (VALUE)cref;
	}

	return vm_exec(th);
    }
    else {
	return vm_yield_with_cfunc(th, block, self, argc, argv, blockptr);
    }
}

src/ruby-1.9.2-p290/include/ruby/ruby.h

struct RArray {
    struct RBasic basic;
    union {
	struct {
	    long len;
	    union {
		long capa;
		VALUE shared;
	    } aux;
	    VALUE *ptr;
	} heap;
	VALUE ary[RARRAY_EMBED_LEN_MAX];
    } as;
};

#define R_CAST(st)   (struct st*)
#define RARRAY(obj)  (R_CAST(RArray)(obj))

#define RARRAY_PTR(a) \
    ((RBASIC(a)->flags & RARRAY_EMBED_FLAG) ? \
     RARRAY(a)->as.ary : \
     RARRAY(a)->as.heap.ptr)