[HaBo]

Greenberet · 06.02.06, 00:20

Hi!
Das problem einer doppelten for Schleife liegt daran, dass sie sehr langsam ist. Es ist jedoch leicht möglich eine doppelte in eine einfache umzuwandeln.
Einige meinen vl, dass es keinen großen unterschied macht, aber der Unterschied ist ENORM.

Ich hab diese variante in den Sprachen C, C++(native), c#, java und pawn getestet. Das Ergebnis war überall gleich, die einfache ist schneller :P

Beispiel: Ich hab vor ca. nem jahr eine ShaderApi geschrieben und hab um jedes Pixel zu benutzen eine doppelte for-schleife gehabt.

Code:

for( int y = 0; x < max_y; y++ )
{
     for( int x = 0; y < max_x; x++ )
     {
           //PAAR OPERATIONEN
     }
}

Diese schreibweise ist leider weit verbreitet.
Bei dem Sobel - Operator hat diese Schreibweise bei einem Bild( 1024X768 ) ca 6-7 sekunden gedauert

Hier die Umwandlung in eine einfache for-schleife

Code:

int size = max_x * max_y;
for( int i = 0; i < size; i++ )
{
      int x = i % max_x;
      int y = i / max_x;

     //PAAR OPERATIONEN
}

Allein durch diese Änderung hat die ganze Operation beim Sobel-Filter gerade mal < 1 sec gedauert^^.
Zu beachten ist die Schreibweise der Berechnungen.

x wäre in beiden Fällen die innere Schleife und y die Äußere.

Hier ist jetzt der genaue Code was ihr wie ersetzen müsst:

Code:

for( int var_aussen; var_aussen < aussen_max; var_aussen++ )
{
     for( int var_innen; var_innen < innen_max; var_innen++ )
     {

     //...

     }
}

//die gesammtgröße in eine variable speichern, da sie sonst jedes mal neu ausgerechnet werden würde.
int size = aussen_max * innen_max;
for( int i = 0; i < size; i++ )
{
     int var_innen = i % innen_max;
     int var_aussen = i / innen_max;

     //...
}

Also ihr seht schön eine einfache for-schleife benutzen :P
Wenn ich mein altes Programm gefunden hab, uploade ich es mal.

-- Greenberet

2Bios · 06.02.06, 01:09

wenn ich das jetzt richtig verstanden habe, bezieht sich das nur auf render-engines? denn wenn die innere schleife inkrementel und die äußere dekrementel zälht, dann sollte doch eigentlich keine optimierung möglich sein. nur um auf nummer sicher zu gehen...

weiß eigentlich jemand, wie die performance mit zwei while-schleifen aussieht? bin grad dabei meinen laptop neu aufzusetzen...

Anzeige

- Anzeige -

Greenberet · 06.02.06, 01:24

also das ganze geht nur wenn beide dekrement oder inrement sind
wie die berechnung bei unterschiedlichen ist muss ich mir erst anschauen XD
Ich glaube das ganze müsste man dann mit einer wertinvertierung gehen.

und nein das ist nicht nur bei rendering, ich hab rendering nur als beispiel genommen weil das viel zeit in anspruch nimmt und man dort die zeit aber braucht. Bei anderen dingen ist die einfache auch schneller^^

mit while schleifen sieht das ganze im großen und ganzen gleich aus wie mit den for schleifen.

**CDW** · 06.02.06, 01:51

Ich denke das hängt SEHR vom compiler ab

Zitat:

//die gesammtgröße in eine variable speichern, da sie sonst jedes mal neu ausgerechnet werden würde.

Ein ordentlicher compiler macht es natürlich weg

. Z.B auch

Code:

for(int i=0;i<MAX;i++)
{
ergebnis=i*20;
}

sollte ein "neuerer" Compiler vorberechnen und die Schleife aus dem fertigen Code wegoptimieren.
Was Du vergleichst, ist ohne den "weitere Codeeinsicht" nicht wirklich vergleichsam: denn normalerweise ist eine Division zumindest auf einem Pentium/AMD immer noch langsamer als ein Vergleich - und davon hast Du gleich zwei.Ein "vernünftiger" Compiler würde es hier bei einer belassen (denn bei einer Division wird gleichzeitig auch der Rest festgehalten - so braucht man eigentlich nur eine, eventuell also die Reihenfolge % und / vertauschen - um dem Compiler bei der optimierung zu helfen) . Was ich vermute, warum bei Dir soviel mehr leistung rausgekommen ist: bessere Cache"hits", auch wenn solche Sachen auf einem P4 schwer vorherzusagen sind. Jedenfalls denke ich dass besonders bei Speicherzugriffen diese Zählvariablen alleine keine allzugroße Rolle spielen

Ok, ein wenig von meiner Seite:

Code:

    align 4
        timer_begin 1000, REALTIME_PRIORITY_CLASS ;die schleife wird insgesamt 1000 000 000 durchlaufen
        mov ebx,0 ;mov 0 ist schneller als XOR -> inteldoku +eigene tests
        LOOP1:
          mov ecx,0
          LOOP2:
            add ecx,1
            cmp ecx,1000
            jbe LOOP2
          add ebx,1
          cmp ebx,1000
          jbe LOOP1  
 

    timer_end
    print ustr$(eax)
    print chr$(" ms, 'primitiver Loop'",13,10)

    align 4
    timer_begin 1000, REALTIME_PRIORITY_CLASS

        mov ebx,1000
        LOOP3:
          mov ecx,1000
          LOOP4:
            sub ecx,1 ;auf Pentium4 schneller als dec ecx
            jns LOOP4
          sub ebx,1
          jns LOOP3  
 

    timer_end
    print ustr$(eax)
    print chr$(" ms, 'verbesserter Loop'",13,10)

    
align 4
    timer_begin 1000, REALTIME_PRIORITY_CLASS
        
        mov edi,1000; unsere MAX Konstante, Optimierung die ein "älterer" Compiler nicht vornimmt!            
        mov ebx,0
        LOOP5:
           mov eax,ebx
           mov edx,0
           div edi
           ;jetzt ist in edx X wert und in EAX Y             
           add ebx,1 ;auf Pentium4 schneller als dec ecx
        cmp ebx,1000000
        jbe LOOP5
         

    timer_end
    print ustr$(eax)
    print chr$(" ms, nur 'eine' schleife, leicht optmiert",13,10)

    align 4
    timer_begin 1000, REALTIME_PRIORITY_CLASS
       
        mov edi,1000; unsere MAX Konstante, Optimierung die ein "älterer" Compiler nicht vornimmt!            
        mov ebx,1000000
        LOOP6:
           mov eax,ebx
           mov edx,0
           div edi
           ;jetzt ist in edx X wert und in EAX Y             
           sub ebx,1 ;auf Pentium4 schneller als dec ecx
        jns LOOP6
         

    timer_end
    print ustr$(eax)
    print chr$(" ms, nur 'eine' schleife, etwas besser optimiert",13,10)


mov   eax, input(13,10,"Press enter to exit...")
exit

; ??????????????????????????????????????????????????????????????
end start

Ich bin zwar alles andere als ein guter Optimierer, nicht desto trotz glaube ich einen Compiler überbieten zu können, der nicht mal

Zitat:

e speichern, da sie sonst jedes mal neu ausgerechnet werden würde.
int size = aussen_max * innen_max;

optimieren kann

und zwar wird jede Schleife 1000 000 000 mal asugeführt (die forschleifen jeweils 1000 mal und die funktion selber auch 1000 mal, damit man halbwegs was messen kann).
alle schleifen sind gleich - sie laufen immer die gleiche Anzahl an Loops durch. Die ersten beiden sind jeweils: eine "naive" Schleife, dann eine "optimierete" (zählt rückwärts und erspart sich damit einen Vergleich) die anderen beiden sind jeweils zu einer zusammengefasst worden (nach Deiner Methode - also auch das Modulo/Teilen um X,Y Werte herauszufinden), wobei ich die erste nur "ein wenig" optimiert habe: sprich sie kommt nur mit einer Division aus (das wird ein "älterer" Compiler nicht berücksichtigen und fast mit sicherheit zwei daraus machen) und auch die Konstante lasse ich im Register (wiederum: bei älteren C/Delphi compilern kann man davon ausgehen, dass sie sie Lokal abspeichern und gleich wieder laden

)
die zweite Schleife ist wieder "rückwärts" und erspart sich dadurch einen Vergleich. Das ganze ist auf einen P4 ausgelegt (deswegen auch mov ecx,0 und nicht XOR - denn mov ist schneller, genauso ADD ECX,1 und nicht INC ECX). Meine Zahlen sind (P4, 3.0 GHz, HT):

Durchlauf 1:
525 ms, 'primitiver Loop'
418 ms, 'verbesserter Loop'
9586 ms, nur 'eine' schleife, leicht optmiert
9210 ms, nur 'eine' schleife, etwas besser optimiert

Durchlauf2:
526 ms, 'primitiver Loop'
446 ms, 'verbesserter Loop'
9613 ms, nur 'eine' schleife, leicht optmiert
9435 ms, nur 'eine' schleife, etwas besser optimiert

Durchlauf3:
528 ms, 'primitiver Loop'
440 ms, 'verbesserter Loop'
9586 ms, nur 'eine' schleife, leicht optmiert
9110 ms, nur 'eine' schleife, etwas besser optimiert

Wie man sieht, bringt die jeweilige "Minioptimierung" (sprich das rückwärtslaufenlassen) bei den "normalen" Schleifen am meisten. Die jeweiligen unteren Werte sind übrigens kein Fehler (wie auch ich anfangs dachte)

wenn man die Division weglässt, sind die Werte z.T sogar besser als bei den oberen Schleifen (da weniger Instruktionen).
Und wenn man bedenkt, dass ein "älterer" Compiler hier gar zwei Divisionen und ein paar unnötige Speicherzugriffe hätte - damit untermauere ich meine These, dass bei Dir andere Gründe für den Leistungszuwachs gesorgt haben

.

Im Anhang ist eine Test.exe samt Quelltext und Includes. Damit kann jeder, der MASM32 v8 hat, damit rumspielen.

2Bios · 06.02.06, 02:25

member of honour bzw mod ist das mindeste, was cdw werden kann: sein altruismus in ehren auf ewiglich (oder so) *thumbsup*

nun aber wirklich gute nacht

blueflash · 06.02.06, 10:56

@CDW: wenns aber nur um die division geht, die braucht man natürlich nicht. und das eine einzelne schleife weniger overhead produziert sollte eigtl. klar sein.

Greenberet · 06.02.06, 11:06

Zitat:

Original von CDW
Ich denke das hängt SEHR vom compiler ab

Zitat:

//die gesammtgröße in eine variable speichern, da sie sonst jedes mal neu ausgerechnet werden würde.

Ein ordentlicher compiler macht es natürlich weg

.

Bei Konstanten wirds nicht neu ausgerechnet, allerdings bei normalen variablen schon, da sich die Wärte ändern könnten

Zitat:

Was Du vergleichst, ist ohne den "weitere Codeeinsicht" nicht wirklich vergleichsam: denn normalerweise ist eine Division zumindest auf einem Pentium/AMD immer noch langsamer als ein Vergleich - und davon hast Du gleich zwei.

Weiter codeeinsicht: Also Shapderoperationen bestehen aus additionen und multiplikationen von mindestens 9 werten^^( Ausnahme bei multiplikationen mit 0 die hab ich weggelassen, ist aber abhängig vom Shader )

Zitat:

Ein "vernünftiger" Compiler würde es hier bei einer belassen (denn bei einer Division wird gleichzeitig auch der Rest festgehalten - so braucht man eigentlich nur eine, eventuell also die Reihenfolge % und / vertauschen - um dem Compiler bei der optimierung zu helfen) .

jain, wäre möglich das es ein wenig was nützt, allerdings darfst du nicht vergessen, dass diese 2 anweisungen unabhängig von einander sind und deswegen höchst wahrscheinlich gleichzeitig verarbeitet werden.

Zitat:

Was ich vermute, warum bei Dir soviel mehr leistung rausgekommen ist: bessere Cache"hits", auch wenn solche Sachen auf einem P4 schwer vorherzusagen sind. Jedenfalls denke ich dass besonders bei Speicherzugriffen diese Zählvariablen alleine keine allzugroße Rolle spielen

Ähm ich hab meine variablen nicht im register^^( zumindest nich vom code her

)

Zitat:

DEIN CODE+erklärung

du speicherst alles in registern, ich nicht( hat auch gründe )
du machst alles direkt in asm und springst hin und her. In anderen Programmiersprachen ist die übersetzung nicht so simple wie bei dir

Zitat:

Und wenn man bedenkt, dass ein "älterer" Compiler hier gar zwei Divisionen und ein paar unnötige Speicherzugriffe hätte - damit untermauere ich meine These, dass bei Dir andere Gründe für den Leistungszuwachs gesorgt haben

.

Wüsst keine anderen Gründe, da ich nur das umgestellt hab^^

[quote]Original von blueflash
@CDW: wenns aber nur um die division geht, die braucht man natürlich nicht. und das eine einzelne schleife weniger overhead produziert sollte eigtl. klar sein.[/quote
da geb ich dir vollkommen Recht.

**CDW** · 06.02.06, 20:40

Zitat:

@CDW: wenns aber nur um die division geht, die braucht man natürlich nicht. und das eine einzelne schleife weniger overhead produziert sollte eigtl. klar sein.

Naja, es ging ja egentlich nicht um Shader sondern einfach um "doppelte" schleifen - nichts mehr und nichts weniger, und da so ein "einzelding" eigentlich weniger Overhead verursacht und damit schneller läuft, ist irgendwie logisch

Zitat:

allerdings darfst du nicht vergessen, dass diese 2 anweisungen unabhängig von einander sind und deswegen höchst wahrscheinlich gleichzeitig verarbeitet werden.

Das hängt ja wiederum von der CPU ab und nicht zuletzt was der Compiler daraus bastelt - im schlimmsten Fall hat man nacher zwei Divisionen und der Compiler verwendet bei beiden den EAX Register (was er bei StandardDIV nicht anders machen kann) - so dass sie wiederum abhängig sind und nicht "parallel" ausgeführt werden können. Wobei das ein heikles Thema ist und ich zugegebenermaßen noch nicht wirklich die dicke Intel-Dokumentation unter meinem Schreibtisch durchgelesen habe

Zitat:

Ähm ich hab meine variablen nicht im register^^( zumindest nich vom code her Augenzwinkern )
....
du machst alles direkt in asm und springst hin und her. In anderen Programmiersprachen ist die übersetzung nicht so simple wie bei dir

Naja, das war die "möglichst" optimale Annahme, was so ein Compiler eigentlch daraus basteln können sollte (eventuell gehts auch noch besser).
Und ein Forschleife sollte doch auch in etwa so übersetzt werden - zumindest Schablonenmäßig als Label mit einem Jump. Ob aber mit oder ohne ausgiebige Registernutzung - Div bleibt Div.

Zitat:

Wüsst keine anderen Gründe, da ich nur das umgestellt hab^^

Was ich meinte war ja eben, dass man nicht pauschal das sagen kann - rein logisch müsste es langsamer werden

, auch wenn es vom Schleifenoverhead nicht wirklich auffallen sollte. Was ich mit Chachehits meinte:
ein einfaches Beispiel.
Code 1:

Code:

for (int y=0;y<BILD_Y;y++)
  for(int x=0;x<BIDL_X;x++)
   {
    ReadPixel(x,y);
   }

Code 2:

Code:

for (int x=0;x<BILD_X;x++)
  for(int y=0;y<BIDL_Y;y++)
   {
      ReadPixel(x,y,blue);
   }

Rein formell ist es das gleiche - allerdings wird i.R Code1 auf einem Pentium/AMD
viel schneller laufen als Code2 - denn die Daten liegen linear im Speicher

pixel1,pixel2, ... , pixel2000

und werden auch in Blöcken beim Zugriff "gecacht". Der erste Code geht sequentiell durch, der zweite dagegen "hüpft" durch den Speicherraum durch (zugriff: y*Y_MAX+x) und macht dadurch Caching zurnichte - so dass man als Folge langsame Speicherzugriffe hat und insgesamt eine sehr schlechtere Perfomance. Und vielleicht hattest Du "Glück" mit der Umstellung und hast dadurch z.B die "magische" Cachegrenzengröße erreicht - so dass der Code komplett gecacht werden konnte.
Die Wege des Compilers sind unergründlich

Wäre aber interessant, wenn jemand das ganze mit einem "hochoptimierenden" Compler testet (z.B dem von Intel).

Greenberet · 06.02.06, 21:29

einigen wir uns darauf, dass es teilweise schneller und teilweise langsamer ist( osnt artet das hier noch aus )^^

Zitat:

zugriff: y*Y_MAX+x

falsch
y*X_MAX+x

deswegen ist die formel ja auch

Code:

int x = i % X_MAX;
int y = i / X_MAX;

wenn man hier jetzt Y_MAX genommen hätte wäre es dein code 2 gewesen^^

Tec · 06.02.06, 21:50

/Neunmalkluger-Modus on

Das was hier diskutiert wird ist unter dem Begriff "Big O Notation" bekannt. Eine einzelne Schleife hat die Komplexität von O(N), eine verschachtelte von O(N?).

/Neunmalkluger-Modus off

blueflash · 06.02.06, 22:19

/Neunmalklügerer Modus an

Grundsätzlich richtig. Aber wenn man aus zwei verschachtelten schleifen die jeweils eine Komplexität von O(n) haben eine macht die die gleiche Funktionalität bietet, hat man i.d.R. eine neue Schranke
m = n * n also ändert sich an der Komplexität gar nüscht.

/Neunmalklügerer Modus aus

Tec · 06.02.06, 22:54

Da in der Äusseren Schleife nun "drinnen" keine weitere Schleife mehr abläuft, verringert dies die Komplexität von O(N?) zu O(N log N) wenn ich mich noch recht daran erinnere. Auf jeden Fall ist die Komplexität kleiner geworden (auch wenns nur ein bischen ist).

So genug über Big-O gelabert

Gabriel3 · 24.02.06, 19:17

Hi!
Ich habe mir das Ganze mal angeschaut und stelle fest: Es funktioniert nicht.
Das Problem ist, dass wir in der Mathematik mit einem Dezimalsystem rechnen, wie der Code hier ja auch.

Code:

int size = max_x * max_y;
for( int i = 0; i < size; i++ )
{
      int x = i % max_x;
      int y = i / max_x;

     //PAAR OPERATIONEN
}

Soweit so gut. Aber wenn wir jetzt wollen, dass die Null auch immer mitzählt

Zitat:

for( int y =0; x < max_y; y++ )

for( int x = 0; y < max_x; x++ )

, dann funktioniert der Code nicht mehr und man muss folgendes machen:
----------------------------------------------------------------
int size = max_x * max_y + max_x + max_y;
for( int i = 0; i < size; i++ )
{
int x = i % (max_x+1);
int y = i / (max_x+1);

//PAAR OPERATIONEN
}
---------------------------------------------------------------
Ich hoffe, ich habe den C++-Code richtig geschrieben, kann kaum C++.

cu gabriel

Greenberet · 24.02.06, 19:38

Mein Code stimmt schon.
deiner ist falsch.
du vergisst dass man mit 0 zu zählen beginnt und nicht mit 1
sprich max_x = 5
mögliche pos. für x: 0, 1, 2, 3, 4

Gabriel3 · 25.02.06, 12:40

Hi!
Kann sein, dass ich das falsch verstanden habe. Wenn du also sagst Maximum=5, dann willst du 5 gar nicht erreichen, sondern nur bis 4 gehen? Da macht zwar die Bezeichnung MAX keinen Sinn, aber dann stimmt dein Code natürlich, aber wenn du wirklich bis einschließlich zum Maximum gehen willst, wirst du meinen nehmen müssen.

cu Gabriel

PS: Jetzt sehe ich es gerade: Du hast als Bedingung gestellt: x < max_x. Sorry, habe ich wegen der verwirrenden Bezeichnung "max_x" übersehen.

Anzeige

- Anzeige -

06.02.06, 00:20	#1 (permalink)
Greenberet Registriert seit: 05.02.06 Likes: 0	Doppelte for schleife: performance optimierung Anzeige Hi! Das problem einer doppelten for Schleife liegt daran, dass sie sehr langsam ist. Es ist jedoch leicht möglich eine doppelte in eine einfache umzuwandeln. Einige meinen vl, dass es keinen großen unterschied macht, aber der Unterschied ist ENORM. Ich hab diese variante in den Sprachen C, C++(native), c#, java und pawn getestet. Das Ergebnis war überall gleich, die einfache ist schneller :P Beispiel: Ich hab vor ca. nem jahr eine ShaderApi geschrieben und hab um jedes Pixel zu benutzen eine doppelte for-schleife gehabt. Code: for( int y = 0; x < max_y; y++ ) { for( int x = 0; y < max_x; x++ ) { //PAAR OPERATIONEN } } Diese schreibweise ist leider weit verbreitet. Bei dem Sobel - Operator hat diese Schreibweise bei einem Bild( 1024X768 ) ca 6-7 sekunden gedauert Hier die Umwandlung in eine einfache for-schleife Code: int size = max_x * max_y; for( int i = 0; i < size; i++ ) { int x = i % max_x; int y = i / max_x; //PAAR OPERATIONEN } Allein durch diese Änderung hat die ganze Operation beim Sobel-Filter gerade mal < 1 sec gedauert^^. Zu beachten ist die Schreibweise der Berechnungen. x wäre in beiden Fällen die innere Schleife und y die Äußere. Hier ist jetzt der genaue Code was ihr wie ersetzen müsst: Code: for( int var_aussen; var_aussen < aussen_max; var_aussen++ ) { for( int var_innen; var_innen < innen_max; var_innen++ ) { //... } } //die gesammtgröße in eine variable speichern, da sie sonst jedes mal neu ausgerechnet werden würde. int size = aussen_max * innen_max; for( int i = 0; i < size; i++ ) { int var_innen = i % innen_max; int var_aussen = i / innen_max; //... } Also ihr seht schön eine einfache for-schleife benutzen :P Wenn ich mein altes Programm gefunden hab, uploade ich es mal. -- Greenberet

25.02.06, 12:40	#15 (permalink)
Gabriel3 Registriert seit: 26.05.05 Likes: 0	re Hi! Kann sein, dass ich das falsch verstanden habe. Wenn du also sagst Maximum=5, dann willst du 5 gar nicht erreichen, sondern nur bis 4 gehen? Da macht zwar die Bezeichnung MAX keinen Sinn, aber dann stimmt dein Code natürlich, aber wenn du wirklich bis einschließlich zum Maximum gehen willst, wirst du meinen nehmen müssen. cu Gabriel PS: Jetzt sehe ich es gerade: Du hast als Bedingung gestellt: x < max_x. Sorry, habe ich wegen der verwirrenden Bezeichnung "max_x" übersehen.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Doppelte IP im Netzwerk	sw33tlull4by	Network · LAN, WAN, Firewalls	3	10.07.09 19:16
hilfe bei query optimierung	easteregg	(Web-) Design und webbasierte Sprachen	2	08.07.09 20:15
GalleryScript - Performance Optimierung	reaLInsanity	(Web-) Design und webbasierte Sprachen	9	22.07.08 18:07
640x480 Optimierung	webfreak	(Web-) Design und webbasierte Sprachen	6	06.02.07 21:31
Kernel-Optimierung	Nesssus	Linux/UNIX	3	24.02.06 13:38

06.02.06, 01:09	#2 (permalink)
2Bios Senior Member Registriert seit: 28.08.05 Likes: 0	wenn ich das jetzt richtig verstanden habe, bezieht sich das nur auf render-engines? denn wenn die innere schleife inkrementel und die äußere dekrementel zälht, dann sollte doch eigentlich keine optimierung möglich sein. nur um auf nummer sicher zu gehen... weiß eigentlich jemand, wie die performance mit zwei while-schleifen aussieht? bin grad dabei meinen laptop neu aufzusetzen...

06.02.06, 01:24	#3 (permalink)
Greenberet Themenstarter Registriert seit: 05.02.06 Likes: 0	also das ganze geht nur wenn beide dekrement oder inrement sind wie die berechnung bei unterschiedlichen ist muss ich mir erst anschauen XD Ich glaube das ganze müsste man dann mit einer wertinvertierung gehen. und nein das ist nicht nur bei rendering, ich hab rendering nur als beispiel genommen weil das viel zeit in anspruch nimmt und man dort die zeit aber braucht. Bei anderen dingen ist die einfache auch schneller^^ mit while schleifen sieht das ganze im großen und ganzen gleich aus wie mit den for schleifen.

06.02.06, 02:25	#5 (permalink)
2Bios Senior Member Registriert seit: 28.08.05 Likes: 0	member of honour bzw mod ist das mindeste, was cdw werden kann: sein altruismus in ehren auf ewiglich (oder so) thumbsup nun aber wirklich gute nacht

06.02.06, 10:56	#6 (permalink)
blueflash Member of Honour Registriert seit: 03.10.01 Likes: 1	@CDW: wenns aber nur um die division geht, die braucht man natürlich nicht. und das eine einzelne schleife weniger overhead produziert sollte eigtl. klar sein.

06.02.06, 21:50	#10 (permalink)
Tec Senior Member Registriert seit: 02.10.01 Likes: 1	/Neunmalkluger-Modus on Das was hier diskutiert wird ist unter dem Begriff "Big O Notation" bekannt. Eine einzelne Schleife hat die Komplexität von O(N), eine verschachtelte von O(N?). /Neunmalkluger-Modus off

06.02.06, 22:19	#11 (permalink)
blueflash Member of Honour Registriert seit: 03.10.01 Likes: 1	/Neunmalklügerer Modus an Grundsätzlich richtig. Aber wenn man aus zwei verschachtelten schleifen die jeweils eine Komplexität von O(n) haben eine macht die die gleiche Funktionalität bietet, hat man i.d.R. eine neue Schranke m = n * n also ändert sich an der Komplexität gar nüscht. /Neunmalklügerer Modus aus

06.02.06, 22:54	#12 (permalink)
Tec Senior Member Registriert seit: 02.10.01 Likes: 1	Da in der Äusseren Schleife nun "drinnen" keine weitere Schleife mehr abläuft, verringert dies die Komplexität von O(N?) zu O(N log N) wenn ich mich noch recht daran erinnere. Auf jeden Fall ist die Komplexität kleiner geworden (auch wenns nur ein bischen ist). So genug über Big-O gelabert

24.02.06, 19:38	#14 (permalink)
Greenberet Themenstarter Registriert seit: 05.02.06 Likes: 0	Mein Code stimmt schon. deiner ist falsch. du vergisst dass man mit 0 zu zählen beginnt und nicht mit 1 sprich max_x = 5 mögliche pos. für x: 0, 1, 2, 3, 4

[HaBo]

Doppelte for schleife: performance optimierung