Strings mischen, Algorithmus

[röhrich]

Hast doch Antworten bekommen.
Deine Variante ist die biegerei mit C und C++ Code (nicht C++ typisch) und
Shade of Mine's Version nutzt die Vorteile der C++ Containerklassen.

[Aziz]

Ich schrieb dies in Bezug auf den Beitrag von Jester. Er bleibt mir eine schnellere Variante und/oder eine Erklärung schuldig..

Deine Variante ist die biegerei mit C und C++ Code (nicht C++ typisch) und
Shade of Mine's Version nutzt die Vorteile der C++ Containerklassen.

Ich bin der Meinung, dass meine Variante nur schneller sein kann als irgendein Code, der eine Containerklasse aus der STL verwendet. Außerdem hat Shade Of Mine die Input-Strings bequem in die Vektoren gepusht, und angenommen sie müssen nur zufällig gemischt werden, aber was tun wenn die Strings in der Form existieren wie ich sie am Anfang in meinem Beispiel angegeben habe? In diesem Fall müssen die Strings zuerst geparsed werden und dann erst in den Vektor gepusht werden..

[Jester]

Aziz schrieb:

Ich bin der Meinung, dass meine Variante nur schneller sein kann als irgendein Code, der eine Containerklasse aus der STL verwendet.

Und warum bist Du der Meinung? Weil das andere zu einfach, zu kurz und zu elegant ist? Schnelle Lösungen müssen lang, unleserlich und häßlich sein, oder?

Du schuldest den Beweis, daß Deine Variante schneller ist. Geht natürlich schlecht, weil die beiden nicht das gleiche tun, aber dann ist die Aussage meins ist schneller als Deins nur noch größerer Quatsch.

Abgesehen davon muß ich hier garnichts beweisen. Ich schreibe meinen Code so wie ich ihn will: Kurz und einfach, damit ist er nicht automatisch schnell (A=>B impliziert nicht B=>A), aber er ist deswegen auch nicht automatisch langsam. (Das ist der von Dir hier vertretene Standpunkt gegen den ich mich wehre).

MfG Jester

[röhrich]

Wenn du sowieso mit festen stringlängen arbeitest kann man das auch so machen:
[code]
char *mixer(string &src,char sep,int tco)
{
int le=src.length(),cst=count(src.begin(),src.end(),sep)/tco,tle=le/tco/cst;
char des=new char[le];
le=0;
for(int j=0;j<cst;j++){
for(int i=0;i<tco;i++){
memcpy(des+le,&src[0]+i*tle*cst+jtle,tle);
le+=tle;
}
}
return des;
}
[code]

[röhrich]

Besser nochmal komplett.

char *mixer(string &src,char sep,int tco)
{
int le=src.length(),cst=count(src.begin(),src.end(),sep)/tco,tle=le/tco/cst;
char *des=new char[le];
le=0;
for(int j=0;j<cst;j++){
   for(int i=0;i<tco;i++){
   memcpy(des+le,&src[0]+i*tle*cst+j*tle,tle);
   le+=tle;
   }
}
return des;
}
int main()
{
string a="aaaaaa\nbbbbbb\ncccccc\ndddddd\neeeeee\nffffff\ngggggg\nhhhhhh\niiiiii\n";
cout << mixer(a,'\n',3);
return 0;
}

[Aziz]

Guten Abend!

Jester schrieb:

Und warum bist Du der Meinung? Weil das andere zu einfach, zu kurz und zu elegant ist? Schnelle Lösungen müssen lang, unleserlich und häßlich sein, oder?

Du schuldest den Beweis, daß Deine Variante schneller ist. Geht natürlich schlecht, weil die beiden nicht das gleiche tun, aber dann ist die Aussage meins ist schneller als Deins nur noch größerer Quatsch.

Ok, lassen wir mal für einen Moment das mit dem "kurz, lang, elegant oder hässlich", und wer was beweisen muss.

Stellen wir mal folgendes klar:
Ich habe einen Algorithmus geschrieben der folgende Anforderungen erfüllt:
.) Es sind ein oder mehrere Strings gegeben.
.) Eine Funktion soll diese Strings als Input bekommen und als Output soll ein String ausgegeben werden, der diese Strings in "gemischter Form" beinhaltet.
.) Was bedeutet "gemischte Form"? Nehmen wir an wir haben 3 Papierstapel mit je 100 Blättern. Ich nehme von je einem Stapel in definierter Reihenfolge (Stapel 1, Stapel 2, Stapel 3) ein Blatt Papier und lege sie übereinander auf einem neuen Stapel zusammen. Und das solange bis keine Blätter mehr übrig sind.
Ähnlich soll der Algorithmus arbeiten. Durch ein definierbares Trennungszeichen weiß der Algorithmus wo ein Blatt in einem Stapel (String) anfängt und wo es aufhört (abstrakt betrachtet).
Beispiel: "Das ist ein String"
Trennungszeichen: " " (Leerzeichen)
"Blätter": "Das ", "ist ", "ein ", "String"

Shade Of Mine hat eine Lösung geboten, die nicht alle Anforderungen erfüllt.
Es ist aber ein guter Ansatz, und wer den folgenden Pseudo-Code implementieren würde, wären alle Anforderungen erfüllt:

void MixStrings(string &szDest, const vector<string> &szSources, INT cBreakAt)
{
  //strings parsen und die Teile in vectoren pushen

  //durch die vectoren iterieren und die Teilstrings
  //gemischt in den Zielstring (szDest) einfügen
}

Ich nehme an du würdest das Problem auf diese Weise lösen. Ich gebe zu, dass die Funktion viel leserlicher ist, wenn man sie mit Strings und Vektoren aus der STL implementieren würde. Aber beim besten Willen kann ich mir nicht vorstellen, dass dieser Code schneller sein sollte als meiner. Logisch betrachtet kann das einfach nicht sein. "string" und "vector" sind Klassen, die dynamisch erweitert werden wenn man Elemente hinzufügt. In meinem Code wird nicht ständig dynamisch Speicher angelegt und gelöscht, was die Container-Klassen ganz bestimmt tun müssen wenn sie zu klein sind für weitere Elemente (oder wenn sie initialisiert werden)...Ich tu lediglich kopieren und gleichzeitig parsen.

Jester schrieb:

Abgesehen davon muß ich hier garnichts beweisen. Ich schreibe meinen Code so wie ich ihn will: Kurz und einfach, damit ist er nicht automatisch schnell (A=>B impliziert nicht B=>A), aber er ist deswegen auch nicht automatisch langsam. (Das ist der von Dir hier vertretene Standpunkt gegen den ich mich wehre).

Klar, du brauchst nichts beweisen. Du brauchst aber auch nicht kritisieren ohne zu begründen. Ich hab zwar auch nicht detailliert begründet warum meine Variante schneller sein soll, aber ich dachte das ist für jeden, der das logisch betrachtet ersichtlich. Shade Of Mine hat jedenfalls keinen Einwand gegen meine Behauptung erhoben...

Um welchen Faktor meine Funktion schneller ist als die "STL-Funktion" (die noch noch zu implementieren wäre), lässt sich nur durch Messungen ergründen. Aber dass sie schneller ist, ist meiner Meinung nach nur sicher. Ich hab dir angeboten mich demütig geschlagen zu geben, falls du es schaffst eine schnellere Variante zu schreiben, oder falls du zumindest nachvollziehbar erklären kannst warum meine Variante nicht schneller oder bedeutend schneller sein kann als die STL-Variante. Also ich habe die Anforderungen klar definiert, und mich würde interessieren was du jetzt zu sagen hast.

MfG,
Aziz

[borg]

// es ist bestimmt schneller 'tmp' zu inkrementieren und zu dereferenzieren
      // als dies mit 'pSourcesCpy[i]' zu tun
      tmp = pSourcesCpy[i];

warum das denn?

[KPC]

So würde ich das Ganze lösen, wie schnell das ist hab ich keine Ahnung und jetzt auch keine Lust das zu testen! Wahrscheinlich kann man noch was rausholen wenn man noch ein resize bei szDest aufruft.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef const vector<string> StringVector;

void MixStrings(string &szDest, StringVector &szSources, int cBreakAt) 
{ 
  vector <int> Position(szSources.size());
  bool Finish = false;

  while(!Finish)
  {
	int Index = 0;
	for(StringVector::const_iterator it=szSources.begin(); it != szSources.end(); ++it, ++Index)
	{
		string::size_type Found = (*it).find(cBreakAt, Position[Index]+1);
		if(Found == string::npos)
		{
			Finish = true;
			break;
		}
		szDest.append((*it), Position[Index], Found-Position[Index]+1);

		Position[Index] = Found;
	}
}
}

int main()
{
	vector <string> Src;
	Src.push_back("Weiß ob schneller ");
	Src.push_back("nicht das war ");
	Src.push_back("! !! !!! ");
	string Dest = "";
	MixStrings(Dest, Src, ' ');

	cout << Dest << endl;
}

[Aziz]

borg schrieb:

// es ist bestimmt schneller 'tmp' zu inkrementieren und zu dereferenzieren
      // als dies mit 'pSourcesCpy[i]' zu tun
      tmp = pSourcesCpy[i];

warum das denn?

Weil mehr Maschinen-Code ausgeführt werden muss, wenn ich "*pSourcesCpy[i]" schreibe als wie wenn ich "*tmp" schreibe. Und je weniger Maschinen-Code in der while-Schleife ausgeführt wird, desto schneller ist die Funktion.

KPC schrieb:

So würde ich das Ganze lösen, wie schnell das ist hab ich keine Ahnung und jetzt auch keine Lust das zu testen! Wahrscheinlich kann man noch was rausholen wenn man noch ein resize bei szDest aufruft.

Danke, dass du dir die Zeit genommen hast, diese Funktion zu implementieren. Ich werd mal die Geschwindigkeit beider Varianten testen. Du kannst deine Variante immer noch optimieren. Ich werde die Tests dementsprechend updaten.

[Aziz]

Ich habe jetzt mit dem Profiler von VC++6.0 einen Test durchgeführt:
So sieht die main-Funktion aus:

int main() 
{ 
  vector <string> Src;
  Src.push_back("Weiß ob schneller "); 
  Src.push_back("nicht das war "); 
  Src.push_back("! !! !!! ");
  string Dest = "";

  TCHAR *pSources[] = {"Weiß ob schneller ",
                       "nicht das war ",
                       "! !! !!! "};
  TCHAR pDest[1024] = {0}; //= new TCHAR[];
  for(int i=0; i < 1000; i++)
  {
    MixStrings(Dest, Src, ' ');
    MixStrings(pDest, pSources, 3, ' ');
  }

  //cout << pDest << endl;
  //delete pDest;
  return 0;
}

Und so, die Ergebnisse des Profilers (natürlich nur das Wesentliche):

Func          Func+Child           Hit
        Time   %         Time      %      Count  Function
---------------------------------------------------------
       3,027   9,2       31,983  97,1     1000 MixStrings(class std::basic_string... blabla..) (main.obj)
       0,569   1,7        0,715   2,2     1000 MixStrings(char *,char * * const,unsigned int,int) (main.obj)

[Aziz]

Ok, die for-Schleife war etwas unfair für die Funktion von KCP. Der "Dest"-String muss immer zurückgesetzt werden...

for(int i=0; i < 1000; i++)
  {
    Dest = "";
    MixStrings(Dest, Src, ' ');
    MixStrings(pDest, pSources, 3, ' ');
  }

Und ich liege immer noch ganz oben auf der Bergspitze. Holt mich bitte runter, ich hab Höhenangst!!

Func          Func+Child           Hit
        Time   %         Time      %      Count  Function
---------------------------------------------------------
       5,039  31,1       13,218  81,5     2000 MixStrings(class std::basic_string... blablabla..) (main.obj)
       1,093   6,7        1,409   8,7     2000 MixStrings(char *,char * * const,unsigned int,int) (main.obj)

[Shade Of Mine]

Aziz schrieb:

Weil mehr Maschinen-Code ausgeführt werden muss, wenn ich "*pSourcesCpy[i]" schreibe als wie wenn ich "*tmp" schreibe. Und je weniger Maschinen-Code in der while-Schleife ausgeführt wird, desto schneller ist die Funktion.

Blödsinn.
Ein Compiler kann optimieren.

Danke, dass du dir die Zeit genommen hast, diese Funktion zu implementieren. Ich werd mal die Geschwindigkeit beider Varianten testen. Du kannst deine Variante immer noch optimieren. Ich werde die Tests dementsprechend updaten.

Hier ist mein Code mindestens gleich schnell - wenn er als erstes aufgerufen wird und doppelt so schnell wenn er als 2. aufgerufen wird.

#include <sys/time.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

char* MixStrings(char *pDest, char *pSources[], unsigned iSourceCount, int cBreakAt)
{
  char *tmp = NULL;
  char **pSourcesCpy = new char *[iSourceCount];

  if( !pSourcesCpy )
    return NULL;

  memcpy(pSourcesCpy, pSources, iSourceCount*sizeof(char*));

  int i;
  int allPtrs;
  do
  {
    allPtrs = 0; // reset
    for(i=0; i < iSourceCount; ++i)
    {
      // es ist bestimmt schneller 'tmp' zu inkrementieren und zu dereferenzieren
      // als dies mit 'pSourcesCpy[i]' zu tun
      tmp = pSourcesCpy[i];
      while( *tmp ) // this 'while' will exit if the end of a string is reached
      {
        if( (*pDest = *tmp) == cBreakAt )
        {
          ++tmp;   // cBreakAt found; point to next character
          ++pDest;
          break;
        }
        ++tmp;
        ++pDest;
      }
      pSourcesCpy[i] = tmp;
      // the outer while-loop will continue as long as
      // their is a pointer that doesn't point to the NULL character
      allPtrs |= *tmp;
    }

  }while( allPtrs );

  delete[] pSourcesCpy;
  return pDest;
}

void doit(string& out, char delim, vector<string> const& in)
{
  vector<int> sources(in.size());

  bool allFinished;
  do
  {
    allFinished=true;
    for(int i=0; i<in.size(); ++i)
    {
      if(sources[i]==in[i].size()) continue;
      while(in[i][sources[i]]!=delim)
        out+=in[i][sources[i]++];
      out+=delim;
      ++sources[i];
      allFinished=false;

    }
  } while(allFinished);
}

unsigned foo()
{
  timeval start, ende;
  char* stapel1="11111\n100 mal";
  char* stapel2="22222\n100 mal";
  char* stapel3="33333\n100 mal";  
  char* stapels[3];
  stapels[0]=new char[5*100+10];
  memcpy(stapels[0], stapel1, 5*100+10);
  stapels[1]=new char[5*100+10];
  memcpy(stapels[1], stapel2, 5*100+10);
  stapels[2]=new char[5*100+10];
  memcpy(stapels[2], stapel3, 5*100+10);

  char* buffer=new char[strlen(stapel1)+strlen(stapel2)+strlen(stapel3)+1];
  gettimeofday(&start, 0);
  MixStrings(buffer, stapels, 3, '\n');
  gettimeofday(&ende, 0);
 delete [] buffer;

  delete[]stapels[0];
  delete[]stapels[1];
  delete[]stapels[2];

  return ende.tv_usec-start.tv_usec;
}

unsigned foo2()
{
  timeval start, ende;

    vector<string> stapels;
    stapels.push_back("11111\n100 mal");
    stapels.push_back("22222\n100 mal");
    stapels.push_back("33333\n100 mal");
  {
    string out;
    out.resize(100*3*6);
  gettimeofday(&start, 0);

    doit(out, '\n', stapels);
  gettimeofday(&ende, 0);
  }

  return ende.tv_usec-start.tv_usec;
}

int main()
{
  cout<<"Aziz:  "<<foo()<<'\n';
  cout<<"Shade: "<<foo2()<<'\n';
}

Also: STL Code muss nicht langsamer sein.
Ich habe das jetzt nur schnell zusammen ge'hackt' - und einfach deinen Algo übernommen

Die Zeichenketten beinhalten 100 mal das Token 11111\n

getestet unter Linux 2.4.22 mit g++ 3.3.1 mit Optimierung -O3

[Aziz]

Ich hab versucht deinen Code mit VisualC++ 6.0 zu kompilieren, aber er kann diesen time-Header nicht inkludieren (<sys/time.h>)...

Hab aber mit deiner Funktion den gleichen Test gemacht, wie ich ihn mit der Funktion von KPC gemacht habe. Entweder spinnt der Profiler, oder ich weiß nicht. Deine Funktion ist zwar etwas schneller als die von KPC aber trotzdem sehr langsam im Vergleich zu meiner...

[nman]

Aziz schrieb:

Ich hab versucht deinen Code mit VisualC++ 6.0 zu kompilieren, aber er kann diesen time-Header nicht inkludieren (<sys/time.h>)...

Ist ja auch ein POSIX-Header.

Hab aber mit deiner Funktion den gleichen Test gemacht, wie ich ihn mit der Funktion von KPC gemacht habe. Entweder spinnt der Profiler, oder ich weiß nicht. Deine Funktion ist zwar etwas schneller als die von KPC aber trotzdem sehr langsam im Vergleich zu meiner...

Der VC++ hat eine legendär schlechte STL-Implementierung, selbst schuld wenn Du die verwendest - ohne nachgemessen zu haben wage ich einfach mal zu behaupten dass die Resultate mit STLport andere wären.

[Auswerter]

Test 1000000 Durchläufe:

Aziz: 0,651 sec
Shade: 2,574 sec
Röhrich: 1,181 sec
KPC: 1,993 sec

Athlon xp 2400
w2k
512 MB RAM
BCB 6 Enterprise

[Aziz]

nman schrieb:

Hab aber mit deiner Funktion den gleichen Test gemacht, wie ich ihn mit der Funktion von KPC gemacht habe. Entweder spinnt der Profiler, oder ich weiß nicht. Deine Funktion ist zwar etwas schneller als die von KPC aber trotzdem sehr langsam im Vergleich zu meiner...

Der VC++ hat eine legendär schlechte STL-Implementierung, selbst schuld wenn Du die verwendest - ohne nachgemessen zu haben wage ich einfach mal zu behaupten dass die Resultate mit STLport andere wären.

Berechtigter Einwand

[borg]

Weil mehr Maschinen-Code ausgeführt werden muss, wenn ich "*pSourcesCpy[i]" schreibe als wie wenn ich "*tmp" schreibe. Und je weniger Maschinen-Code in der while-Schleife ausgeführt wird, desto schneller ist die Funktion.

Das ist sache des Compilers, mit sowas musst du dich nicht rumschlagen.