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

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?

volkard

life schrieb:

volkard schrieb:

Nett, daß delete so schnell ist.

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

Cache-Effekte, hoffe ich. Oder der Funny MSVC hat wiedermal endeckt, daß ein unbedingtes new/delete-Paar mit nur Drinnenrumschreiben ohne Ergebnis da ist, und hat es wegoptimiert.

Wie wärs mit einer trivialen Lösung:

void remove_c ( string& s, char c ) {
	unsigned i, j, k, n;
	k = n = s.size();
	for ( i = 0, j = 0; i < k; i++ ) {
		if ( s[i] != c )
			s[j] = s[i], j++;
		else
			n--;
	}
	if ( k != n )
		s.resize ( n );
}

int main() {
	string s = " B en c h m ark - th is, b ro t he r! ";
	remove_c ( s, ' ' );
	cout << s << endl;
	return 0;
}

Gruß,
B.B.

Michael E.

Naja, erstens löschst du alle Leerzeichen und nicht, wie gefordert, alle doppelten Leerzeichen. Zweitens ist dein Algorithmus im Prinzip gleich den anderen vorgestellten Lösungen und drittens hast du die komplizierteste Darstellung

Blue-Tiger

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!

Da machst du ziemlich sicher was falsch, kannst uns mal zeigen wie du misst?

@ Big Brother & N.G. Hacker:
schaut euch doch mal an was std::unique macht bevor ihr eure eigenen Implementierungen davon schreibt

unskilled

btw:
hat eigtl keiner mitbekommen, dass der code von blue irgendwas da oben nen fehler enthält? ^^
s.erase(newEnd, s.begin());
sieht nicht wirklich richtig aus

bb

Blue-Tiger schrieb:

@ Big Brother & N.G. Hacker:
schaut euch doch mal an was std::unique macht bevor ihr eure eigenen Implementierungen davon schreibt

Die Lösung von Michael E. ist die beste und schnellste, wenn man mit std::string arbeiten muss. Schneller gehts nur mit char[], also völlig ohne std::string. Kann man std::unique auf char[] anwenden?

Michael E.

Klar. Das ist ja das schöne an den generischen Implementierungen:

char foo[20];
unique(foo, foo + 20);

Nexus

Next Generation Hacker schrieb:

Kann man std::unique auf char[] anwenden?

Ja, denn die STL-Algorithmen arbeiten auf Iteratorenbasis. Dabei ist egal, wohin der Iterator zeigt und was für einen Typen er hat, sofern er die erforderten Konzepte (z.B. Random Access) unterstützt. char* kann auch als Iterator eingesetzt werden, d.h. man übergibt std::unique() zwei Zeiger auf Beginn und Ende der Sequenz. Dafür brauchts nicht einmal eine Nullterminierung.