Reale Laufzeit abschätzen

[hm...]

Hi Leute,

ich habe mehrere Millionendaten und möchte gerne im <Vorab berechnen wie lange das Programm ca. rechnen wird.

Mein derzeitiger Algorithmus läuft im O(n^2) kann mir jemand sagen wie ich diese Abschätzung im ungefähren in eine reale Zeitangabe umrechnen kann? Ich habe das Programm auf einem PC mit durchschnitlicher leistung.

mfg

[hm...]

Hi Leute,

ich habe mehrere Millionendaten und möchte gerne im <Vorab berechnen wie lange das Programm ca. rechnen wird.

Mein derzeitiger Algorithmus läuft im O(n^2) kann mir jemand sagen wie ich diese Abschätzung im ungefähren in eine reale Zeitangabe umrechnen kann? Ich habe das Programm auf einem PC mit durchschnitlicher leistung.

mfg

das programm soll in java laufen :)

[MudGuard]

Hi,

Mein derzeitiger Algorithmus läuft im O(n^2) kann mir jemand sagen wie ich diese Abschätzung im ungefähren in eine reale Zeitangabe umrechnen kann? Ich habe das Programm auf einem PC mit durchschnitlicher leistung.

das programm soll in java laufen :)

Diese Information ist genauso hilfreich wie "PC mit durchschnittlicher Leistung".

cu,
Andreas

[hm...]

Danke für die Antworten.

Ich hab 12 Ram zur Verfügung und 1.7 Millionen Datensätze [(1.7 Millionen)x(3) um genau zu sein] und wollte abschätzen inwiefern ein O(n^2) Algorithmus diese innerhalb von maximal 10 Minuten verarbeiten kann. Ich wollte herausfinden ob ich den Algorihtmus Randomisieren muss um auf eine Laufzeit von maximal O(n) zu kommen.

Wenn O(n^2) aber nicht gleichbehandelt werden kann wie O(c*n^2) [mit c viel kleiner als n] geht das wohl nicht.

[Jens Holzkämper]

Tach,

Ich hab 12 Ram zur Verfügung und 1.7 Millionen Datensätze [(1.7 Millionen)x(3) um genau zu sein] und wollte abschätzen inwiefern ein O(n^2) Algorithmus diese innerhalb von maximal 10 Minuten verarbeiten kann.

dafür musst du herausfinden, wie schnell der Algorithmus ist. Du hast momentan nur eine Abschätzung, wie schnell der Algorithmus mit größerem Input langsamer wird; ein O(n²)-Algorithmus kann aber für einen Datensatz beliebig viel Zeit brauchen, du weißt nur, dass er dann für zwei Datensätze viermal so lange (eher vier mal so viele Ressourcen) braucht.

Wenn O(n^2) aber nicht gleichbehandelt werden kann wie O(c*n^2) [mit c viel kleiner als n] geht das wohl nicht.

c=1, das würde ich gegen 1000000 noch nicht als mathematisch viel kleiner betrachten, solange ich da große Zahlen als Referenz haben möchte.

mfg
Woodfighter

[T-Rex]

Ich geb dir mal ein praktisches Beispiel.

Meine Frau hat einen Rechner, der hat auf den ersten Blick gesehen halb so viel Leistung wie mein (Highend will immer das neuste GTA spielen :D) Rechner.

Meine Webseite hat ca. 5 MB Daten aufgeteilt in ca. 10.000 Datensätze (nur grob). LAde ich mir die Datenbank runter und Importier sie bei meiner Frau, dann dauert es einen kleinen Moment und die Daten sind auf der Festplatte.
Bei meinem Rechner kann ich mir einen Kaffee holen. Wahrscheinlich ist die Schreibleistung meiner Festplatte immens schlecht.
Ich möchte dir damit sagen, dass nicht alles so offensichtlich ist. Dass meine Festplatte beim schrieben länger braucht ist auch nur eine Vermutung. Vielleicht sitzt ein Kabel nicht richtig.

Ich würde an deiner Stelle das Programm ca. 10 mal laufen lassen und dann einen Durchschnittswert bilden.

Gruß
wer möchte seinen Chef gegen meinen eintauschen?
T-Rex

[MudGuard]

Hi,

ich habe mehrere Millionendaten und möchte gerne im <Vorab berechnen wie lange das Programm ca. rechnen wird.

Mein derzeitiger Algorithmus läuft im O(n^2) kann mir jemand sagen wie ich diese Abschätzung im ungefähren in eine reale Zeitangabe umrechnen kann?
Ich habe das Programm auf einem PC mit durchschnitlicher leistung.

Dann wird es wohl durchschnittlich lange laufen.

Ohne weitere Daten kann man da gar nichts sagen.

Wie lange dauert die Initialisierung des Programms?
Wie lange dauert die Nachbearbeitung des Programms?

Wie lange braucht das Programm für die eigentliche Berechnung (also ohne Initialisierung/Nachbearbeitung) für 1000/10000 Daten?

Wenn Du diese Zeiten hast, kann man hochrechnen.
Wenn's für 1000 Daten x Sekunden dauert, wird's für 1000000 mindestens ca. 1000000 mal solange dauern (es sind 1000mal soviele Daten, bei O(n²) also 1000000 mal so viel Rechenzeit.

Mindestens deshalb, weil bei großen Datenmengen natürlich noch zusätzliche Effekte auftreten können (RAM reicht nicht mehr, so daß geswapped werden muß; ...)

cu,
Andreas

[Christian Kruse]

Moin hm...,

ich habe mehrere Millionendaten und möchte gerne im <Vorab berechnen wie lange das Programm ca. rechnen wird.

Das ist so nicht möglich, denn das hängt von vielen Faktoren ab: Durchsatz des I/O-System, was läuft sonst noch auf der Kiste, ist der Algorithmus parallelisierbar, wie ist es um die Rechenkapazität bestellt, wie lange braucht dein Algorithmus für einen Datensatz, wieviel RAM steht zur Verfügung, etc, pp – das musst du messen.

Wenn dir das bei 1mio Datensätzen zu lange dauert, messe es für 1000 Datensätze (bei O(n^2) würdest du dabei ja 1000000 Datensätze letztlich betrachten) und rechne es hoch auf 1mio Datensätze.

LG,
 CK