Feature #3647 ยป array_sample_shuffle.patch
| array.c | ||
|---|---|---|
| 3732 | 3732 | |
| 3733 | 3733 |
/* |
| 3734 | 3734 |
* call-seq: |
| 3735 |
* ary.shuffle! -> ary |
|
| 3735 |
* ary.shuffle! -> ary |
|
| 3736 |
* ary.shuffle!(random: RANDOM) -> ary |
|
| 3736 | 3737 |
* |
| 3737 | 3738 |
* Shuffles elements in +self+ in place. |
| 3739 |
* Unless an Random object is passed with :random keyword, |
|
| 3740 |
* use default random number generator. |
|
| 3738 | 3741 |
*/ |
| 3739 | 3742 | |
| 3740 | 3743 | |
| 3741 | 3744 |
static VALUE |
| 3742 |
rb_ary_shuffle_bang(VALUE ary) |
|
| 3745 |
rb_ary_shuffle_bang(int argc, VALUE* argv, VALUE ary)
|
|
| 3743 | 3746 |
{
|
| 3744 | 3747 |
VALUE *ptr; |
| 3748 |
VALUE opt, random = Qnil; |
|
| 3745 | 3749 |
long i = RARRAY_LEN(ary); |
| 3746 | 3750 | |
| 3751 |
if (argc > 0 && !NIL_P(opt = rb_check_hash_type(argv[argc-1]))) {
|
|
| 3752 |
--argc; |
|
| 3753 |
random = rb_hash_aref(opt, ID2SYM(rb_intern("random")));
|
|
| 3754 |
} |
|
| 3755 |
if (NIL_P(random)) {
|
|
| 3756 |
random = rb_const_get_at(rb_cRandom, rb_intern("DEFAULT"));
|
|
| 3757 |
} |
|
| 3747 | 3758 |
rb_ary_modify(ary); |
| 3748 | 3759 |
ptr = RARRAY_PTR(ary); |
| 3749 | 3760 |
while (i) {
|
| 3750 |
long j = (long)(rb_genrand_real()*i);
|
|
| 3761 |
long j = (long)(rb_random_real(random)*(i));
|
|
| 3751 | 3762 |
VALUE tmp = ptr[--i]; |
| 3752 | 3763 |
ptr[i] = ptr[j]; |
| 3753 | 3764 |
ptr[j] = tmp; |
| ... | ... | |
| 3767 | 3778 |
*/ |
| 3768 | 3779 | |
| 3769 | 3780 |
static VALUE |
| 3770 |
rb_ary_shuffle(VALUE ary) |
|
| 3781 |
rb_ary_shuffle(int argc, VALUE* argv, VALUE ary)
|
|
| 3771 | 3782 |
{
|
| 3772 | 3783 |
ary = rb_ary_dup(ary); |
| 3773 |
rb_ary_shuffle_bang(ary); |
|
| 3784 |
rb_ary_shuffle_bang(argc, argv, ary);
|
|
| 3774 | 3785 |
return ary; |
| 3775 | 3786 |
} |
| 3776 | 3787 | |
| ... | ... | |
| 3793 | 3804 |
rb_ary_sample(int argc, VALUE *argv, VALUE ary) |
| 3794 | 3805 |
{
|
| 3795 | 3806 |
VALUE nv, result, *ptr; |
| 3807 |
VALUE opt, replace = Qnil, random = Qnil; |
|
| 3796 | 3808 |
long n, len, i, j, k, idx[10]; |
| 3809 |
#define RAND_UPTO(n) (long)(rb_random_real(random)*(n)) |
|
| 3797 | 3810 | |
| 3798 | 3811 |
len = RARRAY_LEN(ary); |
| 3812 |
if (argc > 0 && !NIL_P(opt = rb_check_hash_type(argv[argc-1]))) {
|
|
| 3813 |
--argc; |
|
| 3814 |
replace = rb_hash_aref(opt, ID2SYM(rb_intern("replace")));
|
|
| 3815 |
random = rb_hash_aref(opt, ID2SYM(rb_intern("random")));
|
|
| 3816 |
} |
|
| 3817 |
if (NIL_P(random)) {
|
|
| 3818 |
random = rb_const_get_at(rb_cRandom, rb_intern("DEFAULT"));
|
|
| 3819 |
} |
|
| 3799 | 3820 |
if (argc == 0) {
|
| 3800 | 3821 |
if (len == 0) return Qnil; |
| 3801 |
i = len == 1 ? 0 : (long)(rb_genrand_real()*len);
|
|
| 3822 |
i = len == 1 ? 0 : RAND_UPTO(len);
|
|
| 3802 | 3823 |
return RARRAY_PTR(ary)[i]; |
| 3803 | 3824 |
} |
| 3804 | 3825 |
rb_scan_args(argc, argv, "1", &nv); |
| ... | ... | |
| 3806 | 3827 |
if (n < 0) rb_raise(rb_eArgError, "negative sample number"); |
| 3807 | 3828 |
ptr = RARRAY_PTR(ary); |
| 3808 | 3829 |
len = RARRAY_LEN(ary); |
| 3830 |
RB_GC_GUARD(ary); |
|
| 3831 |
if (RTEST(replace)) {
|
|
| 3832 |
result = rb_ary_new2(n); |
|
| 3833 |
while (n-- > 0) {
|
|
| 3834 |
rb_ary_push(result, ptr[RAND_UPTO(len)]); |
|
| 3835 |
} |
|
| 3836 |
return result; |
|
| 3837 |
} |
|
| 3809 | 3838 |
if (n > len) n = len; |
| 3810 | 3839 |
switch (n) {
|
| 3811 | 3840 |
case 0: return rb_ary_new2(0); |
| 3812 | 3841 |
case 1: |
| 3813 |
return rb_ary_new4(1, &ptr[(long)(rb_genrand_real()*len)]);
|
|
| 3842 |
return rb_ary_new4(1, &ptr[RAND_UPTO(len)]);
|
|
| 3814 | 3843 |
case 2: |
| 3815 |
i = (long)(rb_genrand_real()*len);
|
|
| 3816 |
j = (long)(rb_genrand_real()*(len-1));
|
|
| 3844 |
i = RAND_UPTO(len);
|
|
| 3845 |
j = RAND_UPTO(len-1);
|
|
| 3817 | 3846 |
if (j >= i) j++; |
| 3818 | 3847 |
return rb_ary_new3(2, ptr[i], ptr[j]); |
| 3819 | 3848 |
case 3: |
| 3820 |
i = (long)(rb_genrand_real()*len);
|
|
| 3821 |
j = (long)(rb_genrand_real()*(len-1));
|
|
| 3822 |
k = (long)(rb_genrand_real()*(len-2));
|
|
| 3849 |
i = RAND_UPTO(len);
|
|
| 3850 |
j = RAND_UPTO(len-1);
|
|
| 3851 |
k = RAND_UPTO(len-2);
|
|
| 3823 | 3852 |
{
|
| 3824 | 3853 |
long l = j, g = i; |
| 3825 | 3854 |
if (j >= i) l = i, g = ++j; |
| ... | ... | |
| 3830 | 3859 |
if ((size_t)n < sizeof(idx)/sizeof(idx[0])) {
|
| 3831 | 3860 |
VALUE *ptr_result; |
| 3832 | 3861 |
long sorted[sizeof(idx)/sizeof(idx[0])]; |
| 3833 |
sorted[0] = idx[0] = (long)(rb_genrand_real()*len);
|
|
| 3862 |
sorted[0] = idx[0] = RAND_UPTO(len);
|
|
| 3834 | 3863 |
for (i=1; i<n; i++) {
|
| 3835 |
k = (long)(rb_genrand_real()*--len);
|
|
| 3864 |
k = RAND_UPTO(--len);
|
|
| 3836 | 3865 |
for (j = 0; j < i; ++j) {
|
| 3837 | 3866 |
if (k < sorted[j]) break; |
| 3838 | 3867 |
++k; |
| ... | ... | |
| 3852 | 3881 |
ptr_result = RARRAY_PTR(result); |
| 3853 | 3882 |
RB_GC_GUARD(ary); |
| 3854 | 3883 |
for (i=0; i<n; i++) {
|
| 3855 |
j = (long)(rb_genrand_real()*(len-i)) + i;
|
|
| 3884 |
j = RAND_UPTO(len-i) + i;
|
|
| 3856 | 3885 |
nv = ptr_result[j]; |
| 3857 | 3886 |
ptr_result[j] = ptr_result[i]; |
| 3858 | 3887 |
ptr_result[i] = nv; |
| ... | ... | |
| 3861 | 3890 |
ARY_SET_LEN(result, n); |
| 3862 | 3891 | |
| 3863 | 3892 |
return result; |
| 3893 |
#undef RAND_UPTO |
|
| 3864 | 3894 |
} |
| 3865 | 3895 | |
| 3866 | 3896 | |
| ... | ... | |
| 4593 | 4623 |
rb_define_method(rb_cArray, "flatten", rb_ary_flatten, -1); |
| 4594 | 4624 |
rb_define_method(rb_cArray, "flatten!", rb_ary_flatten_bang, -1); |
| 4595 | 4625 |
rb_define_method(rb_cArray, "count", rb_ary_count, -1); |
| 4596 |
rb_define_method(rb_cArray, "shuffle!", rb_ary_shuffle_bang, 0);
|
|
| 4597 |
rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, 0);
|
|
| 4626 |
rb_define_method(rb_cArray, "shuffle!", rb_ary_shuffle_bang, -1);
|
|
| 4627 |
rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, -1);
|
|
| 4598 | 4628 |
rb_define_method(rb_cArray, "sample", rb_ary_sample, -1); |
| 4599 | 4629 |
rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -1); |
| 4600 | 4630 |
rb_define_method(rb_cArray, "permutation", rb_ary_permutation, -1); |
| hash.c | ||
|---|---|---|
| 418 | 418 |
return rb_convert_type(hash, T_HASH, "Hash", "to_hash"); |
| 419 | 419 |
} |
| 420 | 420 | |
| 421 |
VALUE |
|
| 422 |
rb_check_hash_type(VALUE hash) |
|
| 423 |
{
|
|
| 424 |
return rb_check_convert_type(hash, T_HASH, "Hash", "to_hash"); |
|
| 425 |
} |
|
| 426 | ||
| 421 | 427 |
/* |
| 422 | 428 |
* call-seq: |
| 423 | 429 |
* Hash.try_convert(obj) -> hash or nil |
| ... | ... | |
| 432 | 438 |
static VALUE |
| 433 | 439 |
rb_hash_s_try_convert(VALUE dummy, VALUE hash) |
| 434 | 440 |
{
|
| 435 |
return rb_check_convert_type(hash, T_HASH, "Hash", "to_hash");
|
|
| 441 |
return rb_check_hash_type(hash);
|
|
| 436 | 442 |
} |
| 437 | 443 | |
| 438 | 444 |
static int |
| include/ruby/intern.h | ||
|---|---|---|
| 406 | 406 |
#define Init_stack(addr) ruby_init_stack(addr) |
| 407 | 407 |
/* hash.c */ |
| 408 | 408 |
void st_foreach_safe(struct st_table *, int (*)(ANYARGS), st_data_t); |
| 409 |
VALUE rb_check_hash_type(VALUE); |
|
| 409 | 410 |
void rb_hash_foreach(VALUE, int (*)(ANYARGS), VALUE); |
| 410 | 411 |
VALUE rb_hash(VALUE); |
| 411 | 412 |
VALUE rb_hash_new(void); |
| random.c | ||
|---|---|---|
| 329 | 329 |
rb_gc_mark(((rb_random_t *)ptr)->seed); |
| 330 | 330 |
} |
| 331 | 331 | |
| 332 |
#define random_free RUBY_TYPED_DEFAULT_FREE |
|
| 332 |
static void |
|
| 333 |
random_free(void *ptr) |
|
| 334 |
{
|
|
| 335 |
if (ptr != &default_rand) |
|
| 336 |
xfree(ptr); |
|
| 337 |
} |
|
| 333 | 338 | |
| 334 | 339 |
static size_t |
| 335 | 340 |
random_memsize(const void *ptr) |
| ... | ... | |
| 1232 | 1237 |
rb_define_private_method(rb_cRandom, "state", random_state, 0); |
| 1233 | 1238 |
rb_define_private_method(rb_cRandom, "left", random_left, 0); |
| 1234 | 1239 |
rb_define_method(rb_cRandom, "==", random_equal, 1); |
| 1240 |
rb_define_const(rb_cRandom, "DEFAULT", |
|
| 1241 |
TypedData_Wrap_Struct(rb_cRandom, &random_data_type, &default_rand)); |
|
| 1235 | 1242 | |
| 1236 | 1243 |
rb_define_singleton_method(rb_cRandom, "srand", rb_f_srand, -1); |
| 1237 | 1244 |
rb_define_singleton_method(rb_cRandom, "rand", rb_f_rand, -1); |
| test/ruby/test_array.rb | ||
|---|---|---|
| 1878 | 1878 |
100.times do |
| 1879 | 1879 |
assert_equal([0, 1, 2], [2, 1, 0].shuffle.sort) |
| 1880 | 1880 |
end |
| 1881 | ||
| 1882 |
gen = Random.new(0) |
|
| 1883 |
srand(0) |
|
| 1884 |
100.times do |
|
| 1885 |
assert_equal([0, 1, 2].shuffle, [0, 1, 2].shuffle(random: gen)) |
|
| 1886 |
end |
|
| 1881 | 1887 |
end |
| 1882 | 1888 | |
| 1883 | 1889 |
def test_sample |
| ... | ... | |
| 1894 | 1900 |
(0..20).each do |n| |
| 1895 | 1901 |
100.times do |
| 1896 | 1902 |
b = a.sample(n) |
| 1897 |
assert_equal([n, 18].min, b.uniq.size)
|
|
| 1903 |
assert_equal([n, 18].min, b.size) |
|
| 1898 | 1904 |
assert_equal(a, (a | b).sort) |
| 1899 | 1905 |
assert_equal(b.sort, (a & b).sort) |
| 1900 | 1906 |
end |
| ... | ... | |
| 1907 | 1913 |
end |
| 1908 | 1914 | |
| 1909 | 1915 |
assert_raise(ArgumentError, '[ruby-core:23374]') {[1, 2].sample(-1)}
|
| 1916 | ||
| 1917 |
gen = Random.new(0) |
|
| 1918 |
srand(0) |
|
| 1919 |
a = (1..18).to_a |
|
| 1920 |
(0..20).each do |n| |
|
| 1921 |
100.times do |
|
| 1922 |
assert_equal(a.sample(n), a.sample(n, random: gen)) |
|
| 1923 |
end |
|
| 1924 |
end |
|
| 1925 |
end |
|
| 1926 | ||
| 1927 |
def test_sample_without_replace |
|
| 1928 |
100.times do |
|
| 1929 |
samples = [2, 1, 0].sample(2, replace: false) |
|
| 1930 |
samples.each{|sample|
|
|
| 1931 |
assert([0, 1, 2].include?(sample)) |
|
| 1932 |
} |
|
| 1933 |
end |
|
| 1934 | ||
| 1935 |
srand(0) |
|
| 1936 |
a = (1..18).to_a |
|
| 1937 |
(0..20).each do |n| |
|
| 1938 |
100.times do |
|
| 1939 |
b = a.sample(n, replace: false) |
|
| 1940 |
assert_equal([n, 18].min, b.size) |
|
| 1941 |
assert_equal(a, (a | b).sort) |
|
| 1942 |
assert_equal(b.sort, (a & b).sort) |
|
| 1943 |
end |
|
| 1944 | ||
| 1945 |
h = Hash.new(0) |
|
| 1946 |
1000.times do |
|
| 1947 |
a.sample(n, replace: false).each {|x| h[x] += 1 }
|
|
| 1948 |
end |
|
| 1949 |
assert_operator(h.values.min * 2, :>=, h.values.max) if n != 0 |
|
| 1950 |
end |
|
| 1951 | ||
| 1952 |
assert_raise(ArgumentError, '[ruby-core:23374]') {[1, 2].sample(-1, replace: false)}
|
|
| 1953 | ||
| 1954 |
gen = Random.new(0) |
|
| 1955 |
srand(0) |
|
| 1956 |
a = (1..18).to_a |
|
| 1957 |
(0..20).each do |n| |
|
| 1958 |
100.times do |
|
| 1959 |
assert_equal(a.sample(n, replace: false), a.sample(n, replace: false, random: gen)) |
|
| 1960 |
end |
|
| 1961 |
end |
|
| 1962 |
end |
|
| 1963 | ||
| 1964 |
def test_sample_with_replace |
|
| 1965 |
100.times do |
|
| 1966 |
samples = [2, 1, 0].sample(2, replace: true) |
|
| 1967 |
samples.each{|sample|
|
|
| 1968 |
assert([0, 1, 2].include?(sample)) |
|
| 1969 |
} |
|
| 1970 |
end |
|
| 1971 | ||
| 1972 |
srand(0) |
|
| 1973 |
a = (1..18).to_a |
|
| 1974 |
(0..20).each do |n| |
|
| 1975 |
100.times do |
|
| 1976 |
b = a.sample(n, replace: true) |
|
| 1977 |
assert_equal(n, b.size) |
|
| 1978 |
assert_equal(a, (a | b).sort) |
|
| 1979 |
assert_equal(b.sort.uniq, (a & b).sort) |
|
| 1980 |
end |
|
| 1981 | ||
| 1982 |
h = Hash.new(0) |
|
| 1983 |
1000.times do |
|
| 1984 |
a.sample(n, replace: true).each {|x| h[x] += 1 }
|
|
| 1985 |
end |
|
| 1986 |
assert_operator(h.values.min * 2, :>=, h.values.max) if n != 0 |
|
| 1987 |
end |
|
| 1988 | ||
| 1989 |
assert_raise(ArgumentError, '[ruby-core:23374]') {[1, 2].sample(-1, replace: true)}
|
|
| 1990 | ||
| 1991 |
gen = Random.new(0) |
|
| 1992 |
srand(0) |
|
| 1993 |
a = (1..18).to_a |
|
| 1994 |
(0..20).each do |n| |
|
| 1995 |
100.times do |
|
| 1996 |
assert_equal(a.sample(n, replace: true), a.sample(n, replace: true, random: gen)) |
|
| 1997 |
end |
|
| 1998 |
end |
|
| 1910 | 1999 |
end |
| 1911 | 2000 | |
| 1912 | 2001 |
def test_cycle |