在C中随机化通用数组 [英] Shuffle generic array in C

问题描述

我有一个指向结构的指针数组。

我试图用这个问题的第一个答案来解决这个问题，但是我得到了一个句段错误：

C语言中的Shuffle数组

尝试此代码后，我尝试使用此功能进行混洗：

  static void shuffle（void * array，size_t n，size_t size）{
 void * aux; 
 aux = malloc（大小）; 
 
 if（n> 1）{
 size_t i; 
 for（i = 0; i< n-1; ++ i）{
 
 size_t j = i + rand（）/（RAND_MAX /（n-i）+ 1） ; 
 
 memcpy（aux，array [j]，size）; 
 memcpy（array [j]，array [i]，size）; 
 memcpy（array [i]，aux，size）; 
} 
} 
} 
  

但是我遇到了以下错误：

 警告：取消引用'void *'指针[默认启用] 
错误：无效使用void表达式
  

我收到此警告和错误3次：每个memcpy（）一次。

编辑

我更改了代码，因为我试图使用新的而不是旧的。

解决方案

除了@Deduplicator好的建议，还需要将 j 的偏移量缩放为 size 。

此代码还更改了 j 的计算。我不认为您所拥有的会很好。

  #include< stdlib.h> 
 static void shuffle（void * array，size_t n，size_t size）{
 //此if（）在功能上不是必需的，而是按照OP的样式保留
 if（n> 1） {
 char * carray = array; 
 void * aux; 
 aux = malloc（size）; 
 size_t i; 
 for（i = 1; i  size_t j = rand（）％（i + 1）; 
 j * =大小； 
 memcpy（aux，& carray [j]，size）; 
 memcpy（& carray [j]，& carray [i * size]，size）; 
 memcpy（& carray [i * size]，aux，size）; 
} 
 free（aux）; 
} 
} 
  

---

阐明 size_t j = i + rand（）/（RAND_MAX /（n-i）+1）;

的弱点

将值 0 的 rand（）替换为 RAND_MAX 将生成样本分布。示例（i = 0，n = 30265，RAND_MAX = 2147483647）生成值 j = 0到30263 ，分别为70957次和 j = 30264 =41000。这是一个坏情况，可能不是最坏的情况。

使用 size_t j = i + r％ （ni）; 生成几乎统一结果。

示例（i = 0，n = 30265，RAND_MAX = 2147483647）生成值 j = 0至307 ，每个值70957次，而 j = 308至30264 = 70956次。存在补偿这种小的偏差的方法。许多SO帖子。

注意：这两种方法都不能解决 rand（）的继承弱点，但是当尝试使用 0 到 RAND_MAX

孔出现 size_t j = i + rand（）/（RAND_MAX /（n-i）+ 1）;

大约 n> sqrt（RAND_MAX）和 i = 0 ，将不会生成 n 附近的值。例如：（i = 0，n = 104643，RAND_MAX = 2147483647）不会生成值104638至104642。

I have an array of pointer to a struct.

I tried to use the first answer of this question to try to solve this problem, but I got a seg fault:

Shuffle array in C

After try this code, I tryed to use this function to do the shuffling:

static void shuffle(void *array, size_t n, size_t size) {
    void * aux;
    aux = malloc (size);

    if (n > 1) {
        size_t i;
        for (i = 0; i < n - 1; ++i) {

            size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

            memcpy(aux, array[j], size);
            memcpy(array[j], array[i], size);
            memcpy(array[i], aux, size);
        }
    }
}

But i got the following error:

warning: dereferencing 'void *' pointer [enable by default]
error: invalid use of void expression

I got this warning and error 3 times: one for each memcpy().

EDIT

I changed the code because I was trying to use this new one instead the old one.

解决方案

In addition to @Deduplicator good advice, need to scale the j offset by size.

This code also changes the j calculation. I do not think what you have will work well.

#include <stdlib.h>
static void shuffle(void *array, size_t n, size_t size) {
  // This if() is not needed functionally, but left per OP's style
  if (n > 1) {
    char *carray = array;
    void * aux;
    aux = malloc(size);
    size_t i;
    for (i = 1; i < n; ++i) {
      size_t j = rand() % (i + 1); 
      j *= size;
      memcpy(aux, &carray[j], size);
      memcpy(&carray[j], &carray[i*size], size);
      memcpy(&carray[i*size], aux, size);
    }
    free(aux);
  }
}

---

Clarify the weakness of size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

Substituting rand() with the values 0 to RAND_MAX in the formula will generate a sample distribution. Example (i=0, n=30265, RAND_MAX=2147483647) generates the values j = 0 to 30263, 70957 times each and j = 30264= 41000. This is a bad case and likely not the worst case.

Using size_t j = i + r%(n-i); generates a nearly uniform result.

Example (i=0, n=30265, RAND_MAX=2147483647) generates the values j = 0 to 307, 70957 times each and j = 308 to 30264= 70956 times. Methods exist to compensate for this small bias. Many SO postings.

Note: Inherit weaknesses in a poor rand() are not fixed by either of these methods, but method selection can make things noticeably worse when trying to use a sub-range of 0 to RAND_MAX

[Edit]

Holes appear with size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

Somewhere about n > sqrt(RAND_MAX) and i=0, values near n will not be generated. Example: (i=0, n=104643, RAND_MAX=2147483647) does not generate values 104638 to 104642.

这篇关于在C中随机化通用数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！