Das könnte lange dauern

[hefeteig]

Hallo,
ich habe mir ein Programm überlegt, mit dem man jede Kombinationmöglichkeit eines Zahlenschlosses mit 5 Rädchen und je 180 Zahlen auf einem Rädchen durch gehen kann.
Das ganze soll aber nur als Simulation laufen und nicht von einem Roboter gemacht werden.
Geht man von einer Zeit von 10ms pro Durchlauf des Prozesses aus, so ergibt sich eine Laufdauer des Programms:
180^5=200.000.000.000 Durchgänge, das heist 200.000.000.000/100=2.000.000.000 Sekunden
und das sind dann geteilt durch 3600 gleich etwa 555555 Stunden das wiederum sind 23148 Tage und das entspricht 63,4 Jahren!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Vielleicht hab ich mich verrechnet, aber das ist eine Berechnung, die sich sehen lassen kann.
Ich bin jetzt 15 Jahre alt, wenn ich das Programm jetzt starten würde hätte ich mit 78 Jahren die Lösung.
Aber das Programm ist ideal um eine gewisse Zeit zu warten, aber wenn ein Taster oder etwas anderes gedrückt wird fortzufahren und die bereits abgelaufene Zeit zu messen.
Gruß Hefeteig

[steffalk]

Tach auch!

Da ist aber noch Luft drin:

- Wenn Du von 10 ms schreibst, meinst Du etwa RoboPro? Ich würde solche Number-Crunching-Aufgaben nicht mit Robo-Pro machen. Auf modernen CPUs könnte ich mir locker irgendwas in der Größenordnung von Millionen Durchgängen pro Sekunde vorstellen.

- Das ganze noch multithreaded, wenn Du mehrere Prozessorkerne hast. Das gibt nochmal einen entsprechenden Faktor.

Und schon bist Du in erträglichen Zeiträumen. Nur was genau willst Du eigentlich prüfen? Was soll denn in einem dieser Durchgänge genau gemacht werden?

Gruß,
Stefan

[heiko]

Hi,

hab die Berechnung mal angeworfen. Deine Aufgabe ist es jetzt, auszurechnen, wie groß die Datenmenge wird, wenn die Ausgabe das Format a la "48 59 39 12 153" hat und jeder Buchstabe ein Byte groß ist.

Code: Alles auswählen

#include <stdio.h>

int main(void) {
	int a, b, c, d, e;
	int max=180;
	
	printf("# Kombinationsmoeglichkeiten von fuenf Ziffern 0-%d-1\n", max);

	for (a=0; a<max; a++) {
		for (b=0; b<max; b++) {
			for (c=0; c<max; c++) {
				for (d=0; d<max; d++) {
					for (e=0; e<max; e++) {
						printf("%d %d %d %d %d\n", a, b, c, d, e);
					}
				}
			}
		}
	}
}

$ g++ -O3 zahlenschloss.cc -o zahlenschloss && ./zahlenschloss > zahlenschloss.dat

[hefeteig]

Danke für eure schnellen Kommentare,
das ganze ist für ein FT Modell, mit fünf Achsen, die je einen Freiraum von 180 Grad haben.
Eigentlich brauch ich das ganze gar nicht, aber ich wollte mal wissen, wie lange ein Computer brauch um alle möglichen Positionen durch zu rechnen.
Trotzdem danke für eure Ideen das ganze in einen erträglichen Zeitraum ein zu passen.
Gruß Hefeteig

[Kai P.]

wenn du mal einen prozess baust der nach dem Startbefehl in einer endlosschleife in eine Variable 1+ machst, so ist die Variable nach nicht mal einer Sekund voll, also ist das Programm bzw. die Schleife über 32000 mal durch gelaufen. 63 Jahre dürfte somit zu lang sein

[Elektron]

@heiko

Ich habe das mal zum Spaß durchgerechnet:
0...9 Pro Stelle gibt es 10 einstellige Zahlen (die Null zähle ich mit)
10..99 weitere 90 zweistellige Zahlen (99-10=89 und die 10 selbst = 90)
100..180 weitere 81 dreistellige Zahlen (180-100=80 und die 100 selbst = 81)
Mit der Stellenanzahl multipliziert und zusammengerechnet ergibt sich also für einen Durchlauf von 0 bis 180 die stolze Zahl von 10*1+90*2+81*3 Byte= 433 Byte. Diese Anzahl Bytes wird für eine Stelle für einen vollen Durchlauf von 0 bis 180 benötigt. Bei 4 von 5 Stellen gibt es noch eine führende Leerstelle und für die gesamte Zahl habe ich einen Zeilenvorschub mit einem weiteren Byte bedacht. Also ProStelle dann 433+181 = 614 Byte.
Pro Stelle, von denen es 5 gibt, wird von 0 bis 180 durchvariiert ergibt 181 Möglichkeiten.
Auf der kleinsten Stelle 1 wird dann ein Datenvolumen von 181^^4 * 614 Byte erzeugt,
auf der nächsthöheren Stelle 2 ein Datenvolumen von 181^^3 * 614,
auf der drittgrößten Stelle 3 ein Datenvolumen von 181^^2 * 614,
auf der zweitgrößten Stelle 4 ein Datenvolumen von 181 * 614,
auf der höchsten Stelle 5 wird ein Datenvolumen von 614 Byte erzeugt.
Das alles zusammen ergibt eine stolze Summe: 662 656 924 270 Byte

Also eine Terabyte Festplatte würdest Du damit schon ziemlich voll bekommen; aber sie würde noch ausreichen.

Sofern man für die notwendigen Plattenzugriffe von einer mittleren Speicherzeit von 10ms ausgeht, käme man dann mit dem Wegspeichern der Zahlen doch wieder auf eine lebenslange Wartezeit. - Da man für das anschließende Anschauen einer solchen Datei als Mensch länger als 10ms pro Zeile benötigen würde, kann man das auch gleich sein lassen und darauf vertrauen, daß der Computer alles richtig gemacht haben wird. Für eine vollständige Kontrolle wäre nämlich keine Zeit mehr übrig, selbst wenn man sonst nichts anderes mehr tun würde. Auf eine solche Idee kommt hoffentlich niemand

[heiko]

Hallo,

ich habe noch gröber überschlagen. Eine Zeile besteht aus fünf Zahlen mit maximal drei Stellen, vier Leerzeichen dazwischen und einem Zeilenumbruch. Ist also höchstens 20 Byte lang. Wir haben 180^5 * 20 Byte, die obere Grenze ist also 3.4 Tbyte. Die wird auf jeden Fall unterschritten.

Deine Rechnung verstehe ich ab "Auf der kleinsten Stelle 1" irgendwie nicht mehr. 650 Gbyte ist mir ein bisschen zu wenig; ich hätte erwartet, dass es ein bisschen näher an die obere Schranke kommt. Aber vielleicht ist mein Überschlag auch schlecht

Spannend wäre jetzt zu untersuchen, wie gut diese Zeichenfolge von unterschiedlichen Algorithmen komprimiert wird, schließlich besteht sie ausschließlich aus heißer Luft. Ich habe den Test tatsächlich zusammen mit gzip aufgerufen, da hat gzip dann 1/3 der Rechenleistung gebraucht und zahlenschloss 2/3. Das (Zwischen-) Ergebnis hat natürlich sehr wenig Platz gebraucht. Jetzt kann man abwägen zwischen Speicherplatz und Rechenzeit, ich würde viel Speicherplatz und wenig zusätzliche Rechenzeit bevorzugen. Kannst ja mal rumprobieren

Sofern man für die notwendigen Plattenzugriffe von einer mittleren Speicherzeit von 10ms ausgeht, käme man dann mit dem Wegspeichern der Zahlen doch wieder auf eine lebenslange Wartezeit.

*nöööd* falsch. Festplatten sind dafür gemacht, lange sequentielle Datenströme schnell wegzuschreiben. Es wird nicht jede Schreiboperation separat durchgeführt, sondern es wird gepuffert (einerseits im Betriebssystem, andererseits auf der Festplatte), und außerdem muss die Festplatte nicht jedes Mal nach 20 Byte eine zufällige andere Position anfahren, so dass die Wartezeit erheblich geringer ist.

Per S-ATA angeschlossen, erreicht man eher 100 MByte/s als 10 MByte/s, so dass 1 TByte etwa 10^4 Sekunden dauern sollte, also drei Stunden. Ist also nicht das Problem.

Gruß
Heiko

[Elektron]

"Kleinste Stelle 1" würden im Dezimalsystem die Einer sein. Da wir es pro "Stelle" aber mit einer Basis 180 zu tun haben, kann ich da schlecht von einer Einerstelle sprechen. Stelle 5 ist die höchstwertige und 1 die kleinste, die Niedrigste.
Während die höchste Stelle nur einmal von 0 bis 180 durchlaufen wird, muß die nächstkleinere das gleich schon 181 mal tun (0..180). Jedesmal, wenn ein solcher Durchlauf geschafft ist gibt es nämlich einen Übertrag auf die nächsthöhere Stelle. So habe ich das pro Stelle gerechnet.
Ich habe bei meiner Rechnung mit einbezogen, daß man bei jeder Stelle die führenden Nullen jeweils weglassen kann, eine aber wenigstens die jeweilige Stelle vertreten muß. Man hat es im Mittel nicht mit 3-stelligen "Stellen" zu tun, sondern mit weniger langen (zwischen 1 und 3). Die Hälfte von 180 wäre 90 und diese Zahl ist nur 2-stellig. Man kommt also selbst mit deiner Rechnung überschlägig gerechnet nur auf etwa die Hälfte von 3.4 TB. Da aber bei einer Sequenz von 0 bis 180 die 2-stelligen Zahlen überproportional vertreten sind (0..99=100 und 0..180=181 Zahlen. 100/181=55% ) ist es sogar noch weniger.
Wenn das Abspeichern so viel schneller als erwartet ist, dann sollte man das einfach einmal ausprobieren, ob meine Berechnung das Ergebnis ganz genau trifft oder die überschlägige Abschätzung das Ergebnis besser trifft.
Bei einer zu erwartenden Kompressionsrate von ca. 80% erwarte ich 650GB * 0.2 ~= 130GB Platzbedarf.