Laufzeitverhalen O(N^k): Program versus Algorithmus

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 18.07.2013, 10:24 Titel: Laufzeitverhalen O(N^k): Program versus Algorithmus

Liebe Leser,

Zur Frage: "Gibt es ein Programm, das die Komplexität der Laufzeitverhaltens in Bezug auf die Problemgröße (Landau O) bestimmt?"

Die Komplexität eines Algorithmus ist nicht gerade eindeutig definiert, siehe http://de.wikipedia.org/wiki/Landau-Symbole. Wenn es aber um Computer-Programme geht, wird es noch deutlich schwieriger die Beziehung zwischen Aufwand und Problem-Größe zu definieren. Denn ein Computer-Programm läuft auf einem physikalischen Rechner, dessen innerer komplexer Aufbau beträchtlichen Einfluss hat. Ein paar Tests mit unterschiedlichen Problemgrößen N können ein vager Hinweis sein, mehr aber nicht. Oft braucht man aber auch nicht mehr. Hier eine unvollständige Liste der Schwierigkeiten:

1. O(N^10) klingt nach einem sehr langsamen Programm, aber das gilt laut Definition nur für "sehr große N". Das Verhalten bei N=10^100 ist aber in echten Programmen nicht relevant. Nützlicher wäre hier die Potenz von N für die tatsächlich genutzen Größen zu berechnen.

2. Wenn wiederholt auf die gleichen Datenblöcke zugegriffen wird, kann die Rechenzeit stark davon profitieren, wenn die Daten in den Prozessor oder 2nd-Level-Cache passen. Dann entfällt der langsame Zugriff auf das RAM. Noch dramatischer wird es, wenn auch das RAM nicht mehr reicht und die Daten auf die Festplatte als virtuellen Speicher geswapt werden. Dann kann schon eine Änderung von N zu N+1 zu einer 1000 fach längeren Laufzeit führen. Von einer polynomialen Laufzeit wie für die Definition von O benötigt, kann dann nicht mehr die Rede sein.

3. Multi-threading, Pipelining und Branch-Prediction sind Features des Prozessors, die versuchen den theoretischen Laufzeiten ein Schnippchen zu schlagen. Es kommt dann auf den Prozessor und Compiler an, und die Effekte lassen sich beim Lesen des Algorithmus oder des Sourcecodes gar nicht abschätzen. Beispiel:

Code:

x = rand(1, 88999);
tic; for k =1:1000; y = sum(x); end; toc
% >> Elapsed time is 0.121 seconds.
x = rand(1, 88999+1);
tic; for k =1:1000; y = sum(x); end; toc
% >> Elapsed time is 0.195 seconds.

Funktion ohne Link?

(Matlab 2009a/64, Win7, Core2Duo) Die Summe benötigt für 89000 Elemente 58% mehr Laufzeit als für 88999 Elemente?! Ja, denn das ist die magische Grenze, ab der Matlab die Summe auf zwei Threads aufteilt und das Starten der Threads benötigt viel Zeit.
Wenn ein Problem auf mehrere Threads aufgeteilt wird, kann das Betriebssystem diese zwischen den physikalischen Cores hin- und herschieben ("Load-Balancing"). Dieses Verschieben kostet aber Laufzeit und die Effekte auf die Gesamt-Laufzeit lassen sich nicht vorhersagen. Man kann einen Thread auch an einen Core binden (siehe "thread affinity/Core affinity"), das hat aber nicht unbedingt Vorteile.

4. Matlab's JIT kann dynamisch während der Laufzeit optimieren. Das kann heißen, dass beim ersten Durchlauf einer Schleife bestimmte konstante Ausdrücke noch berechnet werden, bei den folgenden Iterationen aber nicht mehr. Auch wenn dann ein "SIN(1.23)" in einer Schleife steht, ist nicht unmittelbar klar, wie oft es berechnet wird.

5. Interpretierte Hochsprachen wie Matlab können sehr komplizierte Seiteneffekte haben. Die Variablen in einem Algorithmus stehen immer "unmittelbar" zur Verfügung. In einem Computer-Programm müssen sie aber zunächst den dazugehörigen Pointer zu den Daten aus einer Lookup-Tabelle besorgen. Dabei können ungeschickte Programmier-Methoden massive Auswirkungen haben, z.B. wenn man in Matlab den Typ einer Variablen wiederholt ändert oder Variablen dynamisch mit EVAL oder ASSIGNIN erzeugt. Beispiel:

Code:

function Test1

tic;
for k = 1:1e5
v = 23 + k;
v = int32(v); % v ändert Typ
x = double(v) / 2;
end
toc;

tic;
for k = 1:1e5
v = 23 + k;
w = int32(v); % neue Variable!
x = double(w) / 2;
end
toc;

>> Elapsed time is 0.731460 seconds.
>> Elapsed time is 0.002624 seconds.

Funktion ohne Link?

Ein einfaches Einführen einer neuen Variable macht den Code 280 mal schneller. Gut, das Beispiel ist an den Haaren herbeigezogen, aber einen Faktor 10 habe ich in echten Programmen schon gesehen. Durch das Anschauen des Algorithmus oder des Programms lässt sich das nicht erahnen und die Laufzeit muss mit Tests bestimmt werden.

6. Moderne Prozessoren werden schnell müde. Es nennt sich zwar "Turbo-Boost", wenn der Prozessor höher takten kann, solange nur wenige Kerne belastet werden. Man könnte es aber auch andersherum ausdrücken: "Fatigue-Brake" oder "Multi-Core Throttle" regelt den Takt runter, wenn viele Kerne aktiv sind, weil der Gesamt-Prozessor es nicht mehr auf die Reihe kriegen würde. Offensichtlich fanden die Chip-Hersteller "Turbo-Boost" aber aus werbetechnischen Gründen besser. Vor einer Laufzeitmessung sollte sich der Prozessor also erstmal warmlaufen. Auf eine ordentliche Definition für O(N)_warmgelaufen braucht man allerdings nicht zu hoffen.

Schlußfolgerung:
Man kann durchaus bestimmen, ob ein Programm für ein Problem mit 2000 Elementen doppelt oder viermal so lange Zeit braucht wie für 1000 Elemente. Das heißt dann aber noch nicht, dass es für 2e9 auch entsprechend viel länger braucht als für 1e9. Knicke erscheinen in den Laufzeitkurven durch Multi-Threading, Cache-Größen und Änderungen der Prozessor-Frequenz. Der Unterschied zwischen Algorithmus und implementierten Programm ist dabei ebenfalls sehr wichtig.

Aus diesen Gründen gibt es wohl keine Matlab-Funktion zur Bestimmung der Laufzeit-Komplexität eines Programms.

Bemerkung: Es gibt es noch weitere "Komplexitäten eines Programms", z.B. die Länge des Parse-Trees (siehe den mtree Befehl, der in MathWorks CODY verwendet wird), die "Cyclomatic complexity" (siehe "checkcode('filename','-cyc')", etc. Google findet mehr zu dem Thema.

Zuletzt bearbeitet von Jan S am 25.09.2013, 12:25, insgesamt 2-mal bearbeitet

denny

Supporter


	Beiträge: 3.853

	Anmeldedatum: 14.02.08

	Wohnort: Ulm

	Version: R2012b

Verfasst am: 18.07.2013, 10:55 Titel:

Hallo Jan,

Zitat:

Die Summe benötigt für 89000 Elemente 58% mehr Laufzeit als für 89999 Elemente?!

Kleiner Tippfehler, meinst du 88999 Elemente?

Jan S

Themenstarter

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 18.07.2013, 17:55 Titel:

Hallo denny,

Wow! Danke für das aufmerksame Lesen!

Merkwürdigerweise hatte ich das gestern Abend schoneimal verbesert und hier einfach den Text aus the Thread per Copy&Paste eingefügt. Da ist wohl gestern etwas schiefgelaufen.

Gruß, Jan


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.