Mit Matlab die Komplexität eines Algorithmuses bestimmen

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

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Kroko123

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 17.07.2013, 19:14 Titel: Mit Matlab die Komplexität eines Algorithmuses bestimmen

Hallo zusammen,

kann ich mit Matlab die Komplexität eines Programms bestimmen? Falls ja, wie geht das?

Viele Grüße
Marcel

Winkow

Moderator


	Beiträge: 3.842

	Anmeldedatum: 04.11.11

	Wohnort: Dresden

	Version: R2014a 2015a

Verfasst am: 17.07.2013, 19:16 Titel:

was verstehst du denn unter "komplexität"? je genauer du die frage formulierst desdo wahrscheinlicher ist es eine antwort zu bekommen. sich mehr als 30 sec für die fragestellung zu nehmen ist meist hilfreich

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 17.07.2013, 19:30 Titel:

Entschuldigung, ich dachte man wüsste etwas mit dem Begriff "Komplexität" anzufangen.

Es geht um die Typischen Komlexitätsklassen O(1) bis O(2^n). Laufzeitkomplexität, Speicherkomplexität.

Harald

Forum-Meister


	Beiträge: 24.492

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 17.07.2013, 20:33 Titel:

Hallo,

Zitat:

Entschuldigung, ich dachte man wüsste etwas mit dem Begriff "Komplexität" anzufangen.

Wenn man aus Bereichen wie numerische Mathematik kommt: ja. Ansonsten eher nicht.

Ich sehe grundsätzlich nur die Möglichkeit, dies experimentell zu ermitteln, indem man die Operation für mehrere N durchführt und dann schaut, welche Kurve sich für die Laufzeit ergibt (tic/toc).

Speicherkomplexität vor allem bei internen Berechnungen dürfte noch schwieriger sein. Wenn der Algorithmus händisch programmiert ist, lässt sich das ja aus dem Workspace ablesen bzw. mit whos.

Grüße,
Harald

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 17.07.2013, 21:15 Titel:

Hallo Harald,

Dankeschön Smile

Schade, dass Matlab eine solche Funktion nicht inbegriffen hat. Mit "anschauen" ist es leider sehr schwierig auszumachen, allerdings möglich.

Grüße
Marcel

Harald

Forum-Meister


	Beiträge: 24.492

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 17.07.2013, 21:39 Titel:

Hallo,

durchaus möglich, dass es eine solche Funktion gibt, z.B. auf File Exchange, aber mir ist nichts bekannt.
Wenn man einen umfangreicheren Algorithmus programmiert, macht man sich ja an sich wenn vorher darüber Gedanken, welche Komplexität das haben wird.

Grüße,
Harald

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 18.07.2013, 00:04 Titel:

Hallo Kroko123,

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.

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

Nebenbei gibt es nocht 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.

Gruß, Jan

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 18.07.2013, 09:42 Titel:

Vielen vielen Dank Jan für den ausführlichsten Kommentar Smile

Bin absolut begeistert Very Happy

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 18.07.2013, 10:25 Titel:

Hallo Kroko123,

Ich habe ein Tutorial daraus gemacht: http://www.gomatlab.de/laufzeitverh.....ithmus-t29722.html#118333

Gruß, Jan

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 18.07.2013, 23:42 Titel:

Top, Daumen HOCH Smile

Da habe ich wohl einmal die Richtige Frage gestellt Smile


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.