welche kostet weniger Zeit?

buSC · Beiträge: 39

hallo liebe Forumer,

welcher Fall kostet weniger Zeit?
Fall1:

Delphi-Quelltext

1:
2:
3:
4:
5:

for i:=1 to 1000 do
 begin
   statment1;
   statment2;
 end

Fall2:(mit 2 for)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

for i:=1 to 1000 do
begin
  statment1;
end
for i:=1 to 1000 do
begin
  statment2;
end

Moderiert von Narses: Delphi-Tags hinzugefügt

Bergmann89 · Verfasst: Do 14.01.10 12:25

Hey,

Fall 1 müsste schneller sein. Probiers doch einfach aus. Mit GetTickCount kannste du die Zeit messen. Da der Vorgang aber einmal viel zu langsam war, machst du nochma ne Schleife mit 1000-10000 durchläufen um die beiden Fälle.

MfG Bergmann

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^

buSC · Beiträge: 39

ja Danke Bergmann, fuer die Antwort
kann ich mal ausprobieren.

Bergmann89 · Verfasst: Do 14.01.10 13:11

Hey,

aus irgend nem Grund ist es doch anders rum^^

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

procedure TForm1.Button1Click(Sender: TObject);
var StartTime: Cardinal;
var i, j: Integer;
var str, str2: String;
const COUNT = 100;
begin
  str := '';
  str2 := '';
  StartTime := GetTickCount;
  for i := 0 to COUNT do begin
    for j := 0 to 1000 do begin
      str := str + IntToStr(j);
      str2 := str2 + IntToStr(i);
    end;
  end;
  Memo1.Lines.Add('Fall 1: '+IntToStr(GetTickCount-StartTime)+' ms');

  str := '';
  str2 := '';
  StartTime := GetTickCount;
  for i := 0 to COUNT do begin
    for j := 0 to 1000 do
      str := str + IntToStr(j);
    for j := 0 to 1000 do
      str2 := str2 + IntToStr(i);
  end;
  Memo1.Lines.Add('Fall 2: '+IntToStr(GetTickCount-StartTime)+' ms');
end;

markieren

Quelltext

1:
2:

Fall 1: 608 ms
Fall 2: 94 ms

MfG Bergmann.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^

Gausi · Verfasst: Do 14.01.10 13:29

Das ist aber auch eine unfaire Messung. Der Großteil der Zeit dürfte für das Umkopieren der Strings im Speicher draufgehen, und für den zweiten Durchlauf ist der Speicher dann "passend".

Auf meinem 2 Jahre alten Laptop liefert obiger Code Laufzeiten meist zwischen 31 und 47 ms (also ein Unterschied von 1, gemessen in der GetTickCount-Genauigkeit von ~15ms). Und mal hat Fall 1, und mal Fall 2 die bessere Laufzeit.

_________________
We are, we were and will not be.

elundril · Verfasst: Do 14.01.10 13:50

theoretisch müsste aber der zweite langsamer sein oder? da der erste ein laufzeit von θ(n) hat und der zweite ja eine von θ(2n) (wobei der 2er ja glaub ich vernachlässigbar ist, oder?)

lg elundril

_________________

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Xentar · Verfasst: Do 14.01.10 14:04

Der einzige Unterschied besteht doch darin, dass Variante 2 eine zweite Schleife startet - das sollten doch nur wenige Assembler Befehle sein?
Vielleicht merkt aber auch der Compiler, dass beide Schleifen über den selben Bereich gehen, und fasst die zusammen?

_________________
PROGRAMMER: A device for converting coffee into software.

FinnO · Verfasst: Do 14.01.10 14:43

Öhm?

mal rein bildlich:

wenn ich einmal 1000 Schritte laufe, und jedes mal dabei irgendwas mache, und direkt danach nochmal 1000 Schritte und was anderes Mache, brauch ich doch länger, als wenn ich EINMAL 1000 Schritte mache, und dann immer beides direkt nacheinander?

Bergmann89 · Verfasst: Do 14.01.10 15:14

Ja,

wie user profile icon

elundril schon gesagt hat, die Laufzeit vom 2. Fall ist größer, mal davon abgesehen, dass man normalerweiße Konstante Faktoren nicht berücksichtigt...

@Gausi: Ich hab das mal in 2 Programme geteilt. Da sollte die Verteilung des Speichers bei beiden Fällen gleich sein. Un ich hab bei Fall 1 500ms un bei Fall 2 2000ms.

MfG Bergmann.

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^

JoelH · Verfasst: Do 14.01.10 15:47

Xentar hat folgendes geschrieben :

Der einzige Unterschied besteht doch darin, dass Variante 2 eine zweite Schleife startet - das sollten doch nur wenige Assembler Befehle sein?
Vielleicht merkt aber auch der Compiler, dass beide Schleifen über den selben Bereich gehen, und fasst die zusammen?

theoretisch sollte die Variante 2 genau 1/4 langsamer sein. Wenn man davon ausgeht, dass jeder Befehl die gleiche Ausführungszeit hat, was ja aber meist nicht gegeben ist, weshalb im Praxistest der Unterschied nur unwesentlich sein sollte, da das inc i wohl die geringste Ausführungszeit hat.

Denn letztlich brauchts mindestens 3 Befehle bei Variante 1 und 4 bei Variante 2 pro Durchlauf.

bei 1

inc i
do a
do b

bei 2

inc i
do a
inc i2
do b

_________________
mfg. Joel

Bergmann89 · Verfasst: Do 14.01.10 16:01

Hey,

das ich nich ganz richtig. Bei der Laufzeitberechnung is genau vorgeschrieben was wielange braucht.
und inc(i) benötigt 3 (wenn ich mich noch recht entsinnen kann):

markieren

Delphi-Quelltext

1:	i := i + 1; //i lesen (1), rechnen (2), i schreiben (3)

Wenn du das jetzt auch mit den Rest machst erkennst du, das dein 1/4 nich stimmt.

MfG Bergmann

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^

JoelH · Verfasst: Do 14.01.10 16:16

Bergmann89 hat folgendes geschrieben :

....und inc(i) benötigt 3 ...

Äpfel, Birnen oder Tomaten?

Wie gesagt, tendenziell sollte dies trotzdem der mit abstand kleinste Part des gesamten Durchlaufs sein. Wenn du jetzt nicht gerade irgendwelche Arrayvars nullst. Aber wenn da zwischendrin richtig gewerkelt wird, dann wird der Zeitverbrauch für die Schleifenerhöhung insgesamt marginal gering.

Edit:
Aber es gibt sicher Assemblerpuristen hier dies bis auf den Taktzyklus genau ausrechnen könne

_________________
mfg. Joel

Boldar · Verfasst: Do 14.01.10 16:21

dass komt drauf an, ob i schon in einem register steht, in dem Fall wäre es 1 Befehl.
Laufvariablen stehen meines Wissens im Register, vielleicht meldet sich Benbe ja mal dazu, der hat da Ahnung.(Der ist doch unser ASM-Freak)

F34r0fTh3D4rk · Verfasst: Do 14.01.10 17:30

Xentar hat folgendes geschrieben :

Der einzige Unterschied besteht doch darin, dass Variante 2 eine zweite Schleife startet - das sollten doch nur wenige Assembler Befehle sein?
Vielleicht merkt aber auch der Compiler, dass beide Schleifen über den selben Bereich gehen, und fasst die zusammen?

Die beiden geposteten Code Fragment sind allerdings nicht äquivalent. Die Umformung ist nur dann legal, wenn statment1;
und statement2; nicht voneinander abhängen. Man kann aus den beiden Schleifen eine machen, aber ich wüsste grad keine andere Möglichkeit (wenn man es genau nimmt) als:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

for i:=1 to 2000 do
begin
  if (i<=1000) then
    statement1(i) else
      statement2(i-1000);
end;

Lossy eX · Beiträge: 1048 Erhaltene Danke: 4

Xentar hat folgendes geschrieben :

Vielleicht merkt aber auch der Compiler, dass beide Schleifen über den selben Bereich gehen, und fasst die zusammen?

Also Delphi fast keine Schleifen einfach so zusammen. Ein ehemalier Kollege (C++ Entwickler) hatte mir vor einigen Jahren mal gesagt, dass der C++ Kompiler mitunter hergehen und Schleifen optimieren. Dazu wird der Schleifenkörper dann X Mal wiederholt und die Schleife muss nicht mehr so oft durchlaufen werden. Ob das stimmt konnte ich selbst nie nachprüfen. Deswegen kann ich das nur als Hörensagen so im Raum stehen lassen.

Allerdings auf CPU Ebene hat so etwas durchaus seine Bewandniss. Denn für jeden Schleifendurchgang muss der Prozessor einen Wert verringern und vergleichen. Falls das Ende nicht erreicht ist muss im Code gesprungen werden. Wenn diese Überprüfungen reduziert werden ist das in jedem Fall eine Ersparrnis. Die Aufrufe von statment1 und statment2 sind vorhanden und an denen ändert sich nichts. Man lässt nur einigen Overhead weg.

Das Beispiel von Bergmann finde ich nur bedingt brauchbar. GetTickCount (mehr muss wohl nicht gesagt werden). Und innerhalb der einen Schleife wird auf Variable I, J, Str und Str2 zugegriffen wärend in der anderen Schleife nur jeweils auf zwei der vier Variablen zugegriffen wird. Um so weniger Variablen um so größer die Chance, dass der Kompiler das alles in den Registern abhandeln kann. Bei 4 Variablen muss er zwangsweise irgendwann auf den RAM oder CPU Cache zugreifen. Das ist dann immer langsamer. Obendrauf kommen noch die massiven Stringoperationen. Daraus resultiert Aufwand des Speichermanagements und eventuell des Betriebssystems. Das erhöht ungemeint die Chance, dass irgendwo unsichtbarer Mehraufwand dazu kommt.

Bei einer Schleifenmessung sind die Unterschiede sowieso nur minimal weswegen man so etwas eigentlich nur auf CPU Ebene/theoretisch betrach betrachten kann und sollte. Aber auch da hängt es recht stark davon ab was innerhalb der Schleife passiert. Sofern die Schleife keine Schleife mit 1 Mio durchläufen ist sollte man wohl auch eher den Schleifenkörper betrachten. Da dürfte wesentlich mehr potential existieren als in einer Schleife.

Aber kurz gesagt. Aus CPU Sicht ist eine Schleife günstiger als 2 Schleifen. (1 Auto verbraucht auch weniger Sprit als 2). Hängt aber da immer davon ab wie der Kompiler den Schleifenkörper/Zählvariable organisieren kann.

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.

Horst_H · Verfasst: Fr 15.01.10 11:28

Hallo,

Was CPUs heutzutage alles parallel machen ist schon erstaunlich:
Mein Programm zu GetNumberOfChars, also Buchstaben/char in einem String zählen
www.delphi-forum.de/...der=asc&start=20
kam auf 2,3 Befehle pro Takt , 7 Befehle in 3 Takten.
Und Schleifen sind nun mit das schnellste, was CPU beherrschen, da die Sprungvorhersage nur äußerst selten danebenliegt.

Gruß Horst

F34r0fTh3D4rk · Verfasst: Fr 15.01.10 18:21

Da fällt mir ein, wenn die zwei Schleifen unabhängig voneinander sind, kann man diese (entsprechende Hardware vorausgesetzt) auch auf zwei Prozessoren aufteilen. Das wäre dann fast doppelt so schnell.
Interessant ist, dass wenn beide in unterschiedlichen Threads auf einem Prozessor laufen lässt und beide mit einer Priorität von 50% laufen lässt, sollte ungefähr die erste Variante raus kommen. Wenn der erste der beiden Threads maximale Priorität hat, kommt so etwas wie die zweite Variante raus.

mkinzler · Verfasst: Sa 16.01.10 16:28

Die Ausführungsgeschwindigkeit der Statements ist konstant (bezogen auf die Anzahl der Schleifen)
Deshalb müsste 2. auf jeden Fall langsamer sein.

_________________
Markus Kinzler.

Lossy eX · Beiträge: 1048 Erhaltene Danke: 4

F34r0fTh3D4rk hat folgendes geschrieben :

Da fällt mir ein, wenn die zwei Schleifen unabhängig voneinander sind, kann man diese (entsprechende Hardware vorausgesetzt) auch auf zwei Prozessoren aufteilen. Das wäre dann fast doppelt so schnell.
Interessant ist, dass wenn beide in unterschiedlichen Threads auf einem Prozessor laufen lässt und beide mit einer Priorität von 50% laufen lässt, sollte ungefähr die erste Variante raus kommen. Wenn der erste der beiden Threads maximale Priorität hat, kommt so etwas wie die zweite Variante raus.

Jain. Bzw deine Aussage stimmt. Aber das kann man meiner Meinung nach nicht so pauschal sagen. Kommt da auf einige Faktoren an.

Das Starten der Threads bzw das Warten auf deren Ende dauert auch seine Zeit. Je nachdem was Statement1 und Statement2 so machen kann es sein, dass die schneller Fertig sind als die Threads gestartet wurde. Also bei kleinen Additionen/Berechnungen/was auch immer. Obendrauf kommt noch das Problem, dass gegebenfals irgendwann irgendwas synchronisiert werden muss. Wenn das passiert entsteht noch mehr overhead. Man könnte auch die CPU Anzahl erfragen und auf einem 1 CPU System dann enstprechende Threads weglassen. Der Aufwand lohnt aber nur wenns wirklich wichtig ist.

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.

mkinzler · Verfasst: Mo 18.01.10 09:47

Dann müsste der Code auch in 2 verschiedenen Threads laufen.

_________________
Markus Kinzler.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme