KEEP K.I.S.S.

tk's blog

Ruby 中的 Array Shuffle 算法

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

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

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

?
1
(1..12).to_a.shuffle

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

其实现如下：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 写个示例如下：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}

C shuffle 洗牌算法 Comments(2) 13 年前