String-Klasse als Vorbild gesucht

Vellas

Hi!

@Erhard Henkes:
Von std::string wird vom Indexoperator auch eine Referenz zurückgeliefert.
Ja, das nutzt sie, wie z.B. bei replace, wenn der neue Stringteil größer ist als der alte Stringteil und zusätzlich über die 15 Zeichen hinausgeht.

EDIT: Sorry, falsch verstanden. Aber ja das tut sie. In der insert-Funktion im else if-Zweig. Sollte if ergeben das len+slen+1>bufsize ist dann wird in den else-Zweig gesprungen.

Code-Hacker

Erhard Henkes

Das mit dem char als Rückgabewert des Index-Operators habe ich irgendwann aus dem Buch von Till Jeske C++ nitty-gritty übernommen. Offensichtlich nicht komfortabel. Die Referenz erlaubt die Änderung des Zeichens (bei Breymann steht es richtig).

Interessante Klasse. Puristisch gefällt mir das mit dem FWDBUFFER noch nicht sonderlich, bringt aber vielleicht deutlich Tempo.

Hat jemand ein Test-Programm für eine String-Klasse, mit dem man testen kann, ob EString performanter als std::string ist?

Erhard Henkes

int main()
{
  string   str;
  EString estr;

  const int NMAX = 15;
  int max;
  cout << "Anzahl Schleifendurchlaeufe? ";
  cin >> max;
  clock_t t1,t2;
  double ts, tm=0;

  cout << endl;
  for(int n=0; n<NMAX; ++n)
  {
      t1 = clock(); 
      for( int i=0; i<max;i++) 
      {
        str += "hallo"; //zu messende Aktion 1
      } 
      t2 = clock(); 
      ts = (t2-t1)/static_cast<float>(CLOCKS_PER_SEC); // Zeit in Sekunden.
      cout << "Zeit Aktion 1: " << ts << " sec" << endl;
      tm += ts;   
  }
  tm/=NMAX; 
  cout << "Durchschnitts-Zeit bei Aktion 1: " << tm << " sec" << endl;

  tm=0;
  cout << endl;
  for(int n=0; n<NMAX; ++n)
  {
      t1 = clock();
      for( int i=0; i<max;i++) 
      {
        estr += "hallo"; //zu messende Aktion 2
      } 
      t2 = clock();
      ts = (t2-t1)/static_cast<float>(CLOCKS_PER_SEC);
      cout << "Zeit bei Aktion 2: " << ts << " sec" << endl;
      tm += ts;    
  }
  tm/=NMAX;
  cout << "Durchschnitts-Zeit bei Aktion 2: " << tm << " sec" << endl;

  getch();
}

Anzahl Schleifendurchlaeufe? 10000

Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0.01 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0.011 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0.01 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0 sec
Zeit Aktion 1: 0 sec
Durchschnitts-Zeit bei Aktion 1: 0.00206667 sec

Zeit bei Aktion 2: 0.2 sec
Zeit bei Aktion 2: 0.671 sec
Zeit bei Aktion 2: 1.662 sec
Zeit bei Aktion 2: 3.095 sec
Zeit bei Aktion 2: 4.416 sec
Zeit bei Aktion 2: 5.388 sec
Zeit bei Aktion 2: 6.419 sec
Zeit bei Aktion 2: 7.521 sec
Zeit bei Aktion 2: 9.393 sec
Zeit bei Aktion 2: 9.694 sec
Zeit bei Aktion 2: 11.176 sec
Zeit bei Aktion 2: 12.739 sec
Zeit bei Aktion 2: 13.799 sec
Zeit bei Aktion 2: 14.932 sec
Zeit bei Aktion 2: 16.113 sec
Durchschnitts-Zeit bei Aktion 2: 7.81453 sec

Uups! Untauglich.

Muss an der Funktion EString::insert(...) liegen.

KPC

Erhard Henkes schrieb:

Hat jemand ein Test-Programm für eine String-Klasse, mit dem man testen kann, ob EString performanter als std::string ist?

Für sowas wirst du nie einen aussagekräftigen Test bekommen, denn meistens sind die string Klassen immer auf einen speziellen Fall vorbereitet. So kann zum Beispiel eine Klasse darauf ausgelegt sein besonders kleine Strings zu speichern und allokiert deswegen sehr wenig Speicher.

Eine auf reference counting basierte Klasse wird keine Chance haben, wenn keine gleichen Strings im Programm verwendet werden, usw.

Man müsste also schon SEHR breit gefächerte Testszenarien ausmessen. Für einen Anhaltspunkt kann man natürlich mal eine kleine Messung machen, aber zu genau sollte man die Ergebnisse nicht nehmen.

Erhard Henkes

Was sagst du zu meiner ersten Messung? (siehe oben)

truebool

@code-hacker.
wollte nur mal fragen "wie" du auf die klasse bekommen bist
also auch nua weil ich mal fast die gleiche machen musste in
André Willms ->C++ Programmierung -->Kapitel 12
würd mich halt nua mal interessieren

Erhard Henkes

str += 'a'; //zu messende Aktion 1
estr += 'a'; //zu messende Aktion 2

Anzahl Schleifendurchlaeufe? 10000
...
Durchschnitts-Zeit bei Aktion 1: 0.00206667 sec

Zeit bei Aktion 2: 0.2 sec
Zeit bei Aktion 2: 0.671 sec
Zeit bei Aktion 2: 1.662 sec
Zeit bei Aktion 2: 3.095 sec
Zeit bei Aktion 2: 4.416 sec
Zeit bei Aktion 2: 5.388 sec
Zeit bei Aktion 2: 6.419 sec
Zeit bei Aktion 2: 7.521 sec
Zeit bei Aktion 2: 9.393 sec
Zeit bei Aktion 2: 9.694 sec
Zeit bei Aktion 2: 11.176 sec
Zeit bei Aktion 2: 12.739 sec
Zeit bei Aktion 2: 13.799 sec
Zeit bei Aktion 2: 14.932 sec
Zeit bei Aktion 2: 16.113 sec
Durchschnitts-Zeit bei Aktion 2: 7.81453 sec

Vellas

Hi!

@truebool:
Das ist die Klasse aus "GoTo C++ Programmierung" Kapitel 23.

@Erhard Henkes:
std::string ist ja noch hier und da optimiert und kann auch je nach Compiler anders implementiert sein und optimiert. Und ich glaube die Klasse EString ist sehr sicher, als das man da sicher einiges weglassen könnte um performance zu gewinnen.

Code-Hacker

Erhard Henkes

Selbst bei den einfachen vergleichsoperatoren ist std:string 10 mal schneller:

string   str ="Hallo";
  EString estr ="Hallo";
  bool    retVal;

  retVal = (str > str);   //zu messende Aktion 1
  retVal = (estr > estr); //zu messende Aktion 2

Anzahl Schleifendurchlaeufe? 10000000
Durchschnitts-Zeit bei Aktion 1: 0.0220667 sec
Durchschnitts-Zeit bei Aktion 2: 0.194267 sec

die Klasse EString ist sehr sicher

Übrigens ist ein Fehler in der Klasse EString:

EString estr;
retVal = (estr > estr); // Fehlermeldung bei allen Vergleichsoperatoren!

z.B.:

int main()
{
  EString estr;
  cout << (estr <= estr);
  getch();   
}

das liegt an dem Konstruktor ohne Argument, der string = 0 setzt, siehe:

#include <iostream>
#include <conio.h>
#include <cstring>
using namespace std;

int main()
{
    cout << strcmp(0,0); // Fehlermeldung! 
    getch();
}

Konstruktor ohne Argument:

EString::EString()
{
	len=0;
	bufsize=0;
	string=0; 
}

/*
** Vergleichsoperatoren
*/

bool EString::operator<(const EString &s) const
{return(strcmp(string,s.string)<0);}

bool EString::operator<=(const EString &s) const
{return(strcmp(string,s.string)<=0);}

bool EString::operator==(const EString &s) const
{return(strcmp(string,s.string)==0);}

bool EString::operator!=(const EString &s) const
{return(strcmp(string,s.string)!=0);}

bool EString::operator>=(const EString &s) const
{return(strcmp(string,s.string)>=0);}

bool EString::operator>(const EString &s) const
{return(strcmp(string,s.string)>0);}

Entweder muss man den Konstruktor oder die Vergleichsoperatoren ändern. Man müsste string==0 || s.string==0 abfangen, da strcmp offensichtlich keine Nullzeiger akzeptiert. Leicht zu erreichen.

Wie man sieht, ist die Klasse EString alles andere als performant oder ausgereift!

Vellas

Hi!

@Erhard Henkes:
Mit "die Klasse ist sehr Sicher" meine ich das überall eine Sicherheitsabfrage drin ist bevor irgendetwas gemacht wird. Z.B. beim Indexoperator, dort wird vorher mit assert geprüft ob der Index gültig ist, eine Bereichsprüfung macht auch nur std::string::at.

Naja, das die Klasse nicht an std::string rankommt war eigentlich klar, was solls.

Die Vergleichoperatoren greifen auf strcmp zurück. Würde mich mal interessieren was die std::string-Klasse wesentlich anders macht.

Code-Hacker

Du brauchst doch nur nachsehen, was die anders machen.

groovemaster

Also mir gefällt die String Klasse überhaupt nicht, und die Geschwindigkeitsprobleme ergeben sich aus einigen grundsätzlichen Designfehlern. Nur mal ein paar kleine Verbesserungsvorschläge:
1. Schmeiss die Struktur der nullterminierten C-Strings weg und implementier die Daten der Zeichenkette als ganz normales Array. Die 3 benötigten Member dafür hast du ja. Dann brauchst du auch keine str... Funktionen mehr zu verwenden, die ein Bottleneck der Klasse darstellen. Dafür nimmst du dann die mem... Funktionen, die wesentlich schneller sind. Später lässt sich dann dadurch sogar kinderleicht eine Template basierte Stringklasse entwickeln, mit der man zB auch wchar_t als Zeichentyp nutzen kann. Die einzige str... Funktion die du brauchst, ist strlen (bzw. wcslen oder was auch immer), da es ja auch möglich sein soll ein String Literal bzw C-String zu übergeben. Solltest du deinen String wiederum als C-String brauchen (zB für eine WinAPI Funktion), dann mach es wie std::string und biete dafür eine entsprechende Funktion an (c_str()).
2. Implementier ínsert und add (+=) separat, da das Hinzufügen somit deutlich performanter ist.
3. Verwende für Längenangaben bzgl. eines Speicherbereiches std::size_t.
4.

EString(const char);

const char zu übergeben macht keinen Sinn (bei einigen anderen Funktionen genauso), da der Parameter sowieso als Kopie vorliegt und der ursprüngliche Wert eh nicht verändert werden kann. Was willst du damit erreichen? Das man den Wert auf dem Stack nicht verändert? Wozu?
5. Stell einen ctor mit std::size_t Parameter zur Verfügung um einen entsprechend gross vorreservierten String zu erzeugen, dh

EString s(10);

erzeugt einen String der Länge 0 mit 10 reservierten Zeichen. Das ist praktisch, wenn du genau weisst wie gross dein String maximal wird und somit nur ein mal Speicher reservieren brauchst.
6. Zwinge deiner Klasse im Header nicht den std Namensraum auf und verwende std:: stattdessen.
7. Durch besseres Speicher-Handling und damit einer überarbeiteten insert Funktion lässt sich sicherlich auch noch mal einiges rausholen.

Und um dich jetzt noch ein bisschen zu motivieren , ich hab vor einiger Zeit selbst eine String Klasse für Lernzwecke implementiert (ohne expliziten Prozessor Schnickschnack wie MMX, SSE, etc.), die teilweise schneller ist als die std::string Implementation von MS.

Erhard Henkes

Der Konstruktor ohne Argument ist nicht richtig implementiert. Auch beim Copy-Konstruktor gibt es damit Probleme.

EString s; sollte eher analog erstellt werden wie EString s("");

Man kann die Klasse deutlich(!) beschleunigen, wenn man die Konstante FWDBUFFER erhöht, z.B. auf 100 (oder höher). Dieser Mechanismus kommt mir aber noch irgendwie suspekt vor.

@ groovemaster2002: poste deine Klasse doch mal hier, damit wir sie so richtig zerlegen können.

groovemaster

Erhard Henkes schrieb:

@ groovemaster2002: poste deine Klasse doch mal hier, damit wir sie so richtig zerlegen können

War das ironisch oder ernst gemeint?

Shlo

groovemaster2002 schrieb:

Erhard Henkes schrieb:

@ groovemaster2002: poste deine Klasse doch mal hier, damit wir sie so richtig zerlegen können

War das ironisch oder ernst gemeint?

Eher sarkastisch

DEvent

groovemaster2002 schrieb:

die teilweise schneller ist als die std::string Implementation von MS.

wurde die STL von MS implementiert ?

Shlo

DEvent schrieb:

groovemaster2002 schrieb:

die teilweise schneller ist als die std::string Implementation von MS.

wurde die STL von MS implementiert ?

Es gibt verschiedene Implementierungen, von Microsoft gibt es soweit ich weiß keine. Die Standardbibliothek die mit VC mitgeliefert wird, stamm von Dinkumware.

Vellas

Hi!

goovemaster2002 schrieb:

6. Zwinge deiner Klasse im Header nicht den std Namensraum auf und verwende std:: stattdessen.

Das hat Erhard Henkes so gemacht. Eigentlich ist der namensraum std nur in der CPP-Datei global bekannt gemacht.

Danke für deine Vorschläge, da ich jetzt etwas ferien habe werde ich die Stringklasse mal erneuern. Habe mal die im Stroustrup kurz überflogen, die sah ganz interessant aus. Dort wird der String über den Konstruktor ohne Argument auch mit einem Leerstring initialisiert.

Code-Hacker

Helium

Die Vergleichoperatoren greifen auf strcmp zurück. Würde mich mal interessieren was die std::string-Klasse wesentlich anders macht.

Naja, normalerweise würde ich erstmal die länge der Strings vergleichen (die ja extra gespeichert ist). Wenn die Länge zweier strings verschieden ist, kann der inhalt nicht gleich sein.

Vellas

Hi!

Stimmt.
Außerdem prüft strcmp alle Fälle und nicht nur Gleichheit. Deswegen kann man dort wieder jedes Zeichen nur mit == vergleichen und bei ungleichheit einfach false zurückgeben, ansonsten true.

Code-Hacker