Krautkanal.com

Veröffentlicht am 2016-12-09 14:24:46 in /prog/

/prog/ 9591: Informatikerbernd zuhuelf! Ich habe gerade das Problem...

vikashpathak18 Avatar
vikashpathak18:#9591

Informatikerbernd zuhuelf!
Ich habe gerade das Problem, dass ich einen Bereich von 32bit Integern randomisieren will.
Dabei soll (bzw. muss) es sich nicht um echten Zufall handeln, viel mehr geht es darum, dass die Zahlen in diesem Bereich einfach nicht sequenziell ausgegeben werden sollen, sondern verteilt.
Da es sich um einen recht grossen Bereich von Zahlen handelt, waere der Ansatz, alle Integer in ein Array zu packen und mittels rand() zu verschieben recht ineffektiv.Bild relatiert
Was ich braeuchte waere eine Funktion der Art:

uint32_t randomize(uint32_t start, uint32_t stop, uint32_t index);

die bei jedem Aufruf eine "zufaellige" Zahl zurueckliefert (ahnand von $index).
Ich habe schon daran gedacht, die Zahlen mittels wechselnder Bitmasken + Modulo zu verteilen, allerdings bin ich nicht in der Lage zu beweisen, dass ich damit den kompletten Bereich von $start bis $stop erreiche.
Ideen?

curiousonaut Avatar
curiousonaut:#9593

Packe deine Integer in eine Liste, rufe liste.get(rand(sizeof liste) auf und lösche das Element aus deiner Liste sobald du es geholt hast

Oder übersehe ich was?

grantrobinson Avatar
grantrobinson:#9594

>>9593
Das waere ja auch (in etwa) mein Ansatz gewesen: Array mit allen Integern, dann randomisieren und auslesen. Aber ein Array mit mehreren Hunderttausend Integern ist mir einfach zu gross.

markolschesky Avatar
markolschesky:#9595

>>9594
Ich weiß jetzt nicht genau was du machen willst, aber der Unterschied zwischen meiner und deiner Idee ist, dass du die Liste nicht auf einmal sortieren müsstest. Könnte also als Faden im Hintergrund ausgelagert werden. Außerdem könntest du vorher das Riesenarray mit memcpy() in mehrere kleine aufsplitten.

Eine andere Idee wäre, gleich irgendwie mit einer SQL-Datenbank zu arbeiten und Einträge mit Hilfe von newid() zufällig zurückgeben zu lassen.

Außerdem solltest du wohl eh mit einer set/map/liste arbeiten. Oder du nimmst das überlegene std::vector. Gibt eigentlich keinen Grund meer, sich auf pures C zu beschränken.

polarity Avatar
polarity:#9596

>>9595
Ich hab mich vielleicht ein wenig falsch ausgedrueckt. Ich habe keine bestehende Liste vorliegen, die ich randomisieren will, sondern einen Bereich von $min zu $max.

Ich will beim Aufruf meiner Funktion genau einen Integer bekommen, ahenlich dem Generator-Konzept in Python. Wenn du dort xrange(9000) aufrufst, wird dir keine Liste mit 9000 Elementen zurueckgegeben, sondern ein Generator-Objekt. Dieses merkt sich deine aktuelle Position und gibt bei jedem Aufruf (also beim Iterieren) von next() einfach ein i++ zurueck.

Ich will nicht unhoeflich sein, aber bist du gerade am trollen? Wegen deines SQL-Vorschlages...

linux29 Avatar
linux29:#9597

>>9596
Gibt es denn einen Grund, warum du die IPs immer wieder neu generieren willst? Ich würde sie einmal in eine File schreiben, und dann immer wieder darauf zugreifen.

Wenn du bereit wärst, etwas C++ zu nutzen, gäbe es für Boost die irange (http://www.boost.org/doc/libs/1_62_0/libs/range/doc/html/range/reference/ranges/irange.html), das glaube ich das selbe macht wie xrange für python, und wohl genau das wäre, was du brauchst. Ein C-Äquivalent ist mit leider nicht bekannt, wird aber wohl auch irgendwo rumschwirren.

Und warum sollte das mit SQL ein Troll sein? Wie gesagt, keine Ahnung was du damit anstellen willst. Könnte ja sein, dass du zu den IPs noch irgendwelche Informationen speicher willst usw.

teylorfeliz Avatar
teylorfeliz:#9598

So, hab nun eine Loesung gefunden: http://sprunge.us/XccO?c

Und naja, fuer dieses Problem extra eine Datenbank anzuwerfen schien mir etwas oversized - aber du konntest ja nicht wissen, was ich noch mit der Liste vorhatte.

suprb Avatar
suprb:#9599

Bernd geht mal davon aus, dass der genannte Bereich von $start bis $stop inklusive der Randpunkte ist und außerdem keine Lücken enthält. Es geht also um das geschlossene Intervall [$start, $stop] auf den ganzen Zahlen.

Wenn der Bereich eine Länge l:=$stop-$start+1 besitzt, sodass l+1 eine Primzahl ist, hast du Glück:
- besuche https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n#Examples_2
- gehe zur Zeile n=l+1
- notiere dir die Zahl g aus der Spalte "generating set" (bei primen n ist das immer eine einzelne Zahl) (durch geschicktes Gurgeln findet man auch größere Versionen dieser Tabelle)
- voila, deine gesuchte Funktion ist nun
function randomize(start, stop, index) {
return ((g ^ (index - start + 1)) % n) + start - 1
}

- für einen Beweis siehe den Beweis des kleinen Satzes von Fermat

Wenn l+1 keine Primzahl ist, kannst du den Bereich als Vereinigung von Teilbereichen betrachten, die jeweils diese Voraussetzung erfüllen. Allerdings kann es dann sein, dass einzelne Teilbereiche sehr klein werden und der "Grad" der Pseudorandomisierung hier zu niedrig für deine Anforderungen ist.

Wenn die Länge l erst zur Laufzeit bekannt wird, dann eignet sich dieser Ansatz nicht, weil sich die erzeugenden Elemente aus dieser Tabelle nicht so ohne Weiteres programmatisch bestimmen lassen.

garand Avatar
garand:#9600

>>9599
Anmerkung: Um (g ^ (index - start + 1)) % n zu berechnen (^ ist hier "hoch" und nicht "xor"), musst du wahrscheinlich iterativ vorgehen, weil die Potenz schnell den Wertebereich des Datentyps übersteigt. Einfach gurgeln nach Potenz + Modulo, da finden sich dann geeignete Algorithmen.

craighenneberry Avatar
craighenneberry:#9601

>>9600
iterativ>>>rekurisv
immer 99%

emileboudeling Avatar
emileboudeling:#9602

>>9599
Oh, wow. Ich versuche deine Loesung mal nachzuvollziehen, danke dir.
Meine jetzige Loesung ist sehr, sehr simpel, genuegt jedoch.
Ich teile meinen Bereich in n gleichgrosse Unterbereiche auf und nehme mir dann immer die Zahlen in der Folge: Bereich1[0], Bereich2[0], Bereich3[0], Bereich1[1], Bereich2[1], Bereich3[1], ...

Shriiiiimp Avatar
Shriiiiimp:#9603

>>9591
vom gnu klauen, was sonst:
http://www.mathstat.dal.ca/~selinger/random/

curiousonaut Avatar
curiousonaut:#10222

Nein.

aadesh Avatar
aadesh:#10287

Ich brauche auch mal Hilfe.

Folgendes endet in einem segfault:


cam_t* cams = malloc(sizeof(cam_t));

int read = getline(&line, &len, file);

printf("%s\n", line);


Es funktioniert wieder wenn ich entweder die komplette malloc-Zeile entferne ODER wenn ich read nicht setze, aber getline() weiterhin aufrufe.

cam_t sieht so aus:


typedef struct cam_s {
  char* ip;
  int port;
} cam_t;


Was zum Teufel ist hier los? Kann es sein das Kot davor irgendwie falsch ist und sich ein Speicherproblem o.ä. verschleppt bis dann malloc aufgerufen bzw. read gesetzt wird? Der Kompilierer zeigt mir mit -Wall auch keinerlei Warnungen an.

RussellBishop Avatar
RussellBishop:#10288

>>10287
Du übergibst einen Pointer auf len an getline(), da sollte aber eigentlich ein size_t hin. Ich hoffe mal, Du stellst sicher, dass len kleiner als die Größe von line ist.

Shriiiiimp Avatar
Shriiiiimp:#10289

>>10288
OK danke das wars wohl...

Meine Variablendeklaration sah so aus:


char* line;
size_t len;


Muss aber so sein:


char* line = NULL;
size_t len = 0;



>If *lineptr is set to NULL and *n is set 0 before the call, then getline() will allocate a buffer for storing the line. This buffer should be freed by the user program even if getline() failed.

stephcoue Avatar
stephcoue:#10290

>>10289
Ich finde es beängstigend, dass es ohne die malloc()-Zeile funktioniert. Der Zeiger kann ja auf sonstwas gestanden haben.

Neuste Fäden in diesem Brett: