C 中的随机数组 [英] Shuffle array in C
问题描述
我正在 ANSI C 中寻找一个函数,它可以像 PHP 的 shuffle()
那样随机化一个数组.有没有这样的功能还是必须自己写?如果我必须自己编写它,最好/最高效的方法是什么?
I'm looking for a function in ANSI C that would randomize an array just like PHP's shuffle()
does. Is there such a function or do I have to write it on my own? And if I have to write it on my own, what's the best/most performant way to do it?
我目前的想法:
- 遍历数组,例如 100 次,然后将一个随机索引与另一个随机索引交换
- 创建一个新数组并用第一个数组中的随机索引填充它,每次检查索引是否已经被占用(性能 = 0 复杂性 = 严重)
推荐答案
粘贴自 Asmodiel 的 链接到Ben Pfaff 的著作,为了坚持:
Pasted from Asmodiel's link to Ben Pfaff's Writings, for persistence:
#include <stdlib.h>
/* Arrange the N elements of ARRAY in random order.
Only effective if N is much smaller than RAND_MAX;
if this may not be the case, use a better random
number generator. */
void shuffle(int *array, size_t n)
{
if (n > 1)
{
size_t i;
for (i = 0; i < n - 1; i++)
{
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
}
EDIT:这是一个通用版本,适用于通过 memcpy 的任何类型(
int
、struct
、...)代码>.要运行示例程序,它需要 VLA,并非每个编译器都支持此功能,因此您可能希望将其更改为 malloc
(这将导致性能不佳)或足够大的静态缓冲区以容纳您抛出的任何类型在它:
EDIT: And here's a generic version that works for any type (int
, struct
, ...) through memcpy
. With an example program to run, it requires VLAs, not every compiler supports this so you might want to change that to malloc
(which will perform badly) or a static buffer large enough to accommodate any type you throw at it:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* compile and run with
* cc shuffle.c -o shuffle && ./shuffle */
#define NELEMS(x) (sizeof(x) / sizeof(x[0]))
/* arrange the N elements of ARRAY in random order.
* Only effective if N is much smaller than RAND_MAX;
* if this may not be the case, use a better random
* number generator. */
static void shuffle(void *array, size_t n, size_t size) {
char tmp[size];
char *arr = array;
size_t stride = size * sizeof(char);
if (n > 1) {
size_t i;
for (i = 0; i < n - 1; ++i) {
size_t rnd = (size_t) rand();
size_t j = i + rnd / (RAND_MAX / (n - i) + 1);
memcpy(tmp, arr + j * stride, size);
memcpy(arr + j * stride, arr + i * stride, size);
memcpy(arr + i * stride, tmp, size);
}
}
}
#define print_type(count, stmt) \
do { \
printf("["); \
for (size_t i = 0; i < (count); ++i) { \
stmt; \
} \
printf("]\n"); \
} while (0)
struct cmplex {
int foo;
double bar;
};
int main() {
srand(time(NULL));
int intarr[] = { 1, -5, 7, 3, 20, 2 };
print_type(NELEMS(intarr), printf("%d,", intarr[i]));
shuffle(intarr, NELEMS(intarr), sizeof(intarr[0]));
print_type(NELEMS(intarr), printf("%d,", intarr[i]));
struct cmplex cmparr[] = {
{ 1, 3.14 },
{ 5, 7.12 },
{ 9, 8.94 },
{ 20, 1.84 }
};
print_type(NELEMS(intarr), printf("{%d %f},", cmparr[i].foo, cmparr[i].bar));
shuffle(cmparr, NELEMS(cmparr), sizeof(cmparr[0]));
print_type(NELEMS(intarr), printf("{%d %f},", cmparr[i].foo, cmparr[i].bar));
return 0;
}
这篇关于C 中的随机数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!