Por que as cordas são tão lentas?

23

Desde a minha primeira aula de programação no ensino médio, ouvi dizer que as operações com strings são mais lentas - ou seja, mais caras - do que a mítica "operação média". Por que os torna tão lentos? (Esta questão foi deixada intencionalmente ampla.)

Pops
fonte
11
Se você sabe que essas "operações médias" são míticas, você pode pelo menos nos dizer o que são algumas delas? Dado que você está fazendo uma pergunta tão vaga, é difícil confiar em sua afirmação de que essas operações não especificadas são realmente míticas.
seh
1
@ seh, infelizmente, na verdade não posso responder a isso. Nas poucas vezes em que perguntei às pessoas o que são mais lentas, elas meio que dão de ombros e dizem "são lentas". Além disso, se eu tivesse informações mais específicas, isso seria uma pergunta para SO, não para programadores; já é meio que limítrofe.
Pops
Qual é o ponto ? Se as strings contadas forem realmente lentas, você vai parar de usá-las?
Tulains Córdova
Esqueça. Se alguém lhe disser esse absurdo, a contra-pergunta é: "Sério? Eles são? Devemos usar uma matriz int então?"
Ingo

Respostas:

47

"A operação média" ocorre nas primitivas. Mas, mesmo em idiomas em que as strings são tratadas como primitivas, elas ainda estão dispostas sob o capô, e fazer qualquer coisa que envolva toda a string leva tempo O (N), onde N é o comprimento da string.

Por exemplo, adicionar dois números geralmente requer 2-4 instruções ASM. Concatenar ("adicionar") duas strings requer uma nova alocação de memória e uma ou duas cópias de strings, envolvendo a string inteira.

Certos fatores de linguagem podem piorar as coisas. Em C, por exemplo, uma string é simplesmente um ponteiro para uma matriz de caracteres terminada em nulo. Isso significa que você não sabe quanto tempo leva; portanto, não há como otimizar um loop de cópia de cadeia com operações de movimentação rápida; você precisa copiar um caractere de cada vez para poder testar cada byte para o terminador nulo.

Mason Wheeler
fonte
4
E certas linguagens o tornam muito melhor: a codificação do comprimento da string pelo Delphi no início da matriz torna a concatenação muito rápida.
97510 Frank Shearar
4
@ gablin: Isso também ajuda, fazendo com que a string se copie muito mais rapidamente. Quando você conhece o tamanho antecipadamente, não precisa copiar um byte de cada vez e verificar se há um terminador nulo em cada byte, para que você possa usar o tamanho total de qualquer registro, incluindo o SIMD, para movimentação de dados, até 16 vezes mais rápido.
Mason Wheeler
4
@mathepic: Sim, e isso é bom até onde for necessário, mas quando você começa a interagir com libc ou outro código externo, espera um char*, não um strbuf, e você volta à estaca zero. Isso pode ser feito quando um design incorreto é inserido no idioma.
Mason Wheeler
6
@mathepic: Claro que o bufponteiro está lá. Eu nunca quis dizer que não está disponível; pelo contrário, é necessário. Qualquer código que não saiba sobre seu tipo de string otimizado, mas fora do padrão, incluindo coisas tão fundamentais quanto a biblioteca padrão , ainda precisa recorrer ao lento e inseguro char*. Você pode chamar isso de FUD, se quiser, mas isso não faz com que não seja verdade.
Mason Wheeler
7
Gente, existe uma coluna de Joel Spolsky sobre o argumento de Frank Shearer: Back to Basics
user16764
14

Este é um tópico antigo e acho que as outras respostas são ótimas, mas ignoram alguma coisa, então aqui estão meus 2 centavos (atrasados).

Revestimento sintático de açúcar esconde complexidade

O problema com as strings é que eles são cidadãos de segunda classe na maioria dos idiomas e, na maioria das vezes, na verdade não fazem parte da própria especificação de idioma: eles são uma construção implementada em uma biblioteca com um revestimento sintático ocasional de açúcar no topo para torná-los menos dolorosos de usar.

A conseqüência direta disso é que a linguagem esconde grande parte de sua complexidade da sua vista e você paga pelos efeitos colaterais sorrateiros, porque adquire o hábito de considerá-los como uma entidade atômica de baixo nível, assim como outros tipos primitivos (como explicado pela resposta mais votada e outras).

Detalhes da implementação

Good Ol 'Array

Um dos elementos dessa "complexidade" subjacente é que a maioria das implementações de cadeias recorreria ao uso de uma estrutura de dados simples com algum espaço de memória contíguo para representar a cadeia: sua boa e velha matriz.

Isso faz sentido, lembre-se, pois você deseja que o acesso à cadeia como um todo seja rápido. Mas isso implica custos potencialmente terríveis quando você deseja manipular essa sequência. O acesso a um elemento no meio pode ser rápido se você souber qual índice procura , mas a procura de um elemento com base em uma condição não é.

Até o retorno do tamanho da string pode ser caro, se o seu idioma não armazenar em cache o comprimento da string e precisar percorrê-la para contar caracteres.

Por razões semelhantes, a adição de elementos à sua cadeia de caracteres será dispendiosa, pois você provavelmente precisará realocar um pouco de memória para que esta operação ocorra.

Portanto, idiomas diferentes adotam abordagens diferentes para esses problemas. O Java, por exemplo, teve a liberdade de tornar suas seqüências imutáveis ​​por alguns motivos válidos (tamanho do cache, segurança de threads) e, por suas contrapartes mutáveis ​​(StringBuffer e StringBuilder), optar por alocar tamanho usando blocos de tamanho maior para não precisar alocar sempre, mas sim espere os melhores cenários. Geralmente funciona bem, mas o lado ruim é pagar às vezes por impactos na memória.

Suporte Unicode

Além disso, e novamente, isso se deve ao fato de o revestimento sintático de açúcar do seu idioma esconder isso de você para ser agradável, geralmente você não considera termos de suporte unicode (especialmente enquanto você realmente não precisar dele) e bateu nessa parede). E algumas linguagens, com visão de futuro, não implementam seqüências de caracteres com matrizes subjacentes de primitivas char simples de 8 bits. Eles são compatíveis com UTF-8 ou UTF-16 ou o que você tem para você, e a conseqüência é um consumo de memória tremendamente maior, que muitas vezes não é necessário, e um tempo de processamento maior para alocar memória, processar as seqüências de caracteres, e implemente toda a lógica que anda de mãos dadas com a manipulação de pontos de código.


Os resultados de tudo isso é que, quando você faz algo equivalente no pseudo-código a:

hello = "hello,"
world = " world!"
str = hello + world

Pode não ser - apesar de todos os melhores esforços que os desenvolvedores de linguagem enviam para que eles se comportem como você exceto - - simples como:

a = 1;
b = 2;
shouldBeThree = a + b

Como acompanhamento, você pode querer ler:

haylem
fonte
Boa adição à discussão atual.
Abel
Acabei de perceber que esta é a melhor resposta, porque a declaração mítica pode ser aplicada a qualquer coisa como a criptografia RSA é lenta. A única razão para a string ser colocada nesse ponto embaraçoso é que o operador plus forneceu strings na maioria dos idiomas, o que faz com que os novatos não tenham conhecimento do custo por trás da operação.
Codism
@ Abel: obrigado, me pareceu que havia espaço para detalhes mais genéricos.
haylem
@ Codism: obrigado, feliz que você gostou. Na verdade, acho que isso pode ser aplicado a muitos casos em que é apenas uma questão de complexidade estar oculta (e de não prestarmos mais tanta atenção aos detalhes de nível inferior até que finalmente precisamos, porque atingimos algum tipo de gargalo ou parede de tijolos )
haylem
1

A frase "operação média" provavelmente é uma abreviação para uma única operação de uma máquina teórica de Programa Armazenado de Acesso Aleatório . Essa é a máquina teórica que costuma ser usada para analisar o tempo de execução de vários algoritmos.

As operações genéricas são normalmente consideradas como carregar, adicionar, subtrair, armazenar e ramificar. Talvez também leia, imprima e pare.

Mas a maioria das operações de cadeia exige várias dessas operações fundamentais. Por exemplo, duplicar uma sequência normalmente requer uma operação de cópia e, portanto, várias operações que são proporcionais ao comprimento de uma sequência (ou seja, é "linear"). Encontrar uma substring dentro de outra string também tem complexidade linear.

James Youngman
fonte
1

Depende completamente da operação, como as strings são representadas e quais otimizações existem. Se as strings tiverem 4 ou 8 bytes de comprimento (e alinhadas), elas não seriam necessariamente mais lentas - muitas operações seriam tão rápidas quanto as primitivas. Ou, se todas as cadeias tiverem um hash de 32 ou 64 bits, muitas operações também serão rápidas (embora você pague o custo do hash antecipadamente).

Também depende do que você quer dizer com "lento". A maioria dos programas processa as strings com bastante rapidez para o que é necessário. As comparações de string podem não ser tão rápidas quanto comparar duas entradas, mas apenas a criação de perfil revelará o que "lento" significa para o seu programa.

Kevin Hsu
fonte
0

Deixe-me responder sua pergunta com uma pergunta. Por que dizer uma sequência de palavras leva mais tempo do que dizer uma única palavra?

ChaosPandion
fonte
2
Não necessariamente.
user16764
3
Supercalifragilisticexpialidocious
Spoike
s / palavra / sílaba / g
Caleb
Deixe-me responder sua pergunta-resposta com uma pergunta: por que você não diz o que sua resposta significa? Afinal, está longe de ser claro como isso pode ser interpretado como aplicável a algum sistema de tempo de execução.
PJTraill