random_shuffle würfelt Array immer gleich aus!- Hilfe

Hi,

da unbekannt ist welche Funktion zum Initionalisieren des Zufallszahlengenerators (srand oder srand48) von der STL aufgerufen wird, würde ich ein Versuch mit srand48 wagen.

Grüße
Martin

hustbaer

So zum Beispiel:

struct rng
{
	size_t operator () (size_t n)
	{
		if(n <= 1)
			return 0;
		else
			return rand() % n;
	}
};

void foo()
{
	std::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);

	rng r;

	std::random_shuffle(v.begin(), v.end(), r);
}

Is keine gute Implementierung (% n liefert bei LC Generatoren keine guten Ergebnisse), aber naja.
Der Funktor muss halt einen Parameter N nehmen, und eine Zahl [0, N) zurückgeben, also von 0 bis (N-1) inklusive.

Suseplus

Also fassen wir kurz zwischenzeitlich zusammen:

random_shuffle(Anfangswert,Endwert)

liefert schon eine zufällig Zahlenfolge, diese ist allerdings auf verschiedenen PC's und auch nach einem Neustart immer gleich.

Könnt Ihr dies so bestätigen?

Will man eine richtige Zufallszahl, kommt man um rand() und die vorherige Initialisierung mit srand() oder drand48() nicht vorbei.

wenn ich srand48 verwende funktioniert alles wunderbar.

Suseplus

Das ist nicht schlecht, nur leider beantwortet das jetzt meine Fragen nicht.

CStoll

random_shuffle() verwendet - wenn du nicht explizit einen eigenen Zufallsgenerator übergibst - sein eigenes System zur Zufallsberechnung. Nur leider ist im Standard nicht festgelegt, wie dieses initialisiert wird (es kann sein, daß rand() verwendet wird), also hängt es auch von deinem System ab, welche Initialisierungsfunktion du aufrufen mußt, um "echte" Pseudozufallszahlen zu erhalten.

Das heißt, du mußt dich entweder durch den <algorithm> Header durcharbeiten, um die Wirkungsweise von random_shuffle() zu erkennen (wenn du weißt, welchen Generator es intern benutzt, kennst du auch die zugehörige Initialisierungsfunktion) oder du übergibst dem Algorithmus deinen eigenen Zufallsgenerator (bei hustbaer's Beispiel ist z.B. garantiert, daß die Verwürfelung über rand() arbeitet - also kannst du mit einem srand()-Aufruf sicherstellen, daß bei jedem Durchlauf andere Werte entstehen).

Suseplus

Danke, aber kann mir hierauf jemand eine Antwort geben:

random_shuffle(Anfangswert,Endwert)

liefert schon eine zufällig Zahlenfolge, diese ist allerdings auf verschiedenen PC's und auch nach einem Neustart immer gleich.

Könnt Ihr dies so bestätigen?

hustbaer

Suseplus schrieb:

Danke, aber kann mir hierauf jemand eine Antwort geben:

random_shuffle(Anfangswert,Endwert)

liefert schon eine zufällig Zahlenfolge, diese ist allerdings auf verschiedenen PC's und auch nach einem Neustart immer gleich.

Könnt Ihr dies so bestätigen?

Nein. Da nicht spezifiziert ist welcher Generator verwendet wird is auch nicht sicher ob nicht mit manchen Compilern der Wert von Start zu Start unterschiedlich ist.

Suseplus

Wie gesagt ich verwende gcc und KDevelop mit Suse 9.0. Ich habe mal in die algo.h und algorithm.h geschaut, dort wird ja random_shuffle wohl definiert. Konnte dort aber nichts von Gehalt ablesen, also kein rand oder srand. Würde es helfen wenn ich die beiden Header Dateien hier poste?

Hallo zusammen,

die relevanten Dateien werden bei meiner Implementation in algorithm via Präprozessordirektive include eingebunden. Innerhalb von stl_algo.h ist die folgende Definition von random_shuffle enthalten:

/**
   *  @if maint
   *  Return a random number in the range [0, __n).  This function encapsulates
   *  whether we're using rand (part of the standard C library) or lrand48
   *  (not standard, but a much better choice whenever it's available).
   *
   *  XXX There is no corresponding encapsulation fn to seed the generator.
   *  @endif
  */
  template<typename _Distance>
    inline _Distance
    __random_number(_Distance __n)
    {
  #ifdef _GLIBCPP_HAVE_DRAND48
      return lrand48() % __n;
  #else
      return rand() % __n;
  #endif
    }

  /**
   *  @brief Randomly shuffle the elements of a sequence.
   *  @param  first   A forward iterator.
   *  @param  last    A forward iterator.
   *  @return  Nothing.
   *
   *  Reorder the elements in the range @p [first,last) using a random
   *  distribution, so that every possible ordering of the sequence is
   *  equally likely.
  */
  template<typename _RandomAccessIter>
    inline void
    random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
    {
      // concept requirements
      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIter>)

      if (__first == __last) return;
      for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
	iter_swap(__i, __first + __random_number((__i - __first) + 1));
    }

Grüße
Martin

Hallo zusammen,

wie ist folgende Problemlösung zu bewerten? Ist das Makro _GLIBCPP_HAVE_DRAND48 implementierungsabhängig?

#include <iostream>
#include <iterator>
#include <algorithm>
#include <sys/timeb.h>
using namespace std;

int main()
{
  int v[] = { 1, 2, 3, 4, 5 };

  // Array mischen
  timeb t;
  ftime(&t);

#ifdef _GLIBCPP_HAVE_DRAND48
  srand48(t.millitm);
#else
  srand(t.millitm);
#endif

  random_shuffle(&v[0], &v[5]);

  // Ausgabe des gemischten Arrays
  ostream_iterator<int> oi(cout, " ");
  copy(&v[0], &v[5], oi);
}

Grüße
Martin

CStoll

lucky_tux schrieb:

wie ist folgende Problemlösung zu bewerten?

Vermutlich nur geeignet für den GCC.

Ist das Makro _GLIBCPP_HAVE_DRAND48 implementierungsabhängig?

Es sieht zumindest sehr nach einem GCC-spezifischen Makro aus.

Wie schon gesagt, hast du zwei Möglichkeiten, dein Problem anzugehen:

du sieht dir die <algorithm> an und suchst dir die Initialisierungsfunktion heraus, die DEIN spezieller Compiler benötigt (in die Kategorie fällt auch deine Lösung)
Nachteil: Dein Code ist nicht mehr portabel
du übergibst der random_shuffle() deinen eigenen Zufallsgenerator (siehe hustbaer's Beispielcode am Ende der ersten Seite)

hustbaer

Gerade wenn *NIX die Zielplattform(en) ist (sind) würde ich versuchen den Code so portabel wie möglich zu halten.
Soll heissen: definiere doch einfach frei nach meinem Beispiel einen eigenen Funktor der als Generator dient. (Du darfst natürlich meinen Code auch gerne 1:1 kopieren wenn du willst, obwohl wie gesagt modulo (%) zum Erzeugen der Range nicht optimal ist.)

Oder, wenn du schon die Standardimplementierung verwenden willst, würde ich hergehen und srand UND srand48 aufrufen wenn rand48 verfügbar ist -- es kann ja nicht schaden srand ZUSÄTZLICH aufzurufen, oder?