Schleife parallelisieren < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:14 Mo 25.06.2012 | | Autor: | hunadh |
Servus,
Ich will für alle Paar-Kombinationen einer Anzahl ([mm]n_{gesamt}[/mm])von Dingen eine Berechnung durchführen. Üblicherweise habe ich dafür eine geschachtelte Schleife verwendet: Die äußere Schleife läuft für [mm]i[/mm] von 1 bis [mm]n_{gesamt}[/mm]-1 und die innere von [mm]i[/mm]+1 bis [mm]n_{gesamt}[/mm]. Das sind [mm]\bruch{n (n-1)}{2}\textrm{}[/mm] Berechnungen. Da das mitunter sehr lange dauern kann und die Berechnungen unabhängig voneinander sind, wollte ich die Schleife in mehrere Teile teilen. Damit die (annähernd) gleiche Anzahl Berechnungen getrennt durchgeführt werden kann, muss [mm]n_{gesamt}[/mm] in zunehmend größere Teile zerlegt werden. Und hier ist das Problem: Wie kann ich die Teilgrößen berechnen? Ich kann eine Formel für jede Teilmengenzahl entwickeln, aber keine allgemeine, bei der ich die Teilmengenzahl auch als Variable habe. Die Formel verlängert sich mit jeweils um einen Term. Meine Schulmathematik reicht dafür nicht mehr aus. Das mag auch eher ein Problem der Informatik sein, was bestimmt schon x-fach gelöst wurde... Bloß wo suchen?
Falls ich keinen Denkfehler habe, kann ich die Zahl der Paar-Kombination für z.B. jeden von 4 Teilen berechnen (bei den Elementen [mm]n_{1}[/mm],[mm]n_{2}[/mm] und [mm]n_{3}[/mm] wird die Liste aufgetrennt):
Anzahl Berechnungen für Teil 1 = [mm]\bruch{n_{ 1} (n_{1}-1)}{2} + n_{1}(n_{gesamt}-n_{1})[/mm]
Anzahl Berechnungen für Teil 2 = [mm]\bruch{(n_{ 2}-n_{1}) (n_{2}-n_{1}-1)}{2} + (n_{2}-n_{1})(n_{gesamt}-n_{2})[/mm]
Anzahl Berechnungen für Teil 3 = [mm]\bruch{(n_{ 3}-n_{2}) (n_{3}-n_{2}-1)}{2} + (n_{3}-n_{2})(n_{gesamt}-n_{3})[/mm]
Anzahl Berechnungen für Teil 4 = [mm]\bruch{(n_{ gesamt}-n_{3}) (n_{gesamt}-n_{3}-1)}{2}[/mm]
Das würde sich wie gesagt für steigende Teilmengenzahl immer weiter verlängern. Gibt es dafür eine allgemeine Form? Das endgültige Ziel ist, dass ich eine annähernd gleiche Anzahl Berechnungen für jeden Teil habe. (Wenn ich das in C++ schreiben würde, würde mir wahrscheinlich der Compiler das schon optimieren 
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Mi 27.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
