Autor Beitrag
Matg40
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 52



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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

ausblenden 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

ausblenden Delphi-Quelltext
1:
2:
3:
4:
asm
    MOV EAX, DWORD PTR [A]
    ADD DWORD PTR [A], EAX
end;


oder

ausblenden 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 user profile iconChristian 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 4373

Ubuntu 7.10 "Gutsy Gibbon"

BeitragVerfasst: Mo 15.05.06 13:36 
user profile icondigi_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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 :mrgreen:) 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 416


Delphi32 (D2005 PE); Chrome/C# (VS2003 E/A, VS2005)
BeitragVerfasst: Di 16.05.06 11:12 
user profile iconuall@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) ;)