C'è qualche scenario in cui la Corda struttura di dati è più efficace di una stringa builder

Question

Relative al questa domanda, basandosi commento di utente Eric Lippert.

C'è qualche scenario in cui il Corda struttura di dati è più efficace di una stringa di generatore?È un po ' di gente opinione che la corda strutture di dati, non sono quasi mai di meglio in termini di velocità rispetto a quella nativa stringa o una stringa generatore di operazioni nei casi tipici, quindi sono curioso di vedere scenari realistici in cui le corde sono meglio.

Answer 1

La documentazione per la SGI C ++ implementazione va in qualche dettaglio sul grande comportamenti O versi i fattori costanti, che è istruttivo.

La loro documentazione presuppone stringhe molto lunghe essere coinvolti , gli esempi postulò per riferimento parlare di 10 stringhe MB . Molto pochi programmi saranno scritti che si occupano di queste cose e, per molte classi di problemi con tali requisiti rielaborando loro di essere basato sul flusso , piuttosto che richiedere la stringa completa di essere a disposizione, ove possibile, porterà a significativamente superiore risultati. Poiché tali corde sono per manipolazione non lo streaming di multi sequenze di caratteri megabyte quando si è in grado di trattare adeguatamente la corda come sezioni (si funi) piuttosto che una sequenza di caratteri.

significativi Pro:

• concatenazione / Insertion diventare operazioni di tempo pressoché costanti
• Alcune operazioni possono riutilizzare le sezioni corda precedenti per consentire la condivisione in memoria.
  • Si noti che le stringhe Net, a differenza di stringhe java non condividono il buffer di carattere su sottostringhe - una scelta con pro e contro in termini di occupazione di memoria. Corde tendono ad evitare questo tipo di problema.
• Corde permettono il carico differito di sottostringhe fino al momento
  • Si noti che questo è difficile da ottenere, molto facile da rendere inutile a causa di un eccessivo desiderio di accesso e richiede che consumano il codice di trattarlo come una corda, non come una sequenza di caratteri.

Significativo Contro:

• a caso l'accesso in lettura diventa O (log n)
• I fattori costanti in materia di accesso di lettura sequenziale sembrano essere tra 5 e 10
• uso efficiente delle API richiede trattandolo come una corda, non solo cadere in una corda come attuazione rovescio del 'normale' api stringa.

Questo porta ad alcuni usi 'ovvie' (la prima volta in modo esplicito da SGI).

• Modifica buffer su file di grandi dimensioni che consente un facile undo / redo
  • Si noti che, ad un certo punto potrebbe essere necessario scrivere i cambiamenti sul disco, che coinvolge in streaming attraverso l'intera stringa, quindi questo è utile solo se la maggior parte delle modifiche risiederà principalmente in memoria piuttosto che richiedere la persistenza frequente (dire attraverso una funzione di salvataggio automatico )
• manipolazione di segmenti di DNA in cui si verifica manipolazione significativo, ma molto poco uscita effettivamente accade
• Multi threaded algoritmi che mutano sottosezioni locali di stringa. In teoria tali casi possono essere parcellizzati off per thread e core separati senza dover prendere copie locali delle sottosezioni e poi ricombinare, notevole risparmio di memoria e di evitare un'operazione combinando seriale costosa alla fine.

Ci sono casi in cui il comportamento specifico del dominio nella stringa può essere accoppiato con relativamente semplici potenziamenti alla realizzazione corda per permettere:

• Leggi solo le stringhe con un numero significativo di sottostringhe comuni sono suscettibili di semplici internato per un notevole risparmio di memoria.
• Corde con strutture sparse, o significativa ripetizione locale sono suscettibili di eseguire la codifica lunghezza pur consentendo livelli ragionevoli di accesso casuale.
• Dove i confini sottostringa stessi sono 'nodi' in cui le informazioni possono essere memorizzate, se tali strutture sono del tutto possibile meglio fatto come un Radix Trie se sono raramente modificati, ma spesso lettura.

Come si può vedere dagli esempi elencati, tutti rientrano bene nella categoria 'nicchia'. Inoltre, molti potrebbe avere alternative migliori se si è disposti / in grado di riscrivere l'algoritmo come operazione di stream processing, invece.

Answer 2

La risposta breve a questa domanda è sì, e che richiede poca spiegazione. Naturalmente c'è situazioni in cui la struttura dei dati corda è più efficiente di un costruttore di stringa. essi funzionano in modo diverso, in modo che siano più adatti per scopi diversi.

(Dal punto di vista C #)

La struttura dati corda come un albero binario è meglio in certe situazioni. Quando stai guardando estremamente grandi valori di stringa (si pensi 100+ MB di XML provenienti da SQL), la struttura dei dati corda potrebbe mantenere l'intero processo fuori dal mucchio di grandi dimensioni dell'oggetto, in cui l'oggetto stringa colpisce quando passa 85000 byte.

Se stai guardando stringhe di caratteri 5-1000, probabilmente non migliora le prestazioni abbastanza per essere valsa la pena. questo è un altro caso di una struttura di dati che è stato progettato per il 5% delle persone che hanno una situazione estrema.

Answer 3

Il 10 ICFP Contest di Programmazione affidamento, fondamentalmente, su persone utilizzando la corda struttura di dati efficiente per la risoluzione dei.Che è stato il grande trucco per ottenere una VM che correva in un tempo ragionevole.

La corda è ottima se non ci sono un sacco di prefisso (a quanto pare la parola "aggiungendo" è composto da gente e non è una parola giusta!) e potenzialmente migliore per inserimenti;StringBuilders uso continuo di memoria, in modo che solo il lavoro in modo efficiente per l'aggiunta.

Pertanto, StringBuilder è grande per la costruzione di stringhe mediante l'aggiunta di frammenti di un normale caso di utilizzo.Come gli sviluppatori hanno bisogno di fare un sacco di tutto questo, StringBuilders sono una tecnologia mainstream.

Le corde sono grandi per modificare il buffer, ad esempioi dati-struttura alle spalle, per dire, a un enterprise-punto di forza TextArea.Così (un allentamento delle Funi, ad es.un elenco collegato di linee piuttosto che un albero binario) è molto comune nei controlli UI mondo, ma non è spesso esposto per gli sviluppatori e gli utenti di tali controlli.

Hai bisogno di davvero grande quantità di dati e la zangola per fare la corda pay-off - processori sono molto bravi a flusso di operazioni, e se hai la RAM quindi semplicemente realloc per prefissare un lavoro accettabile per un uso normale-casi.Che la concorrenza menzionati all'inizio fu l'unica volta che l'ho visto necessario.

Answer 4

La maggior parte degli editor di testo avanzati rappresentano il corpo del testo come una "sorta di corda" (anche se in esecuzione, le foglie di solito non sono singoli caratteri, ma il testo corre), principalmente per migliorare i gli inserti frequenti e cancella su grandi testi.

In generale, StringBuilder è ottimizzato per l'aggiunta e cerca di ridurre al minimo il numero totale di riassegnazioni , senza overallocating a molto. La garanzia tipico è (log 2 N allocazioni, e meno di 2,5 volte la memoria). Normalmente la stringa è costruita una volta e può quindi essere usata per molto tempo senza essere modificato.

Corda è ottimizzato per inserti frequenti e rimozioni, e cerca di minimizzare quantità di dati copiati (da un maggior numero di allocazioni). In un'implementazione del buffer lineare, ogni inserto e cancellare diventa O (N), e di solito si devono rappresentare gli inserti di caratteri singoli.

Answer 5

JavaScript VM utilizzano spesso le corde per le stringhe.

Maxime Chevalier-Boisvert, sviluppatore del bosone di Javascript VM, dice :

  

In JavaScript, è possibile utilizzare un array di stringhe e, infine,   Array.prototype.join per rendere concatenazione di stringhe ragionevolmente veloce,   O (n), ma il modo "naturale" programmatori JS tendono a costruire le stringhe è quello di   basta aggiungere utilizzando l'operatore + = a loro costruire in modo incrementale. JS   stringhe sono immutabili, quindi se questo non è ottimizzato internamente,   apposizione incrementale è O (n2). Penso che sia probabile che le corde erano   implementato nei motori JS proprio a causa della SunSpider   parametri di riferimento che fanno stringa aggiunta. implementatori del motore JS usati   corde per ottenere un vantaggio sugli altri, facendo qualcosa che era   in precedenza lenta più veloce. Se non fosse stato per quei parametri di riferimento, penso   che grida dalla comunità circa stringa di accodamento uno scarso rendimento   potrebbe essere stato incontrato "usare Array.prototype.join, manichino!".

anche.