KEEP K.I.S.S.

tk's blog

Ruby 中的 Array Shuffle 算法

其实就是数组的洗牌算法,洗牌算法主要是生成一组互不相同的伪随机数列,可用于随机排序等等。

如果单纯依赖 C 库的 rand 去生成随机数来做的话,容易发生碰撞,尤其在需要生成的数列个数比较大的情况下。

Ruby 的 Array 有一个 shuffle 的方法,用于生成随机排序的元素新数组:

(1..12).to_a.shuffle 

=> [12, 9, 6, 5, 3, 1, 8, 4, 11, 7, 10, 2]

其实现如下:

static VALUE
rb_ary_shuffle_bang(VALUE ary)
{
    VALUE *ptr;
    long i = RARRAY_LEN(ary);
    rb_ary_modify(ary);
    ptr = RARRAY_PTR(ary);
    while (i) {
        long j = (long)(rb_genrand_real()*i);
        VALUE tmp = ptr[--i];
        ptr[i] = ptr[j];
        ptr[j] = tmp;
    }
    return ary;
} 

很简单,用 C 写个示例如下:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define ARRAY_SIZE(a)  ((sizeof(a) / sizeof(*(a))))

static void
shuffle(int *arr, size_t len)
{
    int i;
    i = len;
    while (i) {
        size_t j = (size_t)(rand() % i);
        i--;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;       
    }
}

int main(int argc, char *argv[])
{
    int array[] = {
        1, 2, 3, 4, 5, 6,
        7, 8, 9, 10, 11, 12
    };
    srand(time(NULL));
    shuffle(array, ARRAY_SIZE(array));
    for (int i = 0; i < ARRAY_SIZE(array); i++) {
        printf("%d, ", array[i]);
    }
    printf("\n");
    return 0;
}