AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Warum delphi lahmer als c++?

Ein Thema von jmd anders · begonnen am 14. Dez 2006 · letzter Beitrag vom 20. Dez 2006
Antwort Antwort
Seite 4 von 4   « Erste     234   
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#31

Re: Warum delphi lahmer als c++?

  Alt 19. Dez 2006, 13:31
Zitat von Olli:
Mehr Code bedeutet auch, daß es länger dauert ihn auszuführen (es sei denn irgendwelche Schleifen wurden linearisiert, was durchaus vorkommen kann).

Nee.

Gegenbeispiel:
Boyer-Moore Pattern Matching (ca. 30 Zeilen) vs. naives Suchen (3 Zeilen)... Boyer-Moore ist viel viel schneller.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Olli
(Gast)

n/a Beiträge
 
#32

Re: Warum delphi lahmer als c++?

  Alt 19. Dez 2006, 13:41
Zitat von alzaimar:
Gegenbeispiel:
Boyer-Moore Pattern Matching (ca. 30 Zeilen) vs. naives Suchen (3 Zeilen)... Boyer-Moore ist viel viel schneller.
Wie funzt denn "naives Suchen" nach alzaimar in 3 Zeilen? Lasse mich ja gern belehren, aber ich habe ja nicht ohne Grund Schleifen ausgeklammert. Und der Umkehrschluß ist natürlich augenfällig. Wenn innerhalb einer Schleife eine Anweisung steht und die Schleife aber eine Million Male aufgerufen wird, ist die Schleife logischerweise langsamer als eine Schleife mit 10 Anweisungen die nur 1000mal ausgeführt wird (unter der Annahme alle Anweisungen kosten gleichviel Zeit). Also bitte mehr Details. Ausnahmsweise bezog sich meine Angabe nämlich nicht auf "mehr" im Sinne von Dateigröße

Achso: "Zeilen" in HLLs zu vergleichen und daraus die Codelänge welche ausgeführt wird abzuleiten ist etwas gewagt

Nachtrag: Hah, ich glaube ich weiß woher das Mißverständnis rührt. Vermutlich wegen meiner Erwähnung der Linearisierung, richtig? Das ist natürlich ein Feature des Binärcodes und beeinflußt damit die Größe der Datei. Aber das "mehr" war wirklich auf die Ausführung gemünzt.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#33

Re: Warum delphi lahmer als c++?

  Alt 19. Dez 2006, 13:55
Zitat von Olli:
Zitat von alzaimar:
Gegenbeispiel:
Boyer-Moore Pattern Matching (ca. 30 Zeilen) vs. naives Suchen (3 Zeilen)... Boyer-Moore ist viel viel schneller.
Wie funzt denn "naives Suchen" nach alzaimar in 3 Zeilen?
Z.B. so (Suche die 'Needle' im 'Haystack'):
Delphi-Quellcode:
For i:=1 to length (Haystack)-Length(Needle)+1 do
  For j:=1 to Length (Needle) do
    If Haystack[i+j-1] = Needle[j] Then
      Found := True;
Entschuldigung, sind 4 Zeilen. In C, Fortran, ASM etc. ist der Code nicht wesentlich komplexer.

"Naives Suchen" (oder Brute Force) ist eine gängige Bezeichung für dieses Verfahren. Ein Weiteres nennt sich übrigens "Not so naive".

Hier z.B. ein Pattern-Matching ("Reverse-Factor") der einem die Kinnlade runterklappen lässt , die Implementierung einer Graph-Klasse ist noch nichtmal dabei)... Aber schnell ist er trotzdem:
(Aus "Charras & Lecroq, Exact String Matching Algorithms")
Code:
void buildSuffixAutomaton(char *x, int m, Graph aut) {
   int i, art, init, last, p, q, r;
   char c;
 
   init = getInitial(aut);
   art = newVertex(aut);
   setSuffixLink(aut, init, art);
   last = init;
   for (i = 0; i < m; ++i) {
      c = x[i];
      p = last;
      q = newVertex(aut);
      setLength(aut, q, getLength(aut, p) + 1);
      setPosition(aut, q, getPosition(aut, p) + 1);
      while (p != init &&
             getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, p, c, q);
         setShift(aut, p, c, getPosition(aut, q) -
                             getPosition(aut, p) - 1);
         p = getSuffixLink(aut, p);
      }
      if (getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, init, c, q);
         setShift(aut, init, c,
                  getPosition(aut, q) -
                  getPosition(aut, init) - 1);
         setSuffixLink(aut, q, init);
      }
      else
         if (getLength(aut, p) + 1 ==
             getLength(aut, getTarget(aut, p, c)))
            setSuffixLink(aut, q, getTarget(aut, p, c));
         else {
            r = newVertex(aut);
            copyVertex(aut, r, getTarget(aut, p, c));
            setLength(aut, r, getLength(aut, p) + 1);
            setSuffixLink(aut, getTarget(aut, p, c), r);
            setSuffixLink(aut, q, r);
            while (p != art &&
                   getLength(aut, getTarget(aut, p, c)) >=
                   getLength(aut, r)) {
               setShift(aut, p, c,
                        getPosition(aut,
                                    getTarget(aut, p, c)) -
                        getPosition(aut, p) - 1);
               setTarget(aut, p, c, r);
               p = getSuffixLink(aut, p);
            }
         }
      last = q;
   }
   setTerminal(aut, last);
   while (last != init) {
      last = getSuffixLink(aut, last);
      setTerminal(aut, last);
   }
}


char *reverse(char *x, int m) {
   char *xR;
   int i;
 
   xR = (char *)malloc((m + 1)*sizeof(char));
   for (i = 0; i < m; ++i)
      xR[i] = x[m - 1 - i];
   xR[m] = '\0';
   return(xR);
}
 
 
int RF(char *x, int m, char *y, int n) {
   int i, j, shift, period, init, state;
   Graph aut;
   char *xR;
 
   /* Preprocessing */
   aut = newSuffixAutomaton(2*(m + 2), 2*(m + 2)*ASIZE);
   xR = reverse(x, m);
   buildSuffixAutomaton(xR, m, aut);
   init = getInitial(aut);
   period = m;
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      i = m - 1;
      state = init;
      shift = m;
      while (i + j >= 0 &&
             getTarget(aut, state, y[i + j]) !=
             UNDEFINED) {
         state = getTarget(aut, state, y[i + j]);
         if (isTerminal(aut, state)) {
            period = shift;
            shift = i;
         }
         --i;
      }
      if (i < 0) {
         OUTPUT(j);
         shift = period;
      }
      j += shift;
   }
}
Ich habe tatsächlich überlesen, das Du Schleifen explizit ausklammerst...

Egal: Natürlich benötigen 10000 Op-codes i.R. länger als 3
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Der_Unwissende

Registriert seit: 13. Dez 2003
Ort: Berlin
1.756 Beiträge
 
#34

Re: Warum delphi lahmer als c++?

  Alt 19. Dez 2006, 14:00
Zitat von Olli:
...(unter der Annahme alle Anweisungen kosten gleichviel Zeit).
Was ja an sich schon eine viel zu allgemeine Annahme ist. Einfaches Beispiel das mir einfallen würde wäre die Multiplikation von Matrizen. Hat man mehrere Matrizen, die miteinander multipliziert werden, so würde man naiv einfach die in der Reihenfolge Multiplizieren, in der sie übergeben werden. Jetzt ist die Multiplikation aber Assoziativ, man kann also hier (bei geeigneten Matrizen) die Reihenfolge der Multiplikation verändern, also einfach einzelne Produkte vor anderen bilden. Das möchte ich jetzt gar nicht weiter ausführen, denke alzaimar und Olli kennen die unterschiedliche Laufzeit (andere natürlich auch!, die die sie nicht kennen finden sicher schnell was in der Theoretischen Informatik dazu). Jedenfalls wird hier vor sortiert, indem die Dimensionen der Matrizen verglichen wird (mehr Anweisungen als die naive Multiplikation), da sich aber die Anzahl von Multiplikationen und Additionen verändert, kann somit eine Optimierung vom Programmierer erreicht werden.

Wichtig ist es natürlich zu beachten, dass eben nicht jeder Befehl gleich lange dauert (@Olli ich denke das ist Dir schon klar!). Nur kostet jede Division doch immer noch >> mehr als eine einfache Addition.

Aber klar, unter der Einfachen Annahme, dass man eine unterschiedliche Anzahl von gleich teuren Befehlen hat, werden natürlich die geringeren Kosten günstiger sein
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#35

Re: Warum delphi lahmer als c++?

  Alt 19. Dez 2006, 14:07
Unterm Strich bleibt eine (banale Erkenntnis):

Das Verfahren ist wichtig, nicht die Sprache.

In der untersten Ebene sind die optimierenden Compiler/Sprachen besser eeignet, also Hochsprachen.

Bernhard Geyer hat schon treffend angemerkt, das auch bei hochoptimierten Elops (Pos, StrCopy etc.) eine normale Anwendung nur um ein paar Prozente profitiert.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Olli
(Gast)

n/a Beiträge
 
#36

Re: Warum delphi lahmer als c++?

  Alt 20. Dez 2006, 03:19
Zitat von Der_Unwissende:
Wichtig ist es natürlich zu beachten, dass eben nicht jeder Befehl gleich lange dauert (@Olli ich denke das ist Dir schon klar!). Nur kostet jede Division doch immer noch >> mehr als eine einfache Addition.
Nunja, da ich beruflich programmiere und Reverse Engineering betreibe ... jupp, ist mir klar. Ich wollte dies nur als theoretische Annahme einführen damit die Komplexität nicht unnötig ansteigt. Das unterscheidet bekanntlich Modelle von der realen Welt

Das Beispiel von überladenen Operatoren und Matrizen (Vektor und/oder Skalarprodukt) ist hier ein gutes Beispiel. Der Code ist intuitiv und supergut lesbar, aber die Operatoren selber sind auch zu implementieren. Sie müssen allerdings nicht für den Programmierer sichtbar sein. Ergo kann eine solche simple Zeile HLL-Code gut und gern ein kleines C-Programm in der Komplexität übertreffen ohne mehr Zeilen zu haben.

Zitat von alzaimar:
Delphi-Quellcode:
For i:=1 to length (Haystack)-Length(Needle)+1 do
  For j:=1 to Length (Needle) do
    If Haystack[i+j-1] = Needle[j] Then
      Found := True;
Wo ist die Abbruchbedingung? (Scherz!)

Zitat von alzaimar:
Code:
void buildSuffixAutomaton(char *x, int m, Graph aut) {
   int i, art, init, last, p, q, r;
   char c;
 
   init = getInitial(aut);
   art = newVertex(aut);
   setSuffixLink(aut, init, art);
   last = init;
   for (i = 0; i < m; ++i) {
      c = x[i];
      p = last;
      q = newVertex(aut);
      setLength(aut, q, getLength(aut, p) + 1);
      setPosition(aut, q, getPosition(aut, p) + 1);
      while (p != init &amp;&amp;
             getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, p, c, q);
         setShift(aut, p, c, getPosition(aut, q) -
                             getPosition(aut, p) - 1);
         p = getSuffixLink(aut, p);
      }
      if (getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, init, c, q);
         setShift(aut, init, c,
                  getPosition(aut, q) -
                  getPosition(aut, init) - 1);
         setSuffixLink(aut, q, init);
      }
      else
         if (getLength(aut, p) + 1 ==
             getLength(aut, getTarget(aut, p, c)))
            setSuffixLink(aut, q, getTarget(aut, p, c));
         else {
            r = newVertex(aut);
            copyVertex(aut, r, getTarget(aut, p, c));
            setLength(aut, r, getLength(aut, p) + 1);
            setSuffixLink(aut, getTarget(aut, p, c), r);
            setSuffixLink(aut, q, r);
            while (p != art &amp;&amp;
                   getLength(aut, getTarget(aut, p, c)) >=
                   getLength(aut, r)) {
               setShift(aut, p, c,
                        getPosition(aut,
                                    getTarget(aut, p, c)) -
                        getPosition(aut, p) - 1);
               setTarget(aut, p, c, r);
               p = getSuffixLink(aut, p);
            }
         }
      last = q;
   }
   setTerminal(aut, last);
   while (last != init) {
      last = getSuffixLink(aut, last);
      setTerminal(aut, last);
   }
}
Igittigitt. Variablen nicht initialisiert. Variablen außerhalb des allernötigsten Bereichs deklariert *brrr*

Nee, aber mal ernst, uns ist allen klar warum sowas schneller geht. Und das ist nicht wegen der fehlenden Abbruchbedingung ...

Zitat von alzaimar:
Egal: Natürlich benötigen 10000 Op-codes i.R. länger als 3
Jupp, mein Punkt war halt, daß man bei einer Schleife ja die Instruktionen innerhalb der Schleife pro Durchlauf einmal ausführen muß. Ergo dürfte die Binärdatei kleiner sein als bei deinem Algo, jedoch werden netto mehr Instruktionen vom Prozessor ausgeführt.

Ich muß echt an meinem Ausdruck feilen. Zu lange im Ausland

Gruß aus dem (nicht vom Internet abgeschnittenen) Reykjavik,
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#37

Re: Warum delphi lahmer als c++?

  Alt 20. Dez 2006, 07:54
Zitat von Olli:
Zitat von alzaimar:
Code:
void buildSuffixAutomaton(char *x, int m, Graph aut) ...
Igittigitt. Variablen nicht initialisiert. Variablen außerhalb des allernötigsten Bereichs deklariert *brrr*
Nicht so schnell schießen (welche Variablen sind denn nicht initialisiert?), lieber nochmals den Code checken oder direkt bei Charras & Lecroq beschweren.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Olli
(Gast)

n/a Beiträge
 
#38

Re: Warum delphi lahmer als c++?

  Alt 20. Dez 2006, 13:10
Zitat von alzaimar:
Zitat von Olli:
Zitat von alzaimar:
Code:
void buildSuffixAutomaton(char *x, int m, Graph aut) ...
Igittigitt. Variablen nicht initialisiert. Variablen außerhalb des allernötigsten Bereichs deklariert *brrr*
Nicht so schnell schießen (welche Variablen sind denn nicht initialisiert?), lieber nochmals den Code checken oder direkt bei Charras & Lecroq beschweren.
Also, ich initialisiere Variablen wenn möglich immer direkt bei der Deklaration und deklariere sie so spät wie möglich (i.e. so kurz wie möglich vor der ersten Benutzung). Das wird von C++ und C99 unterstützt.

Diese Methode hat mehrere Vorteile:
1. Wenn es sich bei der Variablen um ein Stackobjekt handelt, hast du den Aufwand des ctor-Aufrufs erst ab der Zeile mit der Deklaration&Initialisierung. Bei komplexen Objekten kann das einen Unterschied machen.
2. Variablen haben immer einen Standardwert.
3. Baut man zuvor eine Verzweigung (manche benutzen gern goto *würg*) ein, kann nicht hinter der Verzweigung die Variable benutzt werden (wenn sie nur im nächstnötigen Scope liegt) oder zumindest nicht uninitialisiert benutzt werden.

Das sind sozusagen kostenlose Codeverbesserungen die als "Stilmittel" automatisch bestimmte durchaus gängige Fehler vermeiden. Aber keine Angst, ich kenne auch Code der sich partout nicht dran hält und Menschen die noch partout C92 programmieren wollen

War also nicht so ernst gemeint wie du es scheinbar aufgefaßt hast
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#39

Re: Warum delphi lahmer als c++?

  Alt 20. Dez 2006, 19:13
Zitat von Olli:
... von C++ und C99 ... die noch partout C92 programmieren wollen ...
Ich kenn nur C64

Ach, und Code auf Seiten von Universitäten sind meist interessant und selten schnell ('Optimizing is beyond the scope of this article'). Die haben's eben nicht drauf.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 4 von 4   « Erste     234   


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:31 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz