Concatenazione di stringhe efficiente in C ++

StackOverflow https://stackoverflow.com/questions/611263

Domanda

Ho sentito alcune persone esprimere preoccupazioni per " + " operatore in std :: string e varie soluzioni alternative per accelerare la concatenazione. Uno di questi è davvero necessario? In tal caso, qual è il modo migliore per concatenare le stringhe in C ++?

È stato utile?

Soluzione

Il lavoro extra probabilmente non ne vale la pena, a meno che tu non abbia davvero bisogno di efficienza. Probabilmente avrai un'efficienza molto migliore semplicemente usando l'operatore + =.

Ora, dopo questo disclaimer, risponderò alla tua vera domanda ...

L'efficienza della classe di stringa STL dipende dall'implementazione di STL che si sta utilizzando.

Potresti garantire efficienza e avere un maggiore controllo eseguendo la concatenazione manualmente tramite le funzioni incorporate c.

Perché l'operatore + non è efficiente:

Dai un'occhiata a questa interfaccia: 

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

Puoi vedere che un nuovo oggetto viene restituito dopo ogni +. Ciò significa che ogni volta viene utilizzato un nuovo buffer. Se stai facendo un sacco di operazioni extra + non è efficiente.

Perché puoi renderlo più efficiente:

  • Stai garantendo efficienza invece di affidarti a un delegato per farlo in modo efficiente per te
  • la classe std :: string non sa nulla della dimensione massima della stringa, né della frequenza con cui vi concatenerete. Potresti avere questa conoscenza e fare le cose basandoti su queste informazioni. Ciò comporterà meno riassegnazioni.
  • Controllerai i buffer manualmente in modo da poter essere sicuro di non copiare l'intera stringa in nuovi buffer quando non vuoi che ciò accada.
  • Puoi usare lo stack per i tuoi buffer anziché l'heap che è molto più efficiente.
  • stringa + operatore creerà un nuovo oggetto stringa e lo restituirà quindi utilizzando un nuovo buffer.

Considerazioni per l'implementazione:

  • Tieni traccia della lunghezza della stringa.
  • Mantieni un puntatore alla fine della stringa e all'inizio, o solo all'inizio e usa start + la lunghezza come offset per trovare la fine della stringa.
  • Assicurati che il buffer in cui stai memorizzando la tua stringa sia abbastanza grande da non dover riassegnare i dati
  • Usa strcpy invece di strcat in modo da non dover iterare sulla lunghezza della stringa per trovare la fine della stringa.

Struttura dei dati della corda:

Se hai bisogno di concatenazioni molto veloci, considera l'utilizzo di una struttura dei dati .

Altri suggerimenti

Prenota prima il tuo spazio finale, quindi usa il metodo append con un buffer. Ad esempio, supponi che ti aspetti che la lunghezza della stringa finale sia di 1 milione di caratteri: 

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

Non me ne preoccuperei. Se lo fai in un ciclo, le stringhe prealloceranno sempre la memoria per ridurre al minimo le riallocazioni - in questo caso usa solo operator + = . E se lo fai manualmente, qualcosa del genere o più lungo 

a + " : " + c

Quindi sta creando dei provvisori, anche se il compilatore potrebbe eliminare alcune copie del valore di ritorno. Questo perché in un successore chiamato operatore + non si sa se il parametro di riferimento fa riferimento a un oggetto denominato o a un temporaneo restituito da una chiamata secondaria operator + . Preferirei non preoccuparmene prima di non aver profilato prima. Ma facciamo un esempio per dimostrarlo. Per prima cosa introduciamo le parentesi per chiarire l'associazione. Ho messo gli argomenti direttamente dopo la dichiarazione di funzione che è stata usata per chiarezza. Di seguito, mostro qual è l'espressione risultante quindi: 

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

Ora, in quell'aggiunta, tmp1 è ciò che è stato restituito dalla prima chiamata all'operatore + con gli argomenti mostrati. Partiamo dal presupposto che il compilatore è davvero intelligente e ottimizza la copia del valore restituito. Quindi finiamo con una nuova stringa che contiene la concatenazione di a e " : " . Ora, questo succede: 

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

Confrontalo con il seguente: 

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

Sta usando la stessa funzione per un temporaneo e per una stringa denominata! Quindi il compilatore deve copiare l'argomento in una nuova stringa e accodarlo e restituirlo dal corpo di operator + . Non può prendere la memoria di un temporaneo e aggiungerlo a quello. Maggiore è l'espressione, più copie delle stringhe devono essere eseguite.

Next Visual Studio e GCC supporteranno la mossa semantica di c ++ 1x (integrando la copia semantica ) e i riferimenti di valore come aggiunta sperimentale. Ciò consente di capire se il parametro fa riferimento a un temporaneo o meno. Ciò renderà tali aggiunte sorprendentemente veloci, poiché tutto quanto sopra finirà in una "pipeline addizionale" senza copie.

Se risulta essere un collo di bottiglia, puoi ancora farlo 

 std::string(a).append(" : ").append(c) ...

Le chiamate append aggiungono l'argomento a * this e quindi restituiscono un riferimento a se stessi. Quindi non viene eseguita alcuna copia dei provvisori. Oppure, in alternativa, è possibile utilizzare l'operatore + = , ma per fissare la precedenza sono necessarie brutte parentesi.

Per la maggior parte delle applicazioni, non importa. Scrivi il tuo codice, beato inconsapevolmente di come funziona esattamente l'operatore +, e prendi in mano la situazione solo se diventa un evidente collo di bottiglia.

A differenza di .NET System.Strings, gli std :: stringhe di C ++ sono mutabili e quindi possono essere creati attraverso una semplice concatenazione alla stessa velocità di altri metodi.

forse invece std :: stringstream?

Ma sono d'accordo con il sentimento che probabilmente dovresti semplicemente mantenerlo e comprensibile e quindi profilare per vedere se stai davvero avendo problemi.

In C ++ imperfetto , Matthew Wilson presenta un concatenatore di stringhe dinamico che pre-calcola la lunghezza della stringa finale per avere una sola allocazione prima di concatenare tutte le parti. Possiamo anche implementare un concatenatore statico giocando con modelli di espressione .

Questo tipo di idea è stata implementata nell'implementazione di STLport std :: string - che non è conforme allo standard a causa di questo preciso hack.

std :: string operator + alloca una nuova stringa e copia le due stringhe di operando ogni volta. ripeti molte volte e diventa costoso, O (n).

std :: string append e operator + = d'altro canto, aumentano la capacità del 50% ogni volta che la stringa deve crescere . Ciò riduce significativamente il numero di allocazioni di memoria e operazioni di copia, O (log n).

Per le stringhe piccole non importa. Se hai grandi stringhe, è meglio conservarle come sono in vettoriale o in qualche altra collezione come parti. E aggiungi il tuo algoritmo per lavorare con una tale serie di dati anziché con un'unica grande stringa.

Preferisco std :: ostringstream per concatenazioni complesse.

Come per la maggior parte delle cose, è più facile non fare qualcosa che farlo.

Se si desidera inviare stringhe di grandi dimensioni a una GUI, è possibile che qualunque cosa si stia eseguendo in grado di gestire le stringhe in pezzi meglio che come una stringa di grandi dimensioni (ad esempio, concatenando il testo in un editor di testo - di solito mantengono linee come strutture separate).

Se si desidera eseguire l'output su un file, eseguire lo streaming dei dati anziché creare una stringa di grandi dimensioni e inviarla in output.

Non ho mai trovato la necessità di rendere la concatenazione più veloce necessaria se ho rimosso la concatenazione non necessaria dal codice lento.

Un semplice array di caratteri, incapsulato in una classe che tiene traccia delle dimensioni dell'array e del numero di byte allocati è il più veloce.

Il trucco è fare solo una grande allocazione all'inizio.

a

https://github.com/pedro-vicente/table-string

Benchmarks

Per Visual Studio 2015, build di debug x86, miglioramento substanziario rispetto a C ++ std :: string. 

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |

Probabilmente le migliori prestazioni se si pre-alloca (riserva) lo spazio nella stringa risultante. 

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Utilizzo: 

std::string merged = concat("This ", "is ", "a ", "test!");
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top