 Zufallszahlen zur Laufzeit minimieren |
gast
unregistriert
 |
|
| Zufallszahlen zur Laufzeit minimieren |
     |
Hallo!
ich habe ein Programm. Zur Laufzeit werden Zufalls-Zahlen gezogen mit Hilfe der Funktion Random(). Es werden insgesamt viele Zahlen gezogen in einer Schleife. Von diesen Zahlen wird das Minimum und das Maximum ausgerechnet mit:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
|
int min, max;
min=100;
max=-100;
for(int k=0; k<N; k++)
{
int New = Random();
if(New > max) max = New;
if(New < min) min = New;
}
|
|
Meine Aufgabe ist es, dieses Programm in der Laufzeit zu optimieren. Im Moment ist die Laufzeit T(n) = 3n also in O(n) drin.
Ich weiß, dass man auf jeden Fall auch O(n) Laufzeit braucht. Meine Überlegung ist es aber, das Minimum/Maximum schneller zu berechnen.
Dazu habe ich mir zuerst überlegt, die Zahlen in einem Binärbaum zu speichern. In einem Binärbaum wäre die Laufzeit für die Suche im Normalfall O(log(n)) für Minimum und Maximum. Allerdings müssten die Zahlen auch erst in den Binärbaum eingefügt werden und somit wäre die Laufzeit für das Einfügen O(n*log(n)). Deshalb würde dann die Laufzeit wieder wachsen und wäre zu groß.
Jetzt habe ich mir überlegt, eine Art Heap anzulegen, in dem mit konstanter Laufzeit ein Element eingefügt werden kann und von dem man mit konstanter Laufzeit das Minimum und Maximum ausrechnen kann.
Es gibt ja so einen Fibonacci-Heap, bei dem man mit O(1) ein Element einfügen kann und das Minimum auch mit O(1) bekommt. Weiß jemand, ob sowas möglich ist, also eine Optimierung des obigen Codes mit dem Fibonacci-Heap, oder würde es im Endeffekt auf das Gleiche hinauslaufen ? Ich vermute schon, dass man das eigentlich nicht mehr optimieren kann.
Danke im Voraus für eine Antwort und Freundliche Grüße
|
|
12.08.2015 13:46 |
|
|
|
|
Das Minimum/Maximum einer zufälligen Zahlenfolge kannst du nur bestimmen, indem du jede Zahl betrachtest.
Der größte Teil der Laufzeit geht ohnehin für die Erzeugung der Zufallszahlen drauf.
Du solltest min und max nicht so vorbelegen, sonst kann es sein, dass dir der tatsächliche Wert entgeht (etwa wenn alle Zahlen > 100 sind):
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
|
int min, max;
Random random = new Random();
min = random.nextInt();
max = min;
for (int k = 1; k < n; k++) {
int rnd = random.nextInt();
if (rnd > max)
max = rnd;
if (rnd < min)
min = rnd;
} |
|
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
12.08.2015 14:49 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Ich denke es laesst sich eine bessere Loesung finden, aber dafuer muss die Aufgabenstellung klarer sein.
Was liefert Random() zurueck?
Sind die Zahlen gleichverteilt, ist die Verteilung diskret?
Hat die Funktion Seiteneffekt?
Koennen Rundungsfehler ignoriert werden?
Bei einem diskreten Wahrscheinlichkeitsraum koennte man einen Wahrscheinlichkeitsmatrix definieren, der die Wahrscheinlichkeit fuer jede Moegliche min/max-Kombination beinhaeltet.
Wir definieren f(1) als die Wahrscheinlichkeit von min und max von Random().
Dann brauchen wir eine Funktion k(m1, m2) die zwei Wahrscheinlichkeits Matrixen kombiniert.
Dann laesst sich rekursiv feststellen f(n*2)=k(f(n),f(n)).
Am Ende muesste man dann noch einen Wert aus der Ergebnismatrix auslosen.
Die Kosten von f(N) waeren dann log(n) mal die Kosten von K, die wohl etwa dem Quadrat des Ergebnisraums von Random() entsprechen. Da dieser hoffentlich diskret und konstant ist, entspraeche das Ganze O(log(n)).
Der Fall dass N keine Zweierpotenz ist, wird dem geneigten Leser als Hausaufgabe ueberlassen 
Ich weiss das meine Ausfuehrungen nicht besonders konkret sind, aber die Aufgabenstellung ist es auch nicht 
.
Gruss,
ED
PS: Wenn ich laenger darueber nachdenke, funktioniert meine Loesung nur wenn man eine gewisse Unschaerfe hinnimmt oder einen wirklich magischen Zufallsgenerator hat. Andernfalls muss ich der Eulerschen Zahl leider zustimmen und wir sind gezwungen O(n) Iterationen durchzuehren. Eindeutig wird es, wenn wir festlegen dass wir nur einen Zufallszahlenmechanismus erlauben der einen Muenzwurf darstellt.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ed209: 12.08.2015 23:18.
|
|
|
12.08.2015 23:01 |
|
|
as_string 
Haudegen
Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg
|
|
Ich denke, hier kann nur eine Parallelisierung beschleunigend wirken. Wenn Du z. B. 8 Threads startest, die alle ihre Zufallszahlen selbst generieren und ihr min/max bilden und ein Hauptthread die Ergebnisse einsammelt und daraus ein gemeinsames min/max bildet.
In Java wäre so etwas mit der neuen Streaming-API wohl relativ einfach zu schreiben.
Gruß
Marco
|
|
|
14.08.2015 13:13 |
|
|
|
