È inefficiente concatenare stringhe una alla volta?

La tua spiegazione del perché è inefficiente è accurata, almeno nelle lingue che conosco (C, Java, C #), anche se non sarei d'accordo sul fatto che è universalmente comune eseguire massicce quantità di concatenazione di stringhe. Nel codice C # su cui lavoro, c'è un uso copioso di StringBuilder , String.Format , ecc. Che sono tutte tecniche di salvataggio della memoria per evitare una sovra-riallocazione.

Quindi per ottenere la risposta alla tua domanda, dobbiamo fare un'altra domanda: se non è mai veramente un problema concatenare le stringhe, perché esistono classi come StringBuilder e StringBuffer ? Perché l'uso di tali classi è incluso anche nei libri e nelle classi di programmazione semi-principianti? Perché i consigli di ottimizzazione apparentemente prematuri sono così importanti?

Se la maggior parte degli sviluppatori che concatenano le stringhe basano la loro risposta esclusivamente sull'esperienza, la maggior parte direbbe che non fa mai la differenza e eviterebbe l'uso di tali strumenti a favore del "% più leggibile" for (int i=0; i<1000; i++) { strA += strB; } . Ma non l'hanno mai misurato.

La vera risposta a questa domanda si può trovare in questa risposta SO , che rivela che in un caso, quando si concatena 50.000 stringhe (che a seconda dell'applicazione potrebbero essere un evento comune), anche di piccole dimensioni, hanno prodotto un risultato di prestazioni 1000 volte .

Se le prestazioni letteralmente non significano nulla, significa assolutamente concatenare. Ma non sarei d'accordo sul fatto che l'utilizzo di alternative (StringBuilder) sia difficile o meno leggibile , e quindi sarebbe una pratica di programmazione ragionevole che non dovrebbe invocare la difesa "ottimizzazione prematura".

UPDATE:

Penso che ciò che ne consegue, è conoscere la tua piattaforma e seguire le sue migliori pratiche, che purtroppo non sono universali . Due esempi da due diverse "lingue moderne":

1. In un'altra risposta SO , le caratteristiche di rendimento esatto opposto (array.join vs + =) sono stati trovati a volte true in JavaScript . In alcuni browser, la concatenazione delle stringhe sembra essere ottimizzata automaticamente, e in altri casi non lo è. Quindi la raccomandazione (almeno in quella domanda SO), è solo concatenare e non preoccuparsene.
2. In un altro caso, un compilatore Java può sostituire automaticamente la concatenazione con un costrutto più efficiente come StringBuilder. Tuttavia, come altri hanno sottolineato, questo è indeterministico, non garantito, e l'uso di StringBuilder non pregiudica la leggibilità. In questo caso particolare, tenderei a raccomandare l'uso della concatenazione per grandi raccolte o basarsi su un comportamento indeterministico del compilatore Java. Allo stesso modo, in .NET, non viene eseguita alcuna ottimizzazione del tipo , mai.

Non è esattamente un peccato capitale non sapere tutte le sfumature di ogni piattaforma subito, ma ignorare importanti problemi di piattaforma come questo sarebbe quasi come passare da Java a C ++ e non preoccuparsi di deallocare la memoria.

Non è efficiente, grosso modo per le ragioni che hai descritto. Le stringhe in C # e Java sono immutabili. Le operazioni sulle stringhe restituiscono un'istanza separata invece di modificare quella originale, diversamente da quanto avviene in C. Quando concatenano più stringhe, viene creata un'istanza separata in ogni passaggio. L'allocazione e la successiva raccolta dei dati inutili che raccolgono le istanze inutilizzate possono causare un calo delle prestazioni. Solo questa volta la gestione della memoria è gestita dal garbage collector.

Sia C # che Java introducono una classe StringBuilder come una stringa mutabile specificamente per questo tipo di attività. Un equivalente in C userebbe un elenco collegato di stringhe concatenate invece di unirle a un array. C # offre anche un comodo metodo Join sulle stringhe per unire una raccolta di stringhe.

In senso stretto è un uso meno efficiente dei cicli della CPU, quindi sei corretto. Ma per quanto riguarda i tempi di sviluppo, i costi di manutenzione, ecc. Se si aggiunge il costo del tempo all'equazione, è quasi sempre più efficiente fare ciò che è più facile, se necessario, profilare e ottimizzare i bit lenti.
"La prima regola dell'ottimizzazione del programma: non farlo. La seconda regola dell'ottimizzazione del programma (solo per esperti!): Non farlo ancora".

È molto difficile dire qualcosa sulle prestazioni senza un test pratico. Recentemente sono stato molto sorpreso di scoprire che in JavaScript una concatenazione di stringa ingenua era di solito più veloce della soluzione "make list and join" raccomandata (test qui , confronta t1 con t4). Sono ancora perplesso sul motivo per cui ciò accade.

Alcune domande che potresti porre quando ragionerai sulle prestazioni (specialmente riguardo l'uso della memoria) sono: 1) quanto è grande il mio contributo? 2) quanto è intelligente il mio compilatore? 3) in che modo il mio runtime gestisce la memoria? Questo non è esaustivo, ma è un punto di partenza.

1. Quanto è grande il mio contributo?

   Una soluzione complessa avrà spesso un sovraccarico fisso, magari sotto forma di operazioni extra da eseguire, o forse nella memoria extra necessaria. Poiché tali soluzioni sono progettate per gestire casi di grandi dimensioni, gli implementatori di solito non avranno problemi a introdurre tale costo aggiuntivo, poiché il guadagno netto è più importante che micro-ottimizzare il codice. Quindi, se il tuo input è sufficientemente piccolo, una soluzione ingenua potrebbe avere prestazioni migliori rispetto a quella complessa, se non altro per evitare questo sovraccarico. (Determinare cosa sia "sufficientemente piccolo" è comunque la parte difficile)

2. Quanto è intelligente il mio compilatore?

   Molti compilatori sono abbastanza intelligenti da "ottimizzare" le variabili che sono state scritte, ma mai lette. Allo stesso modo, un buon compilatore potrebbe anche essere in grado di convertire una concatenazione di stringa ingenua in un uso della libreria (principale) e, se molti di questi sono realizzati senza alcuna lettura, non è necessario convertirlo in una stringa tra quelle operazioni (anche se il tuo codice sorgente sembra fare proprio questo). Non riesco a capire se qualche compilatore là fuori lo faccia, o fino a che punto sia fatto (AFAIK Java sostituisce almeno parecchi concat nella stessa espressione in una sequenza di operazioni StringBuffer), ma è una possibilità.

3. In che modo il mio runtime gestisce la memoria?

   Nelle moderne CPU il collo di bottiglia non è solitamente il processore, ma la cache; se il tuo codice accede a molti indirizzi di memoria "distanti" in poco tempo, il tempo necessario per spostare tutta la memoria tra i livelli di cache supera le maggiori ottimizzazioni nelle istruzioni utilizzate. Ciò è di particolare importanza in runtime con i garbage collector generazionali, dal momento che le variabili create più di recente (all'interno dello stesso ambito di funzione, ad esempio) di solito si trovano in indirizzi di memoria contigui. Quei runtime inoltre spostano regolarmente la memoria avanti e indietro tra le chiamate di metodo.

   Un modo in cui può influire sulla concatenazione delle stringhe (disclaimer: questa è una congettura sfrenata, non sono abbastanza esperto da dirlo con certezza) sarebbe se la memoria per l'ingenuo fosse allocata vicino al resto del codice che usa (anche se lo assegna e lo rilascia più volte), mentre la memoria per l'oggetto della libreria è stata allocata lontano da esso (quindi il contesto cambia mentre il codice viene calcolato, la libreria consuma, il codice calcola di più, ecc genererebbe molte cache manca). Ovviamente per i grandi input OTOH la cache fallisce comunque, quindi il problema delle allocazioni multiple diventa più pronunciato.

Detto questo, non sto sostenendo l'uso di questo o quel metodo, solo che il test e la profilazione e il benchmarking dovrebbero precedere qualsiasi analisi teorica sulle prestazioni, dal momento che la maggior parte dei sistemi al giorno d'oggi è troppo complessa per comprendere appieno il soggetto.

Joel ha scritto un ottimo articolo su questo argomento da un po 'di tempo fa. Come alcuni altri hanno sottolineato, è strongmente dipendente dalla lingua. A causa del modo in cui le stringhe vengono implementate in C (zero terminato, senza campo di lunghezza), la routine di libreria strcat standard è molto inefficiente. Joel presenta un'alternativa con solo un piccolo cambiamento che è molto più efficiente.

Is it inefficient to concatenate strings one at a time?

No.

Hai letto 'Triste tragedia di Micro -Optimization Theatre '?