3. std::string split-Funktion Optimierung möglich?

std::string split-Funktion Optimierung möglich?


  • es kommt zwar relativ selten vor, dass ich frag, ob mein Code gut ist, aber
    in diesem Fall gehts doch ein bisschen darum, das er Performant ist und
    verbessern will ich mich ja auch mal 😃 .

    Habe hier mal zwei Splitfunktionen mit Aufruf gebastelt.
    Nach meinen Messungen ist schonmal split1 um "einiges Schneller" als split2.
    Aber ich glaube, dass man trotzdem noch eingiges verbessern könnte.
    Bin ja kein Spezi 😋

    Hat jemand ein paar Vorschläge?

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

#include <windows.h>

void split1(const std::string src, const std::string delimiter, std::vector<std::string> &vecString)
{
	int newPos = 0, oldPos = 0;

	oldPos = src.find(delimiter, 0);
	if(oldPos != std::string::npos)
		vecString.push_back(src.substr(0, oldPos));
	else
		vecString.push_back(src);

	while(oldPos != std::string::npos)
	{
		newPos = src.find(delimiter, oldPos+delimiter.length());
		if(oldPos != std::string::npos)
			vecString.push_back(src.substr(oldPos+delimiter.length(), newPos-oldPos));

		oldPos = newPos;
	}
}

void split2(const std::string src, const std::string delimiter, std::vector<std::string> &vecString)
{
	int pos;
	std::string temp = src;

	do
	{
		pos = temp.find(delimiter, 0);

		if(pos != std::string::npos)
		{
			std::string result = src.substr(0, pos);
			vecString.push_back(result);
			temp = temp.substr(pos + 1, temp.length() - pos - 1);
		}
	} while(pos != std::string::npos);

	if(temp.length() > 0)
	{
		vecString.push_back(temp);
	}
}

int main(int argc, char **argv)
{
	LONGLONG freq;
	LONGLONG startFrame;
	LONGLONG endFrame;

	int i;

	std::string src = "12 23 43 33 53";

	for(int j=0; j<20; j++)
	{
		// SPLIT 1
		QueryPerformanceFrequency((LARGE_INTEGER*) &freq);
		QueryPerformanceCounter((LARGE_INTEGER*) &startFrame);

		for(i=0; i<1000; ++i)
		{
			std::vector<std::string> vecString(0);
			split1(src, "x", vecString);
		}

		QueryPerformanceCounter((LARGE_INTEGER*) &endFrame);
		printf("%d\t", endFrame-startFrame);

		// SPLIT 2
		QueryPerformanceCounter((LARGE_INTEGER*) &startFrame);

		for(i=0; i<1000; ++i)
		{
			std::vector<std::string> vecString2(0);
			split2(src, "x", vecString2);
		}

		QueryPerformanceCounter((LARGE_INTEGER*) &endFrame);
		printf("%d", endFrame-startFrame);

		std::cout << std::endl;
	}

	return 0;
}

    ( Ja, ich weiß, dass es "using namespace std;" gibt *g* )

    0
  • K

    Hm naja, wenn du mal kurz erklärt hättest was in den Funktionen überhaupt passieren soll (wenigstens ein paar Kommentare), hätte man auch darüber nachdenken können, ob man das anders lösen kann. So kann man nicht viel sagen. Den Code finde ich eigentlich schon ganz OK, aber bei den Parameter hätte ich const-reference's genommen.

    0

  • Jawohl Kóyaánasqatsi ... Dein Wunsch sei mir Befehl *g*.

    Im Prinzip eine ganz normale Splitfunktion, die anhand eines Delimiters
    die einzelnen Elemente in einen std::vector speichert.

    Einzige Besonderheit ist bloß, dass der Delimiter mehrere Zeichen beinhalten kann. (drum hab ich von einer Iteration über jedes Zeichen abgesehen)
    Und wird kein Delimiter gefunden, wird der übergebene String 1:1 in den Vector geschrieben.

    Die Performance erschien mir deshalb wichtig, weil der String aus dem Netzwerk zu mir gesand wird 😃 und ich ihn so schnell wie möglich verarbeiten will.
    Kann ja sein, dass es in diese Richtung Tipps und Tricks gibt.

    Die 5 popeligen Zahlen sind ja net viel. Das dürften später so um die 100 sein *grübel*

    0
  • C
    Mod

    BasicMan01 schrieb:

    Hat jemand ein paar Vorschläge?

    Mach so wenig wie möglich. Wenn du etwas machen kannst, ohne haufenweise Sachen zu kopieren, ist das in der Regel günstiger.
    Zunächst einmal habe ich Probleme mit dem Interafce

    void split1(const std::string src, const std::string delimiter, std::vector<std::string> &vecString)

    Dass die ersten beiden Parameter keine Referenzen sind, ist vermutlich nur ein Unfall. Der dritte Parameter sollte eher als Ergebnis erscheinen, denn das ist, was dessen Funktion darstellt. Interessanter wäre aber die Verwendung eines Outputiterators, um nicht unnötig auf einen bestimmten Containertyp beschränkt zu sein. Zudem kann man sich fragen, ob die Beschränkung auf string nützlich ist. Folgender Entwurf zeigt, dass eine reine Iteratorversion praktibel ist

    template <typename Forwarditerator1, typename Forwarditerator2, typename Outpuititerator>
Outputiterator split(Forwarditerator1 begin, Forwarditerator1 end, Forwarditerator2 delimiter_begin, Forwarditerator2 deliminiter_end, Outputiterator out)
{
    typedef typename std::iterator_traits<Outputiterator>::value_type value_type;
    Forwarditerator1 pos = std::find_end( begin, end, delimiter_begin, delimiter_end );
// Der Standardalgorithmus findet das letzte Vorkommen, daher rekursive Anwendung
// man könnte auch selbst basteln mit find+equal
    if ( pos != end )
    {
        out = split( begin, pos, delimiter_begin, delimiter_end, out );
        std::advance( pos, std::distance( delimiter_begin, delimiter_end ) );
    }
    else
        pos = begin;
    *out = value_type( pos, end );
    return ++out;
}

template <typename Forwarditerator1, typename T, std::size_t N, typename Outpuititerator>
Outputiterator split(Forwarditerator1 begin, Forwarditerator1 end, T (&arr)[N], Outputiterator out)
{
    return split( begin, end, arr, arr + N, out );
}

    Anwendung

    std::vector<std::string> vec;
            split(src.begin(),src.end(), "x", std::back_inserter(vec));

    boosts Stringalgo Bibliothek verfügt ebenfalls über ein split

    0

  • OK, camper 😃 ... ich bekomm deinen Code nicht in meinem Ofen gebacken.
    Ich dachte, fang erstmal einfach an und probier es ohne Templates, um überall dahinter zu steigen

    std::string split(std::string::iterator begin, std::string::iterator end, std::string::iterator delBegin, std::string::iterator delEnd, std::vector<std::string>::iterator vec)
{
	return begin;
}

std::string split(std::string::iterator begin, std::string::iterator end, std::string (&del)[2], std::vector<std::string>::iterator vec)
{
	return split(begin, end, del, del+2, vec);
}

int main(int argc, char **argv)
{
	std::string src = "12 23 43 33 53";
	std::string del = "x";

	std::vector<std::string> vecString(0);

	split(src.begin(), src.end(), "x", std::back_inserter(vecString));
	split(src.begin(), src.end(), del.begin(), del.end(), std::back_inserter(vecString));

	return 0;
}

    Punkt 1 ist das: "'back_inserter' : Ist kein Element von 'std'"
    Punkt 2 ist der 3. Parameter der unteren split-Funktion > std::string (&del)[2]

    mich würde die Funktionsdefinition ohne templates interessieren. Da kann ich dann drauf aufbauen.

    camper schrieb:

    Zudem kann man sich fragen, ob die Beschränkung auf string nützlich ist

    Das hast du aber jetzt hoffentlich net geschrieben, weil du sonst deinen Beispielcode hättest umschreiben müssen? 😃

    0
  • B

    zu Punkt 1

    #include <iterator>
    0
  • _

    Ist zwar etwas her, aber in Zeile 38 deines ersten Postings muss es

    std::string result = temp.substr(0, pos);

    heißen (temp statt src).

    0
  • Mod

    Nanu, was ist denn mit dir los? Betrunken? Du machst doch sonst nicht so einen Nekromist.

    0
Anmelden zum Antworten