Какой алгоритм случайности использует выборка Array #?

Question

Я пытаюсь выяснить, какой случайный алгоритм Array#sample использует, но я немного теряюсь в поиске кода Ruby C.

Answer 1

Я считаю полезным покопаться в pry, чтобы изучить реальный исходный код, хотя вы также можете найти его, перейдя к Ruby Docs и наведя курсор на имена методов, чтобы открыть click to toggle source с увеличительным стеклом, которое также покажу вам тот же исходный код, который вы можете найти здесь, в pry, если вы сделали gem install pry-doc

arr = []
cd arr
show-method sample

(#<Array>):1> show-method sample

From: array.c (C Method):
Owner: Array
Visibility: public
Number of lines: 103

static VALUE
rb_ary_sample(int argc, VALUE *argv, VALUE ary)
{
    VALUE nv, result;
    VALUE opts, randgen = rb_cRandom;
    long n, len, i, j, k, idx[10];
    long rnds[numberof(idx)];

    if (OPTHASH_GIVEN_P(opts)) {
        VALUE rnd;
        ID keyword_ids[1];

        keyword_ids[0] = id_random;
        rb_get_kwargs(opts, keyword_ids, 0, 1, &rnd);
        if (rnd != Qundef) {
            randgen = rnd;
        }
    }
    len = RARRAY_LEN(ary);
    if (argc == 0) {
        if (len < 2)
            i = 0;
        else
            i = RAND_UPTO(len);

        return rb_ary_elt(ary, i);
    }
    rb_scan_args(argc, argv, "1", &nv);
    n = NUM2LONG(nv);
    if (n < 0) rb_raise(rb_eArgError, "negative sample number");
    if (n > len) n = len;
    if (n <= numberof(idx)) {
        for (i = 0; i < n; ++i) {
            rnds[i] = RAND_UPTO(len - i);
        }
    }
    k = len;
    len = RARRAY_LEN(ary);
    if (len < k && n <= numberof(idx)) {
        for (i = 0; i < n; ++i) {
            if (rnds[i] >= len) return rb_ary_new_capa(0);
        }
    }
    if (n > len) n = len;
    switch (n) {
      case 0:
        return rb_ary_new_capa(0);
      case 1:
        i = rnds[0];
        return rb_ary_new_from_values(1, &RARRAY_AREF(ary, i));
      case 2:
        i = rnds[0];
        j = rnds[1];
        if (j >= i) j++;
        return rb_ary_new_from_args(2, RARRAY_AREF(ary, i), RARRAY_AREF(ary, j));
      case 3:
        i = rnds[0];
        j = rnds[1];
        k = rnds[2];
        {
            long l = j, g = i;
            if (j >= i) l = i, g = ++j;
            if (k >= l && (++k >= g)) ++k;
        }
        return rb_ary_new_from_args(3, RARRAY_AREF(ary, i), RARRAY_AREF(ary, j), RARRAY_AREF(ary, k));
    }
    if (n <= numberof(idx)) {
        long sorted[numberof(idx)];
        sorted[0] = idx[0] = rnds[0];
        for (i=1; i<n; i++) {
            k = rnds[i];
            for (j = 0; j < i; ++j) {
                if (k < sorted[j]) break;
                ++k;
            }
            memmove(&sorted[j+1], &sorted[j], sizeof(sorted[0])*(i-j));
            sorted[j] = idx[i] = k;
        }
        result = rb_ary_new_capa(n);
        RARRAY_PTR_USE(result, ptr_result, {
            for (i=0; i<n; i++) {
                ptr_result[i] = RARRAY_AREF(ary, idx[i]);
            }
        });
    }
    else {
        result = rb_ary_dup(ary);
        RBASIC_CLEAR_CLASS(result);
        RB_GC_GUARD(ary);
        RARRAY_PTR_USE(result, ptr_result, {
            for (i=0; i<n; i++) {
                j = RAND_UPTO(len-i) + i;
                nv = ptr_result[j];
                ptr_result[j] = ptr_result[i];
                ptr_result[i] = nv;
            }
        });
        RBASIC_SET_CLASS_RAW(result, rb_cArray);
    }
    ARY_SET_LEN(result, n);

    return result;
}

Итак, мы можем видеть

    VALUE opts, randgen = rb_cRandom;

Это указывает на то, что для случайности используется случайный класс ruby.

Один только код не расскажет нам много об алгоритме

Так что поиск https://ruby -doc.org / core-2.5.0 / Random.html говорит нам, что он использует

PRNG в настоящее время реализованы в виде модифицированного Mersenne Twister с периодом 2 ** 19937-1.

И какого черта это Mersenne Twister? Я не знаю, но это звучит круто, поэтому https://en.wikipedia.org/wiki/Mersenne_Twister говорит нам об этом и о том, что он широко используется:

Mersenne Twister является PRNG по умолчанию для следующих программных систем: Microsoft Excel, [3] GAUSS, [4] GLib, [5] GNU Multi-Precision Arithmetic Library, [6] GNU Octave, [7] Научная библиотека GNU , [8] gretl, [9] IDL, [10] Джулия, [11] CMU Common Lisp, [12] Embeddable Common Lisp, [13] Steel Bank Common Lisp, [14] Maple, [15] MATLAB, [16 ] Free Pascal, [17] PHP, [18] Python, [19] [20] R, [21] Ruby, [22] SageMath, [23] Scilab, [24] Stata. [25]