| Autor |
Beitrag |
Matg40
      
Beiträge: 52
|
Verfasst: Mo 15.05.06 08:09
Hi !
Gibts eigentlich irgendwo eine zentrale Datenbank/Website... in der Programmiersprachen-Konstrukte nach Performance eingetragen sind?
Ich dachte da an etwas wie:
Programmiersprache: C# Konstrukt: switch Performance bis 10.000 Ausführungen, Performance ab 100.000 Ausführungen...
Also entweder allgemein oder programmiersprachenabhängig die Performance von Konstrukten aufgelistet.
Es gibt viele (unsichere) Einzeltipps, aber gibts da auch was (gesichertes) zentrales?
MfG
Matt
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mo 15.05.06 12:15
Dazu gibt's nichts gesichertes, weil schon das ändern des Variablentyps von A nach B die Performance Signifikant beeinflussen kann. Im Einzelfall muss man immer probieren. Um zu kapieren, was wann weshalb gut ist, sollte man die Architektur des Systems verstanden haben. Man sollte also wisssen, was der Reihe nach wo verarbeitet wird usw ...
Es ist z.B. ein großer Unterschied, ob ich
Delphi-Quelltext 1: 2: 3: 4: 5: 6:
| asm MOV EAX, DWORD PTR [A] MOV EDX, DWORD PTR [A] ADD EAX, EDX MOV DWORD PTR [A], EAX end; |
schreibe oder
Delphi-Quelltext 1: 2: 3: 4:
| asm MOV EAX, DWORD PTR [A] ADD DWORD PTR [A], EAX end; |
oder
Delphi-Quelltext 1: 2: 3:
| asm MUL DWORD PTR [A], 2 end; |
(Zweiteres muss nicht schneller sein  ).
Zu betrachten ist hier immer die Schrittfolge, die am Einfachsten die nötigen Informationen und Zwischenergebnisse liefert ...
Moderiert von Christian S.: Delphi-Tags repariert
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
digi_c
      
Beiträge: 1905
W98, XP
D7 PE, Lazarus, WinAVR
|
Verfasst: Mo 15.05.06 13:23
Ich hoffe das Bewerten und mathematische Beweisen von Algorithmen lernt man im Info-Studium? (Fang nämlich dieses Jahr an)
Ja nach so einer DB hab ich auch schon mal gesucht/gefragt aber nichts gefunden...
|
|
tommie-lie
      
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: Mo 15.05.06 13:36
digi_c hat folgendes geschrieben: | | Ich hoffe das Bewerten und mathematische Beweisen von Algorithmen lernt man im Info-Studium? (Fang nämlich dieses Jahr an) |
Wär' ich mir nicht so sicher. Du wirst sicherlich das Beweisen von Algorithmen lernen und das Ausrechnen ihrer Komplexität, aber mit Real-Life-Performance hat beides recht wenig zu tun. Heutzutage gibt es so viele verschiedene Architekturen und Möglichkeiten, Dinge zu erledigen, es wäre ziemlich aufwändig wenn man im Studium das für alle Algorithmen einmal durchspielen wollte. Schließlich gehört dazu auch mehr als das "Abzählen" der Takte, die ein Befehl braucht. Caches wollen berücksichtigt werden, Das Pipelining heutiger Prozessoren (was die Taktabzählung sowieso ein wenig ad absurdum führt) sowieso. Nicht zu letzt noch das Verhalten des Betriebssystems beim Ressourcenzugriff oder Kontextwechseln.
Die einzige Möglichkeit, da die Performance eines Algorithmus' einzuschätzen, ist Erfahrung. In Hochsprache kommt erschwerend hinzu, das man wissen muss, was der Compiler aus dem Code macht (insbesondere bei switch(), denn da haben verschiedene Compiler bei verschiedenen Einstellungen noch verschiedenere Möglichkeiten, ein switch()-Statement in Assembler-Code zu gießen).
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mo 15.05.06 13:57
@Info-Studium: Was da im Bereich der theoretischen Informatik drankommt, ist, wie schnell ein Algorithmus oder eine Operation auf einer Datenstruktur prinzipiell ist.
Beispiel, weils auch öfter mal im Forum kommt: Dynamische Arrays vs. Listen (echte Listen, nicht so ein Array-Verschnitt wie TList)
Aufgabe: Füge n Objekte in die Datenstruktur ein.
Laufzeit bei einem Array: Quadratisch (weil für jede Längenvergrößerung das Array komplett umkopiert werden muss)
Laufzeit bei einer Liste: Linear (weil man einfach nur bei jeder Einfügeoperation ein paar Zeiger umhängen muss)
Die "Einheit", in der die Theoretiker arbeiten, ist nicht ganz klar definiert. Ist auch egal, ob nun "eine" Operation 10 Takte braucht, oder 10.000.000. Hauptsache, man kann die Anzahl der "Takte" durch eine Konstante beschränken. Wenn also in einem kompliziertem Algorithmus eine Stelle kommt wie "wenn die Liste kleiner als 1000 ist, dann sortiere die Liste", dann kann man das als eine Operation ansehen, die prinzipiell genauso viel kostet wie ein Vergleich zweier Zahlen.
Inwiefern genauere Performance-Untersuchungen in der praktischen Informatik drankommen (auch ein Teil des Info-Studiums), kann ich nicht sagen.
_________________ We are, we were and will not be.
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Mo 15.05.06 15:42
hm Gausi das Beispiel war schlecht gewählt.
Quardatisch bei einem Array ist es auf keinem Fall, höchsten O(n) wenn neuer Speicher allokiert werden muss (und somit umkopiert) aber minimal O(1) wenn man immer bei Arrayüberschreitung das neu zu allokierende Array doppelt so groß macht wie vorher.
Bei einer Liste kommt es darauf an, ob das Element vorne augefügt wird O(1) oder hinten O(n) Falls es sich nicht um eine doppelt verkette Liste handelt. Aber prinizpiell kann man sagen, dass das Löschen und Einfügen zusammen O(n) hat, da man entweder O(n) ins Einfügen oder ins Löschen steckt(stecken muss).
Komplexität von Sortieralgorithmen und die untere Schranke beim Sortieren durch vergleichen lernt man im Studium kennen. Also einfach nur den Aufwand für den Alg. selber, nicht für die Operationen. [die werden zwar in "Vergleichen" und "Vertauschen" aufgesplittet, aber WIE es dann der Compiler macht wird nicht besprochen]
Edit: Hab bei dir überlesen, dass du von n Elementen sprichst, ich bin von einem Element fürs Einfügen ausgegangen. Trotzdem kommt es immer auf die Implemenation an, auch da wird es O(n) bei einem Array bleiben, wenn man es richtig macht.
Verdoppelt man die Eibträge in einem Array kommt man auf 2n (da nur 1mal kopiert wird) was O(n) bleibt. Selbst wenn Man die Elemente vorne an die Liste packt braucht man n operationen da aber 2n = O(n) gilt ist es thepretisch gleich schnell. Praktisch wird aber das im Array noch schneller gehen, da wahrscheinlich eine einmalige Neuallokierung mit umkopieren wohl noch schneller ist als jedesmal Speicher für ein Element zu holen. Aber das gehört alles wieder nicht zum Studium.
Das löschen aus einem Array (und dann neu anordnen) dauert auch O(n), kann aber durch Platzhalter auch auf O(1) gedrückt werden, wenn man die aktuellen gelöschen Elemente mitzählt und sollten die n/2 Übersteigen [d.h. mehr gelösche Elemente in dem Array als benutzte) einmal das Array aktualisiert wird. Oder man die neuen Elemente in dise Platzhalter schreibt, da wiederum das Einfügen O(1) dauert.
Hat man genug Speicher kann man also schon das Einfügen und Löschen in einem Array in O(1) hinbekommen, wenn gut genug implementiert.
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
Zuletzt bearbeitet von uall@ogc am Mo 15.05.06 15:52, insgesamt 1-mal bearbeitet
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mo 15.05.06 15:47
Wenn ich ein Array um eins vergrößere, dann muss ich das Array kopieren. Dafür benötige ich O(k) Schritte, k die Größe des Arrays. Füge ich n Elemente nacheinander ein, so brauche ich 1+2+3+4+..+n-viele Schritte. Nach Gauß (also der Mathematiker, nicht ich  ) sind das n*(n+1)/2, was quadratisch ist
Das Einfügen von n Elementen in eine Liste ist dagegen auf jeden Fall linear, weil jeder Einfügeschritt O(1) benötigt.
_________________ We are, we were and will not be.
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Mo 15.05.06 15:54
Hab den Text nochmal editiert, weil ich von 1 Element ausgegangen bin.
Und bei einer Liste wird (üblich) hinten eingefügt, demnach das einfügen auch O(n) dauert (immer durchhangeln)
Durch geschickte Implementierung (wie schon weiter oben geschrieben) kann man aber schon beides ziemlich verbessern.
Je nachdem was man halt gerade will 
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
digi_c
      
Beiträge: 1905
W98, XP
D7 PE, Lazarus, WinAVR
|
Verfasst: Di 16.05.06 10:36
o.k. o.k. das dachte ich mir mit meinen bescheidenen ASM Kenntnissen schon, schade das es keinen Struktogramm/Performance Rechner gibt(!Idee) 
|
|
Robert_G
      
Beiträge: 416
Delphi32 (D2005 PE); Chrome/C# (VS2003 E/A, VS2005)
|
Verfasst: Di 16.05.06 11:12
uall@ogc hat folgendes geschrieben: | Und bei einer Liste wird (üblich) hinten eingefügt, demnach das einfügen auch O(n) dauert (immer durchhangeln)
Durch geschickte Implementierung (wie schon weiter oben geschrieben) kann man aber schon beides ziemlich verbessern. |
Deshalb merkt man sich auch den Tail -> nix O(n) 
|
|
|