Doppelte (bzw. mehrfach) Vorkommende Leerzeichen in std::string löschen?

Noch einmal wow, die Funktion von Michael E. ist weitaus schneller als meine eigene. Vielen, vielen Dank euch allen!!!

... oder doch nicht? Wenn ich das, was Michael E. geschrieben hat, in eine Funktion packe und dann mit meiner Funktion vergleiche, ist meine schneller. Ich verstehe die Welt nicht mehr!

EOP

Diesmal etwas, das funktioniert:

string str = "a  b    c     d e  f   g  ";
size_t pos = 0;

while( (pos = str.find( "  ", pos )) != string::npos )
	str.erase( pos, 1 );

SeppJ

Zeig doch mal, wie du deine Zeitmessungen machst.

Noob Otto schrieb:

... oder doch nicht? Wenn ich das, was Michael E. geschrieben hat, in eine Funktion packe und dann mit meiner Funktion vergleiche, ist meine schneller. Ich verstehe die Welt nicht mehr!

DAS ist am schnellsten

#include <iostream>
#include <string>
using namespace std;

void remove_spc (char *s) {
   char *t = s;
   char l = 0;
   while (*s) {
      if (*s != ' ' || l != ' ')
         *t++ = *s;
      l = *s++;
   }
   *t = 0;
}

int main (void)  {
   string a = "a  b    c     d e  f   g  ";
   char *p = (char*)a.c_str();
   remove_spc (p);
   a = p;
   cout << a;
}

Michael E.

Da wäre ich wirklich mal auf ein Benchmark gespannt Denn mein Code macht im Prinzip nichts anderes, aber ich denke, die Standardalgorithmen werden sehr gut auf den jeweiligen Compiler hinoptimiert sein.

Next Generation Hacker schrieb:

DAS ist am schnellsten
Viel Mist

In nem C++-Programm ein C-cast -> wenn dann const_cast!
Ist das echt böse! Du verändeeerst einen (nicht zu Unrecht) privaten Member, ohne auf andere Spezialitäten Rücksicht zu nehmen. z.B.
Du veränderst die Länge des strings!!! Woher weißt du, dass nicht intern eine Länge mitgespeichert wird?!?

Du machst zwar später eine Zuweisung - aber muss ja nicht immer hinhauen...
Lass die string-Klasse implizit geshared sein (k.A. wie der deutsche Begriff dafür ist...).
Da wird der data-pointer einfach ins neue Objekt gesetzt, eine Kopie des Arrays findet erst satt, wenn das Objekt über die public-Funktionen verändert wird. Deine Methode verhindert ein korrektes Handling dieses Mechanismus!!!

doIt( const std::string& str) {
    boeseFktDieStrAendert( (char*)str.c_str() );
}

Release + Optimieruzngen kompilieren

Michael E. schrieb:

Da wäre ich wirklich mal auf ein Benchmark gespannt

#include <iostream>
#include <string>
#include <algorithm>
#include <windows.h>
using namespace std;

void remove_spc (char *s) {
   char *t = s;
   char l = 0;
   while (*s) {
      if (*s != ' ' || l != ' ')
         *t++ = *s;
      l = *s++;
   }
   *t = 0;
}

char *hacker()  {
   static char a[100];
   strcpy (a, "a  b    c     d e  f   g  ");
   remove_spc (a);
   return a;
}

bool isDoubleSpace(char first, char second)
{
    return first == second && second == ' ';
}

string michael()
{
    string foo = "a  b    c     d e  f   g  ";
    string::iterator newEnd = unique(foo.begin(), foo.end(), isDoubleSpace);
    foo.resize(newEnd - foo.begin());
    return foo;
}

int main () {
   UINT32 t1, t2;
#define COUNT 1000000   

   t1 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      hacker();
   t1 = GetTickCount() - t1;

   t2 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      michael();
   t2 = GetTickCount() - t2;

   cout << t1 << endl;
   cout << t2 << endl;
}

Visual Studio, Release:
Hacker 141 ms
Michael 780 ms

Visual Studio, Debug:
Hacker 858 ms
Michael 26364 ms

freaky

Next Generation Hacker schrieb:

Visual Studio, Debug:
Hacker 858 ms
Michael 26364 ms

26Sekunden? Was hast du solange im Debug getrieben?

volkard

Iteratorchecks auch im Release ausmachen.

Michael E.

Na wir wollen doch fair bleiben und deiner Version auch mal das Erzeugen eines std::strings beibringen (so wie es gefordert war):

#include <iostream>
#include <string>
#include <algorithm>
#include <windows.h>
using namespace std;

void remove_spc (char *s) {
   char *t = s;
   char l = 0;
   while (*s) {
      if (*s != ' ' || l != ' ')
         *t++ = *s;
      l = *s++;
   }
   *t = 0;
}

string hacker()  {
	string a = "a  b    c     d e  f   g  ";
	char* p = (char*)a.c_str();
   remove_spc (p);
   a = p;
   return a;
}

bool isDoubleSpace(char first, char second)
{
    return first == second && second == ' ';
}

string michael()
{
    string foo = "a  b    c     d e  f   g  ";
    string::iterator newEnd = unique(foo.begin(), foo.end(), isDoubleSpace);
    foo.resize(newEnd - foo.begin());
    return foo;
}

int main () {
   UINT32 t1, t2;
#define COUNT 1000000  

   t1 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      hacker();
   t1 = GetTickCount() - t1;

   t2 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      michael();
   t2 = GetTickCount() - t2;

   cout << t1 << endl;
   cout << t2 << endl;
}

Ergebnis (VS 2008 Release, volle Optimierung):
687 (deins) gegen 579 (meins)

Michael E. schrieb:

Na wir wollen doch fair bleiben und deiner Version auch mal das Erzeugen eines std::strings beibringen (so wie es gefordert war):
...
Ergebnis (VS 2008 Release, volle Optimierung):
687 (deins) gegen 579 (meins)

Und die Moral von der Geschicht: Wenns schnell sein soll, nimm std::string nicht.

life

Next Generation Hacker schrieb:

Und die Moral von der Geschicht: Wenns schnell sein soll, nimm std::string nicht.

#define _SECURE_SCL 0

#include <iostream>
#include <string>
#include <algorithm>
#include <windows.h>
using namespace std;

void remove_spc (char *s) {
   char *t = s;
   char l = 0;
   while (*s) {
      if (*s != ' ' || l != ' ')
         *t++ = *s;
      l = *s++;
   }
   *t = 0;
}

char *hacker()  {
   char* a = new char[100];
   strcpy (a, "a  b    c     d e  f   g  ");
   remove_spc (a);
   return a;
}

bool isDoubleSpace(char first, char second)
{
    return first == second && second == ' ';
}

string michael()
{
    string foo = "a  b    c     d e  f   g  ";
    string::iterator newEnd = unique(foo.begin(), foo.end(), isDoubleSpace);
    foo.resize(newEnd - foo.begin());
    return foo;
}

int main () {
   UINT32 t1, t2;
#define COUNT 1000000  

   t1 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      hacker();
   t1 = GetTickCount() - t1;

   t2 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      michael();
   t2 = GetTickCount() - t2;

   cout << t1 << endl;
   cout << t2 << endl;
}

Hacker 266ms
Michael 327ms

Michael E.

Ich warte aber definitiv lieber ne Sekunde bei der Ausführung als mich wochenlang bei der Entwicklung mit rohen char-Arrays rumzuplagen :p

volkard

[quote="life"]...[/cpp]
Speicherloch?

life schrieb:

[cpp]
#define _SECURE_SCL 0

[/cpp]
Ja!

for (int s=0; s<COUNT; s++)
      delete hacker();

Kannste damit nochmal messen?

life

Mit delete[] braucht er nur noch ~202ms. Da müsste man sich vlt mal den asm code anschauen..

Michael E. schrieb:

Ich warte aber definitiv lieber ne Sekunde bei der Ausführung als mich wochenlang bei der Entwicklung mit rohen char-Arrays rumzuplagen :p

Sowas hört man sonst nur von Java-Programmierern.

volkard

volkard schrieb:

for (int s=0; s<COUNT; s++)
      delete hacker();

Volkard meinte bestimmt

for (int s=0; s<COUNT; s++)
      delete[] hacker();

Macht aber vermutlich keinen Fehler auf MSVC. Nett, daß delete so schnell ist.

life

volkard schrieb:

Nett, daß delete so schnell ist.

So schnell, dass die Ausführung der Anweisung sogar Zeit einspart anstatt welche zu verbrauchen?