ruby-changes:7200
From: nobu <ko1@a...>
Date: Wed, 20 Aug 2008 16:40:22 +0900 (JST)
Subject: [ruby-changes:7200] Ruby:r18719 (trunk): * array.c (rb_ary_sample): performance improvement for huge array.
nobu 2008-08-20 16:40:03 +0900 (Wed, 20 Aug 2008) New Revision: 18719 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=18719 Log: * array.c (rb_ary_sample): performance improvement for huge array. Modified files: trunk/ChangeLog trunk/array.c Index: array.c =================================================================== --- array.c (revision 18718) +++ array.c (revision 18719) @@ -3022,35 +3022,71 @@ static VALUE rb_ary_sample(int argc, VALUE *argv, VALUE ary) { - VALUE nv, result; - int n, len, i, j; + VALUE nv, result, *ptr; + long n, len, i, j, k, idx[10]; len = RARRAY_LEN(ary); if (argc == 0) { if (len == 0) return Qnil; - i = rb_genrand_real()*len; + i = len == 1 ? 0 : rb_genrand_real()*len; return RARRAY_PTR(ary)[i]; } rb_scan_args(argc, argv, "1", &nv); - n = NUM2INT(nv); + n = NUM2LONG(nv); + ptr = RARRAY_PTR(ary); + len = RARRAY_LEN(ary); if (n > len) n = len; - if (n == 0) return rb_ary_new2(0); - result = rb_ary_new2(n); - for (i=0; i<n; i++) { - retry: - j = rb_genrand_real()*len; - nv = LONG2NUM(j); - for (j=0; j<i; j++) { - if (RARRAY_PTR(result)[j] == nv) - goto retry; + switch (n) { + case 0: return rb_ary_new2(0); + case 1: + return rb_ary_new4(1, &ptr[(long)(rb_genrand_real()*len)]); + case 2: + i = rb_genrand_real()*len; + j = rb_genrand_real()*(len-1); + if (j == i) j++; + return rb_ary_new3(2, ptr[i], ptr[j]); + case 3: + i = rb_genrand_real()*len; + j = rb_genrand_real()*(len-1); + k = rb_genrand_real()*(len-2); + if (j == i) j++; + if ((k == i) ? (++k == j) : (k == j) ? (++k == i): 0) ++k; + return rb_ary_new3(3, ptr[i], ptr[j], ptr[k]); + } + if (n < sizeof(idx)/sizeof(idx[0])) { + idx[0] = rb_genrand_real()*len; + for (i=1; i<n; i++) { + long p = i; + k = rb_genrand_real()*--len; + retry: + j = 0; + do { + if (idx[j] == k) { + ++k; + if (p < j) goto retry; + } + else if (idx[j] > k) { + if (p > j) p = j; + } + } while (++j < i); + idx[i] = k; } - RARRAY_PTR(result)[i] = nv; - ARY_SET_LEN(result, i+1); + result = rb_ary_new2(n); + for (i=0; i<n; i++) { + RARRAY_PTR(result)[i] = RARRAY_PTR(ary)[idx[i]]; + } } - for (i=0; i<n; i++) { - nv = RARRAY_PTR(result)[i]; - RARRAY_PTR(result)[i] = RARRAY_PTR(ary)[NUM2LONG(nv)]; + else { + result = rb_ary_new4(len, ptr); + RB_GC_GUARD(ary); + for (i=0; i<n; i++) { + j = (long)(rb_genrand_real()*(len-i)) + i; + nv = RARRAY_PTR(result)[j]; + RARRAY_PTR(result)[j] = RARRAY_PTR(result)[i]; + RARRAY_PTR(result)[i] = nv; + } } + return result; } Index: ChangeLog =================================================================== --- ChangeLog (revision 18718) +++ ChangeLog (revision 18719) @@ -1,3 +1,7 @@ +Wed Aug 20 16:39:59 2008 Nobuyoshi Nakada <nobu@r...> + + * array.c (rb_ary_sample): performance improvement for huge array. + Wed Aug 20 12:28:31 2008 Nobuyoshi Nakada <nobu@r...> * array.c (rb_ary_sample): get rid of infinite loop. #455 -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/