"L'operazione media" ha luogo sui primitivi. Ma anche nelle lingue in cui le stringhe vengono trattate come primitive, sono ancora matrici sotto la cappa, e qualsiasi cosa coinvolga l'intera stringa richiede O (N) tempo, dove N è la lunghezza della stringa.
Ad esempio, l'aggiunta di due numeri richiede generalmente 2-4 istruzioni ASM. La concatenazione ("aggiunta") di due stringhe richiede una nuova allocazione di memoria e una o due copie di stringa, che coinvolgono l'intera stringa.
Alcuni fattori linguistici possono peggiorare le cose. In C, ad esempio, una stringa è semplicemente un puntatore a una matrice di caratteri con terminazione null. Ciò significa che non sai quanto è lungo, quindi non c'è modo di ottimizzare un ciclo di copia delle stringhe con operazioni di spostamento veloce; è necessario copiare un carattere alla volta in modo da poter testare ogni byte per il terminatore null.
Questo è un thread vecchio e penso che le altre risposte siano grandiose, ma trascuri qualcosa, quindi ecco i miei (ultimi) 2 centesimi.
Il problema con le stringhe è che sono cittadini di seconda classe nella maggior parte delle lingue, e di fatto la maggior parte delle volte non fanno realmente parte delle specifiche del linguaggio stesso: sono un costrutto implementato in libreria con qualche occasionale rivestimento sintetico dello zucchero in cima per renderli meno dolorosi da usare.
La diretta conseguenza di ciò è che il linguaggio nasconde una gran parte della loro complessità lontano dalla tua vista, e paghi i subdoli effetti collaterali perché cresci nell'abitudine di considerarli come un'entità atomica di basso livello , proprio come altri tipi primitivi (come spiegato dalla risposta più votata e da altri).
Uno degli elementi di questa "complessità" di fondo è che la maggior parte delle implementazioni di stringhe ricorrerebbe all'utilizzo di una semplice struttura dati con uno spazio di memoria contiguo per rappresentare la stringa: il tuo buon vecchio array.
Questo è un buon senso, intendiamoci, perché volete che l'accesso alla stringa nel suo complesso sia veloce. Ma questo implica costi potenzialmente terribili quando si vuole manipolare questa stringa. L'accesso a un elemento nel mezzo potrebbe essere veloce se sai quale indice stai cercando, ma cercare per un elemento basato su una condizione non lo è.
Anche restituire la dimensione della stringa potrebbe essere costoso, se la tua lingua non memorizza nella cache la lunghezza della stringa e deve eseguirla per contare i caratteri.
Per motivi simili, gli elementi che aggiungono alla tua stringa risulteranno costosi in quanto molto probabilmente dovrai ridistribuire un po 'di memoria affinché questa operazione si verifichi.
Quindi, linguaggi diversi adottano approcci diversi a questi problemi. Java, ad esempio, si è preso la libertà di rendere le sue stringhe immutabili per alcune valide ragioni (lunghezza di cache, sicurezza dei thread) e per le sue controparti mutabili (StringBuffer e StringBuilder) sceglierà di allocare le dimensioni utilizzando chunk di dimensioni maggiori per non dover allocare ogni volta, ma piuttosto sperare per i migliori scenari di casi. In genere funziona bene, ma il lato negativo è a volte pagare per gli impatti della memoria.
Inoltre, e di nuovo questo è dovuto al fatto che il rivestimento sintetico dello zucchero della tua lingua nasconde questo a te per giocare bene, spesso non pensi che termini di supporto unicode (specialmente finché non lo fai ne hanno davvero bisogno e colpiscono quel muro). E alcuni linguaggi, essendo lungimiranti, non implementano stringhe con array sottostanti di semplici primitive di char a 8 bit. Hanno cotto in UTF-8 o UTF-16 o cosa-hai-tu supporto per te, e la conseguenza è un consumo di memoria tremendamente più grande, che spesso non è necessario, e un tempo di elaborazione più grande per allocare memoria, elaborare le stringhe, e implementare tutta la logica che va di pari passo con la manipolazione dei punti di codice.
Il risultato di tutto questo è che quando si fa qualcosa di equivalente in pseudo-codice a:
hello = "hello,"
world = " world!"
str = hello + world
Potrebbe non essere - nonostante tutti i migliori sforzi che gli sviluppatori di linguaggi hanno fatto per far sì che si comportassero come faresti, ad eccezione di:
a = 1;
b = 2;
shouldBeThree = a + b
Come follow-up, potresti voler leggere:
La frase "operazione media" è probabilmente una scorciatoia per una singola operazione di una macchina a programma memorizzato con accesso casuale teorica . Questa è la macchina teorica che è consuetudine utilizzare per analizzare il tempo di esecuzione di vari algoritmi.
Le operazioni generiche sono normalmente prese per caricare, aggiungere, sottrarre, memorizzare, ramificare. Forse anche leggere, stampare e fermare.
Ma molte operazioni con le stringhe richiedono molte di queste operazioni fondamentali. Ad esempio, la duplicazione di una stringa richiede normalmente un'operazione di copia e quindi un numero di operazioni che è proporzionale alla lunghezza di una stringa (ovvero, è "lineare"). Trovare una sottostringa all'interno di un'altra stringa ha anche una complessità lineare.
Dipende completamente dall'operazione, dal modo in cui le stringhe sono rappresentate e da quali ottimizzazioni esistono. Se le stringhe sono lunghe 4 o 8 byte (e allineate), non sarebbero necessariamente più lente - molte operazioni sarebbero veloci come le primitive. Oppure, se tutte le stringhe hanno un hash a 32 o 64 bit, anche molte operazioni saranno altrettanto veloci (anche se pagherai il costo di hashing in anticipo).
Dipende anche da cosa intendi per "lento". La maggior parte dei programmi elaborerà le stringhe molto velocemente per ciò che è necessario. I confronti tra stringhe potrebbero non essere veloci come confrontare due interi, ma solo la profilazione rivelerà cosa significa "lento" per il tuo programma.
Permettimi di rispondere alla tua domanda con una domanda. Perché pronunciare una stringa di parole richiede più tempo di una singola parola?
Leggi altre domande sui tag strings computer-science