char array mit Seperator alphabetisch sortieren

volkard

knivil schrieb:

Quadratische Laufzeit?

Wahrscheinlich. Vielleicht schafft es der Compiler trotzdem zu optimieren.

Nö, sehe da keine Anker, wo der Optimierer greifen könnte. Er wird nicht res.reserve(wordlist.count()+accumulate(wordlist.begin(),wordlist.end(),[]...)) herausfinden.

Aber es kann sein, daß die Implementierung von std::string den Speicher bei += geometrisch wachsen läßt. An sich eine Unsitte. Aber halt sinnvoll für Normalprogrammierer, die die quadratische Laufzeit nicht direkt sehen. Dafür wünschte ich mir ein +=, das direkt und minimal wirkt und eine andere append-Methode, die geometischg wachsen läßt.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    string word="hello";
    string res;
    size_t oldCapacity=0;
    for(int i=0;i<1000000;++i){
        res+=word+" ";
        if(res.capacity()!=oldCapacity){
            cout<<res.capacity()<<'\n';
            oldCapacity=res.capacity();
        }
    }
}

Ausgabe

Ok, gcc verdoppelt immer (ungefähr) bei +=.

Woher mögen die krummen Zahlen kommen?

camper

volkard schrieb:

Woher mögen die krummen Zahlen kommen?

Ausrichtung an 4kB-Seiten - free-storeverwaltungsoverhead - 1 Byte Terminator schätze ich mal. Vermutlich mag default-new Speicheranforderungen, die (fast) Vielfache von 4kB sind.

Columbo

GCC 4.9.0, basic_string.tcc

append(const basic_string& __str)
    {
      const size_type __size = __str.size();
      if (__size)
	{
	  const size_type __len = __size + this->size();
	  if (__len > this->capacity() || _M_rep()->_M_is_shared())
	    this->reserve(__len);
	  _M_copy(_M_data() + this->size(), __str._M_data(), __size);
	  _M_rep()->_M_set_length_and_sharable(__len);
	}
      return *this;
    }

Wo ist hier die Verdopplung versteckt?

camper

Arcoth schrieb:

Wo ist hier die Verdopplung versteckt?

In _S_create, mit ausführlichem Kommentar.

happystudent

volkard schrieb:

Bisher wenig. Denke, Du solltest die chars in einem vector<char> erst sammeln und dann Schwuppdiwupps in den Zielstring kopieren oder erst die Zeichen zählen (endlich accumulate), den Zielstring mit dieser Zeichenanzahl anlegen und dann die Quellstrings alle reinkopieren.

edit: Mit http://www.cplusplus.com/reference/string/string/reserve/ vorher genug Platz reservieren, dann ist die Laufzeit von join/accumulate/schleife optimal.

Beim String steht nämlich nicht http://www.cplusplus.com/reference/vector/vector/push_back/

std::string schrieb:

Complexity
Constant (amortized time, reallocation may happen).

If a reallocation happens, the reallocation is itself up to linear in the entire size.

Moment, das geht mir gerade etwas zu schnell.

Also die Wörter sammel ich jetzt in einem vector<string>, das passt nehme ich an? Diesen konvertiere ich dann bei Bedarf mittels join in eine Form die die dll akzeptiert.

Also geht es momentan nur um die Implementierung der join Funktion, das prinzipielle Vorgehen ist so ok, hab ich das richtig verstanden?

Dann weiter: Dass ich mittels string::reserve genug Platz reserviere macht Sinn, aber wenn ich davor die Zeichen mit accumulate zählen muss, muss ich selbiges doch wieder verwenden, was wie ich dachte quadratische Laufzeit hat?

EDIT:

Hab noch folgendes Snippet beim googlen gefunden:

string join(const vector<string> & vec,const string & sep)
{
    if(vec.size()==0)
        return "";
    string::size_type size=sep.length()*vec.size();
    for(unsigned int i=0;i<vec.size();i++)
    {
        size+=vec[i].size();
    }

    string tmp;
    tmp.reserve(size);
    tmp=vec[0];
    for(unsigned int i=1;i<vec.size();i++)
    {
        tmp=tmp+sep+vec[i];
    }
    return tmp;
}

Ist das besser als meins?

knivil

von std::string den Speicher bei += geometrisch wachsen läßt.

Warum sollte es anders als bei std::vector sein? Ich dachte du meinst, die Anzahl der Kopieroperationen/kopierten Zeichen.

volkard

happystudent schrieb:

Dann weiter: Dass ich mittels string::reserve genug Platz reserviere macht Sinn, aber wenn ich davor die Zeichen mit accumulate zählen muss, muss ich selbiges doch wieder verwenden, was wie ich dachte quadratische Laufzeit hat?

accumulate selber ist linear mit der anzahl der zu summierenden objekte. aber wenn das += des strings auch linear zur länge des ergebnisstrings ist, wird das zusammen quadratisch. also accumulate auf string ist sünde. accumulate auf size_t ist klasse.
wübei die sünde halb so wild wohl ist. gcc rechnet damit, daß gesündigt wird und bleibt schnell. wenn ms auch damit rechnet, dann ist das schon ein quasistandard und.

volkard

knivil schrieb:

von std::string den Speicher bei += geometrisch wachsen läßt.

Warum sollte es anders als bei std::vector sein?

Damit ich als Benutzer nicht so gequält werde. vector benutze ich fast immer mit push_back, da ist das geometrische Wachstum gut (sorg für amortisiert lineare Wachstumskosten). Und ich bin so frei, das reserve vorher sogar wegzulassen, was hier im Forum anscheinend leider zu sowas wie einer Pflichtübung geworden ist. Bei string sieht das ganz anders aus. Da baue ich mal eine sql-query zusammen oder einen vector/set/map von Dateinamen.
Wir sind uns hoffentlich einig, daß die Schnittstelle der DLL komisch ist, eine saulange Stringliste als EINEN riesigen leerzeichengetrennten String haben zu wollen. Für was braucht man sonst schnelles += auf riesige Strings? Also ich nicht. Da bin ich dann Fan von Speichersparen.

volkard

happystudent schrieb:

Hab noch folgendes Snippet beim googlen gefunden:

string join(const vector<string> & vec,const string & sep)
{
    if(vec.size()==0)
        return "";
    string::size_type size=sep.length()*vec.size();
    for(unsigned int i=0;i<vec.size();i++)
    {
        size+=vec[i].size();
    }

    string tmp;
    tmp.reserve(size);
    tmp=vec[0];
    for(unsigned int i=1;i<vec.size();i++)
    {
        tmp=tmp+sep+vec[i];
    }
    return tmp;
}

Ist das besser als meins?

Ja, insofern, daß es sich nicht auf spezielle Implementierungen der Standradbibliothek verläßt, die mehr versprechen als im Standard garantiert ist.
Ich würde sie noch anpassen auf Dich.

string join(const vector<string> & vec/*,const string & sep//weg, ist bei Dir ' '*/)
{
    string tmp;//hoch damit, dann kann sogar der weltdümmste compiler die rückgabe optimieren
/*    if(vec.size()==0) //weg, kommt bei Dir eh nicht vor. 
        return "";*/
    string::size_type size=vec.size();//sep.length weg
    for(size_t i=0;i<vec.size();i++)//schon size_t nehmen
    {
        size+=vec[i].size();
    }

    tmp.reserve(size);
//    tmp=vec[0];//häßlich, oder?
    for(unsigned int i=0;i<vec.size();i++)//zum ausgleich bei 0 starten
    {
        tmp=tmp+sep+vec[i];
    }
    return tmp;
}

happystudent

Cool, danke für die Erklärungen und die Anpassungen.
Werd ich gleich mal einbauen.

volkard

for(unsigned int i=0;i<vec.size();i++)//quatsch, besser begin() und end()

//tmp=tmp+sep+vec[i];//vollquatsch
tmp+=vec[i];
tmp+=' ';

knivil

Und ich bin so frei, das reserve vorher sogar wegzulassen, was hier im Forum anscheinend leider zu sowas wie einer Pflichtübung geworden ist.

Jap, bei meinen Tests (firmenintern, problemspezifisch, etc. ) zeigte sich auch kein Performancevorteil von reserve .

Wir sind uns hoffentlich einig ...

Ja.

otze

Und ich bin so frei, das reserve vorher sogar wegzulassen, was hier im Forum anscheinend leider zu sowas wie einer Pflichtübung geworden ist.

Ich dachte es war Konsenz, dass vector ausser in wenigen Sonderfällen kein reserve braucht.