Shuffle-Array in C

Lesezeit: 13 Minuten

Benutzeravatar von Asmodiel
Asmodel

Ich suche nach einer Funktion in ANSI C, die ein Array genau wie PHP randomisieren würde shuffle() tut. Gibt es eine solche Funktion oder muss ich sie selbst schreiben? Und wenn ich es selbst schreiben muss, wie mache ich das am besten/performantesten?

Meine Ideen bisher:

  • Durchlaufen Sie das Array beispielsweise 100 Mal und tauschen Sie einen zufälligen Index mit einem anderen zufälligen Index aus
  • Erstellen Sie ein neues Array und füllen Sie es mit zufälligen Indizes aus dem ersten, wobei Sie jedes Mal prüfen, ob der Index bereits vergeben ist (Leistung = 0 Komplexität = ernst)

  • Sie müssen Ihre eigenen schreiben – es ist ziemlich einfach. Sehen en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle. Wie immer, wenn es um Zufallszahlen geht, ist es normalerweise keine gute Idee, eigene Lösungen zu finden,

    Benutzer2100815

    25. Mai 2011 um 16:11 Uhr


  • OK, egal, gefunden >.> benpfaff.org/writings/clc/shuffle.html

    – Asmodell

    25. Mai 2011 um 16:12 Uhr

  • Achten Sie auf die auf der Wikipedia-Seite identifizierte „Modulo-Verzerrung“ – der Ben-Pfaff-Algorithmus weist das Problem auf.

    – Jonathan Leffler

    25. Mai 2011 um 16:41 Uhr

  • Siehe auch stackoverflow.com/questions/859253

    – JC Salomon

    25. Mai 2011 um 19:02 Uhr

  • Dies zeigt, wie man ein Kartenspiel mischt und wie man es nicht macht: encodinghorror.com/blog/2007/12/the-danger-of-naivete.html sollte der Code leicht auf C übertragbar sein

    – Nr

    25. Mai 2011 um 21:02 Uhr

Benutzeravatar von John Leehey
John Leehey

Eingefügt von Asmodiels Link zu Ben Pfaffs Schriftenfür Beständigkeit:

#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;
        }
    }
}

BEARBEITEN: Und hier ist eine generische Version, die für jeden Typ funktioniert (int, struct…) durch memcpy. Wenn ein Beispielprogramm ausgeführt werden soll, sind VLAs erforderlich, nicht jeder Compiler unterstützt dies, daher möchten Sie dies möglicherweise ändern malloc (was schlecht funktioniert) oder ein statischer Puffer, der groß genug ist, um jeden Typ aufzunehmen, den Sie darauf werfen:

#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;
}

  • Um die Allokation von t bei jeder Iteration zu vermeiden, sollten Sie die beiden Integer ohne Temp-Variable tauschen: array[i] ^= Array[j]; Reihe[j] ^= Array [i]; Reihe [i] ^= Array [j];

    – Hyperboreus

    25. Mai 2011 um 16:37 Uhr

  • könntest du auch machen array[i] += array[j]; array[j] = array[i] - array[j]; array[i] -= array[j]; wenn Sie sich keine Sorgen über int-Überläufe machen. Ich möchte jedoch keinen Neuling in der Sprache darüber verwirren, warum XOR’ing funktioniert …

    – John Leehey

    25. Mai 2011 um 16:44 Uhr

  • @Hyperboreus – Machst du Witze? Das „Zuweisen“ von ganzen Zahlen auf dem Stack ist so einfach wie das Ausführen einer Addition/Subtraktion an einem Register. Das selbst wird schnell genug sein, aber darüber hinaus wird ein anständiger Optimierer diese Addition/Subtraktion nur einmal für diesen Code durchführen, nicht für jede Iteration. (Kompilieren Sie dies mit aktivierter Optimierung und sehen Sie sich die Disassemblierung selbst an. Ich habe dies mit gcc -S und es gab genau zwei Modifikationen des Stapelzeigers, einmal am Anfang der Funktion und einmal am Ende.) Gibt es nichts Sie sparen, indem Sie haben t und j Scope früher in der Funktion.

    – asveikau

    25. Mai 2011 um 16:53 Uhr


  • Hinweis: Die Formel i + r / (RAND_MAX / (n - i) + 1) führt zusätzliche Verzerrungen ein. zB j(i=32,n=61,RM=2147483647) –> { mit 2147483648 anders r, j= 32 bis 60 kommt jeweils 74051161 vor, 61 kommt nur 74051140 vor }. TBD schlimmsten Fall i,n,RAND_MAX. Mit i+ rnd%(n-i) { j= 32 bis 39 kommen jeweils 74051161 vor, j = 40 bis 61 tritt 74051160 auf, die ungünstigste Verteilung für verschiedene i,n,RAND_MAX höchstens 1 anders sein. Da sich andere Beiträge auf diese beliebte Antwort beziehen, war es wichtig, diese Voreingenommenheit zu beachten.

    – chux – Wiedereinsetzung von Monica

    26. April 2014 um 16:36 Uhr

  • @PaulStelian: Wenn RAND_MAX nur 32767 ist, müssen Sie sich ein besseres PRNG besorgen. Ein einfacher Schritt nach oben ist die drand48() Familie von Funktionen; das ist ein POSIX-Standardsatz von Funktionen. Sie könnten feststellen, dass Sie haben random() und srandom()oder arc4random()oder vielleicht können Sie verwenden /dev/random oder /dev/urandom als Quelle für Zufallswerte. Es gibt viele Möglichkeiten – aber was Sie fragen, ist wirklich eine neue Frage (oder sollte in einer neuen Frage gestellt werden).

    – Jonathan Leffler

    9. Juni 2018 um 18:15 Uhr

Benutzeravatar von Nomadiq
Nomadiq

Der folgende Code stellt sicher, dass das Array basierend auf einem zufälligen Startwert aus der Usec-Zeit gemischt wird. Auch dies implementiert die Fisher-Yates-Shuffle richtig. Ich habe die Ausgabe dieser Funktion getestet und sie sieht gut aus (sogar die Erwartung, dass jedes Array-Element das erste Element nach dem Mischen ist. Auch die Erwartung, dass es das letzte ist).

void shuffle(int *array, size_t n) {    
    struct timeval tv;
    gettimeofday(&tv, NULL);
    int usec = tv.tv_usec;
    srand48(usec);


    if (n > 1) {
        size_t i;
        for (i = n - 1; i > 0; i--) {
            size_t j = (unsigned int) (drand48()*(i+1));
            int t = array[j];
            array[j] = array[i];
            array[i] = t;
        }
    }
}

  • Ich würde eine verwenden intnicht size_tin diesem Fall weil n stellt die Anzahl der Ints dar, nicht die Größe des Speicherblocks. Ich benutze lieber size_t nur für Größen in Byte.

    – mk12

    6. November 2012 um 18:13 Uhr

  • @Mk12 Die Anzahl der Elemente und die sizeof ein Array kann viel mehr sein als INT_MAX. Verwenden size_t Hier ist ein robusterer und portablerer Ansatz.

    – chux – Wiedereinsetzung von Monica

    26. April 2014 um 16:48 Uhr

  • Schön, so wenig Code. Ist es schnell und einfach, dies mit der C-Bibliothek von Microsoft zum Laufen zu bringen?

    – T. Webster

    13. Mai 2015 um 1:00 Uhr

  • Notiz srand() — Warum Sie es nur einmal anrufen sollten.

    – Jonathan Leffler

    11. Dezember 2016 um 1:05 Uhr

Es gibt keine Funktion im C-Standard, um ein Array zu randomisieren.

  • Schauen Sie sich Knuth an – er hat Algorithmen für den Job.
  • Oder schauen Sie sich Bentley – Programming Pearls oder More Programming Pearls an.
  • Oder schauen Sie in fast jedem Buch über Algorithmen nach.

Das Sicherstellen eines fairen Mischens (bei dem jede Permutation der ursprünglichen Reihenfolge gleich wahrscheinlich ist) ist einfach, aber nicht trivial.

  • Wirklich gleich wahrscheinlich ist sehr schwierig. Zum Beispiel muss Ihr Zufallszahlengenerator ein Vielfaches von N haben! Zustände.

    Benutzer97370

    25. Mai 2011 um 19:14 Uhr

  • @Paul: Solange Ihr PRNG-Wrapper “Zufallszahl zwischen 1 und N” korrekt ist (gleichmäßige Verteilung), ist es einfach. Die Leute vermasseln dies jedoch oft und erzeugen Vorurteile.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    25. Mai 2011 um 20:35 Uhr

  • @Paul Hankin: Liegt das daran, dass Sie Zufallszahlen generieren müssen 0 zu i wo i geht von n zu 1?

    – ninjalj

    25. Mai 2011 um 20:38 Uhr

  • @ninjalj: Nein, absolut nicht. Das ist der naive kaputte Algorithmus, den jeder benutzt. Alles, was Gleitkommazahlen enthält, wird die Hölle sein, es richtig zu machen, also wäre der erste Schritt, es zu beheben, auf Ganzzahlen umzusteigen. Verwerfen Sie dann alle Ergebnisse, die größer als das größte Vielfache von 10 minus 1 sind (call rand erneut, wenn Sie einen Wert erhalten, den Sie verwerfen müssen). Es gibt Möglichkeiten, diese Entropie zu speichern und wiederzuverwenden, anstatt sie vollständig zu verwerfen, aber das ist mehr Arbeit und wahrscheinlich wertlos, wenn es sowieso nur pseudozufällig ist.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    25. Mai 2011 um 20:51 Uhr

  • @R. glibc rand() hat nur 2^32 verschiedene Zustände, also kann es höchstens 2^32 verschiedene Mischungen eines Kartenspiels erzeugen, was auch immer Sie tun. 52! ist eher wie 2^225, also generieren Sie tatsächlich einen winzigen, winzigen Bruchteil aller Möglichkeiten.

    Benutzer97370

    27. Mai 2011 um 19:18 Uhr

Benutzeravatar von JC Salomon
JC Salomon

Ich werde nur die Antwort von Neil Butterworth wiederholen und auf einige Probleme mit Ihrer ersten Idee hinweisen:

Du schlugst vor,

Durchlaufen Sie das Array beispielsweise 100 Mal und tauschen Sie einen zufälligen Index mit einem anderen zufälligen Index aus

Machen Sie dies streng. Ich gehe von der Existenz aus randn(int n)ein Wrapper um einen RNG, der gleichmäßig verteilte Zahlen erzeugt [0, n-1]und swap(int a[], size_t i, size_t j),

void swap(int a[], size_t i, size_t j) {
  int temp = a[i]; a[i] = a[j]; a[j] = temp;
}

was tauscht a[i] und a[j]. Lassen Sie uns nun Ihren Vorschlag umsetzen:

void silly_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, randn(n), randn(n)); // swap two random elements
}

Beachten Sie, dass dies nicht besser ist als diese einfachere (aber immer noch falsche) Version:

void bad_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, i, randn(n));
}

Nun, was ist los? Überlegen Sie, wie viele Permutationen Ihnen diese Funktionen geben: With n (oder 2×_n_ für silly_shuffle) Zufallsauswahl in [0, n-1], wird der Code „ziemlich“ eine von _n_² (oder 2×_n_²) Möglichkeiten auswählen, um das Deck zu mischen. Das Problem ist, dass es sie gibt n! = _n_×(n-1)×⋯×2×1 mögliche Anordnungen des Arrays, und weder _n_² noch 2×_n_² ist ein Vielfaches von n!, was beweist, dass einige Permutationen wahrscheinlicher sind als andere.

Der Fisher-Yates-Shuffle entspricht eigentlich Ihrem zweiten Vorschlag, nur mit einigen Optimierungen, die sich von (Leistung = 0, Komplexität = ernst) zu (Leistung = sehr gut, Komplexität = ziemlich einfach) ändern. (Eigentlich bin ich mir nicht sicher, ob es eine schnellere oder einfachere korrekte Version gibt.)

void fisher_yates_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, i, i+randn(n-1-i)); // swap element with random later element
}

ETA: Siehe auch diesen Beitrag auf Coding Horror.

Die gesuchte Funktion ist bereits in der Standard-C-Bibliothek vorhanden. Sein Name ist qsort. Zufällige Sortierung kann implementiert werden als:

int rand_comparison(const void *a, const void *b)
{
    (void)a; (void)b;

    return rand() % 2 ? +1 : -1;
}

void shuffle(void *base, size_t nmemb, size_t size)
{
    qsort(base, nmemb, size, rand_comparison);
}

Das Beispiel:

int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

srand(0); /* each permutation has its number here */

shuffle(arr, 10, sizeof(int));

… und die Ausgabe ist:

3, 4, 1, 0, 2, 7, 6, 9, 8, 5

  • Garantiert dies, dass alle Permutationen gleich wahrscheinlich sind? Ich denke, das ist unwahrscheinlich. Ein Fisher-Yates-Shuffle garantiert, dass alle Permutationen gleich wahrscheinlich sind, unter der Annahme eines unvoreingenommenen PRNG.

    – Jonathan Leffler

    25. März 2020 um 14:53 Uhr

  • @JonathanLeffler Das ist wahrscheinlich hoffnungslos, da es keine Garantie dafür gibt qsort() Algorithmus und die Qualität von rand() im C-Standard.

    – DaBler

    25. März 2020 um 15:19 Uhr

  • Was nützt (void)a; (void)b;?

    – tejasvi88

    5. November 2021 um 13:12 Uhr

  • @tejasvi88 Dies dient dazu, eine Compiler-Warnung zu vermeiden: warning: unused parameter ‘a’ [-Wunused-parameter]

    – DaBler

    5. November 2021 um 14:15 Uhr

  • C lib spezifiziert „Wenn dieselben Objekte (bestehend aus Größenbytes, unabhängig von ihrer aktuellen Position im Array) mehr als einmal an die Vergleichsfunktion übergeben werden, müssen die Ergebnisse miteinander konsistent sein. Das heißt, für qsort müssen sie definieren eine Gesamtordnung auf dem Array”. Diese Antwort ist rand_comparison() versäumt es, a bereitzustellen Gesamtbestellung ergebend undefiniertes Verhalten einschließlich einer potenziellen Endlosschleife.

    – chux – Wiedereinsetzung von Monica

    10. Juni um 19:57 Uhr


Benutzeravatar von Hyperboreus
Hyperboreus

Hier eine Lösung, die Memcpy anstelle von Zuweisungen verwendet, sodass Sie sie für Arrays über beliebige Daten verwenden können. Sie benötigen doppelt so viel Speicher wie das ursprüngliche Array und die Kosten sind linear O (n):

void main ()
{
    int elesize = sizeof (int);
    int i;
    int r;
    int src [20];
    int tgt [20];

    for (i = 0; i < 20; src [i] = i++);

    srand ( (unsigned int) time (0) );

    for (i = 20; i > 0; i --)
    {
        r = rand () % i;
        memcpy (&tgt [20 - i], &src [r], elesize);
        memcpy (&src [r], &src [i - 1], elesize);
    }
    for (i = 0; i < 20; printf ("%d ", tgt [i++] ) );
}

  • Garantiert dies, dass alle Permutationen gleich wahrscheinlich sind? Ich denke, das ist unwahrscheinlich. Ein Fisher-Yates-Shuffle garantiert, dass alle Permutationen gleich wahrscheinlich sind, unter der Annahme eines unvoreingenommenen PRNG.

    – Jonathan Leffler

    25. März 2020 um 14:53 Uhr

  • @JonathanLeffler Das ist wahrscheinlich hoffnungslos, da es keine Garantie dafür gibt qsort() Algorithmus und die Qualität von rand() im C-Standard.

    – DaBler

    25. März 2020 um 15:19 Uhr

  • Was nützt (void)a; (void)b;?

    – tejasvi88

    5. November 2021 um 13:12 Uhr

  • @tejasvi88 Dies dient dazu, eine Compiler-Warnung zu vermeiden: warning: unused parameter ‘a’ [-Wunused-parameter]

    – DaBler

    5. November 2021 um 14:15 Uhr

  • C lib spezifiziert „Wenn dieselben Objekte (bestehend aus Größenbytes, unabhängig von ihrer aktuellen Position im Array) mehr als einmal an die Vergleichsfunktion übergeben werden, müssen die Ergebnisse miteinander konsistent sein. Das heißt, für qsort müssen sie definieren eine Gesamtordnung auf dem Array”. Diese Antwort ist rand_comparison() versäumt es, a bereitzustellen Gesamtbestellung ergebend undefiniertes Verhalten einschließlich einer potenziellen Endlosschleife.

    – chux – Wiedereinsetzung von Monica

    10. Juni um 19:57 Uhr


Angenommen, Sie möchten nur zufällig auf ein Array zugreifen, anstatt es tatsächlich zu mischen, können Sie den degenerativen Fall eines linearen kongruenten Pseudozufallszahlengenerators verwenden

X_n+1 = (a Xn+c) mod N
wobei a teilerfremd zu N ist
erzeugt einen zufälligen Zyklus über alle Werte 0:N

Natürlich könnten Sie diese Sequenz in einem leeren Array speichern.

uint32_t gcd ( uint32_t a, uint32_t b )
{
  if ( a==0 ) return b;
  return gcd ( b%a, a );
}

 uint32_t get_coprime(uint32_t r){  
     uint32_t min_val = r>>1;  
     for(int i =0;i<r*40;i++){  
         uint64_t sel = min_val + ( rand()%(r-min_val ));  
         if(gcd(sel,r)==1)  
             return sel;  
     }  
     return 0;  
}

uint32_t next_val(uint32_t coprime, uint32_t cur, uint32_t N)
{     
   return (cur+coprime)%N;   
}


// Example output Array A in random order
void shuffle(float * A, uint32_t N){
  uint32_t coprime = get_coprime(N);
  cur = rand()%N;
  for(uint32_t i = 0;i<N;i++){
     printf("%f\n",A[cur]);
     cur = next_val(coprime, cur, N);
}

  • Ich bin verwirrt über die Verweise auf r in get_coprime() — sollten sie Verweise auf sein N? Benötigen Sie auch keine Modulo-Operation in next_val() um zu verhindern, dass Werte außerhalb des Bereichs liegen? Oder muss man verwenden next = next_val(coprime, next) % N;?

    – Jonathan Leffler

    13. Juni um 15:38 Uhr


  • Sie sollten wahrscheinlich zeigen, wie der Code verwendet werden würde. Es scheint mir wahrscheinlich, dass die gcd() Die Funktion sollte statisch sein. Vermutlich sind die Operationen ähnlich wie: uint32_t cp = get_coprime(N); uint32_t first = rand() % N; uint32_t cur = first; do { …use array[cur]…; cur = next_val(cp, cur); } while (cur != first);.

    – Jonathan Leffler

    13. Juni um 15:38 Uhr

1409550cookie-checkShuffle-Array in C

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy