Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   
Bücher:

Fachkräfte:
Softwareentwickler (m/w) für automatische Codegenerierung
Softwareentwicklung mit MATLAB/Simulink und dSPACE TargetLink im Bereich Fahrwerkregelsysteme
Elektronische Fahrwerksysteme GmbH - Ingolstadt

Entwicklungsingenieur (m/w) für modellbasierte Softwareentwicklung
Modellbasierte Softwareentwicklung mit MATLAB/Simulink und dSPACE TargetLink
Elektronische Fahrwerksysteme GmbH - Ingolstadt

Ingenieur (w/m) modellbasierte Entwicklung / Embedded Programmierung
Organisation und Durchführung von Projekten zur Integration von TargetLink in aktuelle Entwicklungsprozesse
dSPACE GmbH - Pfaffenhofen

Test-Ingenieur (m/w) für Resimulation
Implementierung, Integration und Anpassung von sogenannten ADTF-Filtern
Automotive Safety Technologies GmbH - Ingolstadt

Testingenieur (w/m) Qualitätssicherung ModelDesk
Erstellung von automatisierten und interaktiven Tests
dSPACE GmbH - Paderborn

weitere Angebote

Partner:


Vermarktungspartner


Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Laufzeitverhalen O(N^k): Program versus Algorithmus

 

Jan S
Moderator

Moderator


Beiträge: 10.481
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 18.07.2013, 10:24     Titel: Laufzeitverhalen O(N^k): Program versus Algorithmus
  Antworten mit Zitat      
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.

(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.
 

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
Private Nachricht senden Benutzer-Profile anzeigen


denny
Supporter

Supporter



Beiträge: 3.849
Anmeldedatum: 14.02.08
Wohnort: Ulm
Version: R2012b
     Beitrag Verfasst am: 18.07.2013, 10:55     Titel:
  Antworten mit Zitat      
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?
Private Nachricht senden Benutzer-Profile anzeigen
 
Jan S
Themenstarter

Moderator

Moderator


Beiträge: 10.481
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 18.07.2013, 17:55     Titel:
  Antworten mit Zitat      
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
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



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
.


goMatlab ist ein Teil des goForen-Labels
goForen.de goMATLAB.de goLaTeX.de goPCB.de


 Impressum  | Nutzungsbedingungen  | Datenschutz  | Werbung/Mediadaten | Studentenversion | FAQ | goMatlab RSS Button RSS


Copyright © 2007 - 2017 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
Partner: LabVIEWforum.de

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.