Kommt auf die genaue Fragestellung an wie "gut" der Zufall sein soll.Web-Schecki schrieb:Klar, hier im konkreten Fall geht's auch sicherlich nicht um kryptographisch sicheren Zufall. Macht den Einwurf von Hardware-RNGs doch aber nur noch absurder
Der Thread ist mit "C++" getagged und der TE spricht von recht konkreten Datenstrukturen wie Listen (wenn auch möglicherweise unabsichtlich). Ist schon sehr konkret an einer Implementierung.JackForceOne schrieb:
Nein, macht man nicht. Es ist eine absolute Standardannahme bspw. bei der Analyse von randomisierten Algorithmen. Zufallsbits zu bekommen ist schlicht kein Problem, um das man sich irgendwelche tieferen theoretischen Gedanken machen muss, wenn es nicht gerade kryptographisch sicher sein muss.JackForceOne schrieb:
Die Größe eines std::string ist immer (!) dieselbe (also eine Konstante) und für eine gegebene Implementierung perPiktogramm schrieb:
sizeof(std::string) bereits zur Kompilierzeit ermittelbar. Damit ist auch das memory, dass ein std::vector<std::string> mindestens benötigt, für eine gegebene Anzahl an Elementen darin ebenfalls fix vorgegeben.class string { unsigned int size; char * p;}uint32_t, weswegen der Index-Vector also weniger Speicherplatz benötigt als der String-Vector.p referenzierte Character-Array nimmt zur Laufzeit natürlich weiteren Speicherplatz ein, ist aber nicht Teil der String-Klasse selbst, und beeinflusst daher folglich weder sizeof(std::string) noch den Memory-Bedarf des String-Vectors).size und p belegten Bytes speichern und sich damit das dynamische Character-Array komplett ersparen. Das spart dann nicht nur bei der string-Erstellung oder beim Kopieren dieses Strings die jeweilige memory-allocation, sondern bei jedem Zugriff auf den String auch noch den Indirektions-Weg zu diesem Character-Array. Enorme Ersparnis!size speichert ob die Character-Werte direkt lokal im std::string Objekt oder in einem externen Character-Array liegen. Falls ersteres der Fall ist, liegen diese Character-Werte dann direkt in den restlichen von size und p belegten Bytes. Auf einer typischen 64-bit Plattform kann man also einen String-Wert bestehend aus maximal 15 Character-Werten direkt im string-Objekt selbst speichern (das erste Byte von size enthält dabei sowohl das obige Bit-Flag wie auch dann in den restlichen Bits dieses Bytes gespeichert die Anzahl der Character-Werte).uint32_t als Typ für die Indices nehmen sollte, sondern besser typename std::vector<T>::size_type (was typischerweise std::size_t ist, und somit auf 64-bit Plattformen typischerweise auf einen 64-bit Integer Typ hinausläuft) ist wiederum eine ganz andere Sache (dann benötigt der Index-Vector auch entsprechend mehr memory), und wird dem OP hoffentlich auffallen falls sein vector je mal mehr als 2^32 Elemente enthalten sollte und sich seine Funktion zum Ziehen daraus dann etwas unerwartet verhält ...
#include <cstdint>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <random>
using namespace std;
template < typename E >
void select_n_elements(const vector < E > & in, vector < E > & out, uint32_t n) {
static auto rng = default_random_engine {};
vector < uint32_t > indexes(in.size());
iota(begin(indexes), end(indexes), 0);
ranges::shuffle(indexes, rng);
set < uint32_t > indexes_set(indexes.begin(), indexes.begin() + n);
for (auto it = in.begin(); it != in.end(); ++it) {
int index = std::distance(in.begin(), it);
if (indexes_set.contains(index)) {
out.push_back(in [index]);
}
}
}
int main() {
vector < string > in = {
"1",
"2",
"3",
"4",
"5",
"6",
"7",
"8",
"9",
"10"
};
for (int i = 0; i <= in.size(); i++) {
vector < string > out = {};
select_n_elements(in, out, i);
for (auto & e: out) cout << e << ' ';
cout << endl;
}
}4
8 9
2 7 9
1 2 4 5
2 3 6 7 10
2 4 5 6 7 8
2 3 4 6 7 9 10
1 2 3 4 5 6 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10n immer kleiner gleich size() wäre...rng muss noch initialisiert werden (nur einmal), sonst wird zum Beispiel im 9. Schritt die 10 immer nicht gezogen werden...#include <time.h>
#include <cstdint>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <random>
using namespace std;
default_random_engine get_rng() {
static auto rng = default_random_engine {};
static bool is_initialized = false;
if (!is_initialized) {
cout << "Init RNG..." << endl;
rng.seed(time(NULL));
is_initialized = true;
}
return rng;
}
template < typename E >
void select_n_elements(const vector < E > & in, vector < E > & out, const uint32_t n) {
vector < uint32_t > indexes(in.size());
iota(begin(indexes), end(indexes), 0);
ranges::shuffle(indexes, get_rng());
set < uint32_t > indexes_set(indexes.begin(), indexes.begin() + n);
for (auto it = in.begin(); it != in.end(); it++) {
int index = distance(in.begin(), it);
if (indexes_set.contains(index)) {
out.push_back(in [index]);
}
}
}
int main() {
vector < string > in = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"};
for (int i = 0; i <= in.size(); i++) {
vector < string > out = {};
select_n_elements(in, out, i);
for (auto & e: out) cout << e << ' ';
cout << endl;
}
}in. Dafür müssten die Indexes aber zunächst aufsteigend sortiert sein. Dadurch würde sich die Laufzeit verringern von 2*m auf m+n (wenn m die Länge von in wäre und n die Anzahl der zu ziehenden Elemente).
Auf einem Desktoprechner kannst dukali-hi schrieb:
Aber so etwas wäre denkbar.random_device zur Initialisierung von default_random_engine nehmen.
Wenn man verschiedene Ansprüche reduziert und es wirklich eine linked list ist kann man auch über die Liste iterieren und per Zufall bei jedem Element entscheiden lassen ob man dieses Element zieht.kali-hi schrieb:
simpsonsfan schrieb:
#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
using namespace std;
template < typename E >
void select_n_elements(const vector < E > & in, vector < E > & out,
const uint32_t n) {
static random_device rd;
static default_random_engine rng(rd());
vector < uint32_t > indexes(in.size());
iota(begin(indexes), end(indexes), 0);
ranges::shuffle(indexes, rng);
sort(indexes.begin(), indexes.begin() + n);
for (auto it = indexes.begin(); it != indexes.begin() + n; it++) {
out.push_back(in [ * it]);
}
}
// tests until the first match
void test1() {
vector < int > in(10);
iota(begin(in), end(in), 0);
for (int i = 0; i < in.size();) {
vector < int > out = {};
select_n_elements(in, out, 1);
for (auto & e: out) cout << e << ' ';
cout << endl;
if (out[0] == i) {
i++;
cout << endl;
}
}
}
// tests until its missing the first element
void test9() {
vector < int > in(10);
iota(begin(in), end(in), 0);
for (int i = 0; i < in.size();) {
vector < int > out = {};
select_n_elements(in, out, 9);
for (auto & e: out) cout << e << ' ';
cout << endl;
if (find(out.begin(), out.end(), i) == out.end()) {
i++;
cout << endl;
}
}
}
int main() {
test1();
test9();
}Ich glaube, das wäre dann ungerecht.foofoobar schrieb:
Deswegen sprach ich ja von "Anspruch reduzieren".kali-hi schrieb:
Was heißt "ungerecht"?kali-hi schrieb:
int rand() { return(1) }Web-Schecki schrieb:
Und der TO sollte die Datenstrukturen genau beschreiben, seinen Anspruch an "Zufälligkeit" und ob viel oder weniger Speicher verbraucht werden darf/soll.Web-Schecki schrieb:
Und/oder vielleicht zieht man mit etwas unterhalb der durchschnittlichen Wahrscheinlichkeit und dann eben so lange, bis die gewünschte Anzahl gezogen ist. Man muss sich halt dem eingebrachten Bias / der reduzierten Anforderung bewusst sein.foofoobar schrieb:
Ich würd's so machen. Aber sagen, kann ich dir das nicht, mein (modernes/aktuelles) C++ ist eher auf B1-Niveau.kali-hi schrieb:
In der Liste können Meier, Müller, Schulze stehen...simpsonsfan schrieb:
Je nach Implementierung ist es doch zufällig was als "erstes" gezogen wird.kali-hi schrieb:In der Liste können Meier, Müller, Schulze stehen...
Wenn Meier und Schulze gezogen werden, dann soll dort nicht auf einmal Schulze und Meier herauskommen. Am Beispiel verständlich?