random_shuffle würfelt Array immer gleich aus!- Hilfe

Braunstein

@Simon2
random_shuffle ist in algorithm, also Standard.

CStoll

Simon2 schrieb:

Da es sich dabei (IIRC) um keine Standardfunktion handelt, können wir hier aber nur mutmaßen.

Nur am Rande: random_shuffle() IST eine Standardfunktion (ich weiß nicht den genauen Absatz des Standards, aber die Funktion ist ein offizieller STL-Algorithmus). Das Problem dürfte wirklich daran liegen, daß der verwendete Zufallsgenerator von random_shuffle() nicht im Standard festgelegt ist - die MS-Version verwendet z.B. rand() dafür.

PS @Suse: Übrigens verwendest du veraltete Header-Dateien - laut Standard gültig sind <cstdlib>, <iostream> und <algorithm>.

Simon2

Braunstein schrieb:

@Simon2
random_shuffle ist in algorithm, also Standard.

[LeoGetz]OK OK OK[/LeoGetz]
Heute scheint mein "Aufräumtag für alte Mißverständnisse" zu sein....
Da mir "algo.h" unbekannt war (ebenso wie random_shuffle() ), habe ich nichtmal nachgesehen (von den anderen ".h"'s bin nich nicht darauf gekommen, dass es die alte Version von algorithm ist).

Glücklicherweise hatte ich "IIRC" geschrieben ...

Danke,

Simon2.

Suseplus

hustbaer schrieb:

Vielleicht hilft es wenn du
srand(time(0));
vor random_shuffle aufrufst.

Alternativ kannst du einen eigenen Zufallszahlengenerator verwenden, indem du den als Predicate mitgibst (einfach nen Funktor als 3. Parameter mitgeben).

Also srand hat keine Abhilfe gebracht. Der 3te optionale Funktionsparameter von random_shuffle würde mich interessieren. Ich hatte schon vor dem Thread mit diesem rumgespielt, aber ich weiß einfach nicht was man da reinschreiben soll. Die Doku kann ich dazu nicht interpretieren.

Wenn meine Header veraltet sind, dann ist es kein Problem, weil ich mit Suse 9.0 arbeite und mit der alten Version der Kompiler und KDevelop 2.1.5. Dies ist auch zwingend nötig für dieses Projekt. Also bitte keine Tipps, wie neue Version nehmen. Es gab ja die alte ne lange Zeit als aktuelle und da muss es dann ja auch gegangen sein.

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?