Strings mischen, Algorithmus

Aziz

Hallo allerseits!

Ich hab' einen Algorithmus entworfen, der mehrere Strings zerteilen und gemischt zusammenfügen kann.

Ein Demonstrations-Beispiel:

Input 1: "------\n++++++\naaaaaa\n"
Input 2: "######\n//////\nbbbbbb\n"
Ausgabe: "------\n######\n++++++\n//////\naaaaa\nbbbbbb\n"

Im Beispiel repräsentieren 'Input 1' und 'Input 2' "Stapel von Karten", wobei die NewLine-Zeichen die einzelnen "Karten" im jeweiligen Stapel trennen.
Der Algorithmus nimmt aus je einem Stapel (String) je eine Karte (zerteilter String) und legt sie auf einem großen Stapel (Resultat) zusammen.
Der Algorithmus mischt sozusagen die Strings so ähnlich wie ein Kartenmischer zwei Stapel von Karten mischen würde. Der Unterschied ist, dass der Algo beliebig viele Strings aufnehmen und genau mischen kann; der Mensch aber, kann höchstens zwei Stapel Karten mischen, und das umso ungenauer desto schneller er dies versucht (d.h. es kann passieren, dass zwei oder mehrere Karten zwischen zwei anderen liegen).

Hoffe die Analogie ist glasklar

Ich möchte diese Funktion mit euch teilen, und von euch wissen was man daran verbessern/optimieren könnte. Bei Strings, die eine unterschiedliche Anzahl von "Karten" haben wäre ich vorsichtig. Der Algo behandelt dieses Problem noch nicht (ich denke man muss nur eine andere Abbruchbedingung für die äußere while-Schleife definieren).

(Mit 'cBreakAt' kann man ein anderes "Unterscheidungszeichen" definieren als das '\n'-Zeichen)

TCHAR* MixStrings(TCHAR *pDest, TCHAR *pSources[], UINT iSourceCount, INT cBreakAt)
{
  myassert(pDest);
  myassert(pSources);

  TCHAR *tmp = NULL;
  TCHAR **pSourcesCpy = new TCHAR *[iSourceCount];

  if( !pSourcesCpy )
    return NULL;

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

  int i;
  do
  {
    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 (the outer 'while' will exit too)
      {
        if( (*pDest = *tmp) == cBreakAt )
        {
          ++tmp;   // cBreakAt found; point to next character
          ++pDest;
          break;
        }
        ++tmp;
        ++pDest;
      }
      pSourcesCpy[i] = tmp;
    }

  }while( *tmp );

  delete[] pSourcesCpy;
  return pDest;
}

Shade Of Mine

Ich würde es so lösen:

vector<string> stapel1;
vector<string> stapel2;

//füllen
stapel1.push_back("-----");
stapel2.push_back("#####";
//usw.

//einen gemeinsamen stapel bilden
vector<string> gemischt(stapel1.size()+stapel2.size());
gemischt.assign(stapel1.begin(), stapel1.end());
gemischt.insert(gemischt.begin()+gemischt.size()-1, stapel2.begin(), stapel2.end());

//mischen:
random_shuffle(gemischt.begin(), gemischt.end());

das wäre n C++ Lösung. Deine ist irgendwie fast reines C.
btw: new wirft std::bad_alloc wenn es fehlschlägt und returned nicht 0
es sei denn du verwendest den vc++ - der wirft nämlich nix.

Aziz

Deine ist irgendwie fast reines C.

Ja stimmt. Dafür ist es aber viel schneller als deine Version (würd ich mal ganz bescheiden annehmen ).

Aziz

Außerdem dürfen die Strings nicht zufällig angeordnet sein. Das ist zumindest für meine Zwecke sinnlos.

Shade Of Mine

Aziz schrieb:

Außerdem dürfen die Strings nicht zufällig angeordnet sein. Das ist zumindest für meine Zwecke sinnlos.

Sorry, das habe ich falsch gelesen gehabt.
Ich habe 'mischen' gelesen und sofort an Zufall gedacht...

Aziz

Diese Version sollte das zuvor-beschriebene Problem beheben (unterschiedliche Anzahl von "Karten")...

TCHAR* MixStrings(TCHAR *pDest, TCHAR *pSources[], UINT iSourceCount, INT cBreakAt)
{
  myassert(pDest);
  myassert(pSources);

  TCHAR *tmp = NULL;
  TCHAR **pSourcesCpy = new TCHAR *[iSourceCount];

  if( !pSourcesCpy )
    return NULL;

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

  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;
}

Jester

Aziz schrieb:

Dafür ist es aber viel schneller als deine Version (würd ich mal ganz bescheiden annehmen ).

Ich könnte wetten, daß zumindest das "viel" und wahrscheinlich sogar das schneller falsch ist. Aber es ist kurz un elegant, also kann es nicht schnell sein.

MfG Jester

Aziz

Jester schrieb:

Aziz schrieb:

Dafür ist es aber viel schneller als deine Version (würd ich mal ganz bescheiden annehmen ).

Ich könnte wetten, daß zumindest das "viel" und wahrscheinlich sogar das schneller falsch ist. Aber es ist kurz un elegant, also kann es nicht schnell sein.

MfG Jester

Hört, hört! Ich bitt' dich darum, eine viel elegantere und schnellere Version zu schreiben, damit ich mich demütig geschlagen geben kann!
Nein, es würd' sogar reichen wenn sie nur eleganter als meine Version wäre, denn das würde es auch automatisch schneller machen, nicht wahr? Also verlautbare kein leeres Gerede sondern tu auch was, oder erklär' zumindest wie du es mit der Geschwindigkeit nun meinst.

Und herzlich eingeladen ist auch der Shade Of Mine, seine Meinung kundzutun

Aziz

Ich würde mich über eine Antwort freuen...

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

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]

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)