Strings mischen, Algorithmus

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.

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.