Se cadeias de caracteres são imutáveis ​​no .NET, por que o Substring leva O (n) tempo?

451

Dado que as strings são imutáveis ​​no .NET, estou me perguntando por que elas foram projetadas de tal forma que string.Substring()levam tempo O ( substring.Length), em vez de O(1)?

ou seja, quais foram as trocas, se houver?

user541686
fonte
3
@ Mehrdad: Eu gosto desta pergunta. Você poderia me dizer como podemos determinar O () de uma determinada função em .Net? Está claro ou devemos calculá-lo? Obrigado
odiseh
1
@odiseh: Às vezes (como neste caso) fica claro que a string está sendo copiada. Caso contrário, você pode procurar na documentação, executar benchmarks ou tentar procurar no código-fonte do .NET Framework para descobrir o que é.
user541686

Respostas:

423

ATUALIZAÇÃO: Gostei muito desta pergunta, apenas escrevi no blog. Veja Strings, imutabilidade e persistência


A resposta curta é: O (n) é O (1) se n não crescer grande. A maioria das pessoas extrai pequenos substrings de pequenos strings, de modo que a complexidade cresce assintoticamente é completamente irrelevante .

A resposta longa é:

Uma estrutura de dados imutável construída de tal forma que as operações em uma instância permitem a reutilização da memória do original com apenas uma pequena quantidade (normalmente O (1) ou O (lg n)) de cópia ou nova alocação é chamada de "persistente" estrutura de dados imutável. Strings no .NET são imutáveis; sua pergunta é essencialmente "por que eles não são persistentes"?

Porque quando você olha para operações que normalmente são feitas em cadeias de caracteres em programas .NET, é de todo modo relevante dificilmente pior simplesmente criar uma cadeia de caracteres totalmente nova. A despesa e a dificuldade de construir uma estrutura de dados persistente complexa não se paga.

As pessoas geralmente usam "substring" para extrair uma sequência curta - digamos, dez ou vinte caracteres - de uma sequência um pouco mais longa - talvez algumas centenas de caracteres. Você tem uma linha de texto em um arquivo separado por vírgula e deseja extrair o terceiro campo, que é um sobrenome. A linha terá talvez algumas centenas de caracteres, o nome será uma dúzia. A alocação de cadeias e a cópia de memória de cinquenta bytes é surpreendentemente rápida no hardware moderno. O fato de criar uma nova estrutura de dados que consiste em um ponteiro para o meio de uma string existente e um comprimento também é surpreendentemente rápido é irrelevante; "rápido o suficiente" é, por definição, rápido o suficiente.

As substrings extraídas são tipicamente pequenas em tamanho e curtas na vida útil; o coletor de lixo vai recuperá-los em breve e, em primeiro lugar, eles não ocuparam muito espaço na pilha. Portanto, usar uma estratégia persistente que incentive a reutilização da maior parte da memória também não é uma vitória; tudo o que você fez foi tornar seu coletor de lixo mais lento, porque agora ele precisa se preocupar com o manuseio de ponteiros internos.

Se as operações de substring que as pessoas realizavam em strings fossem completamente diferentes, faria sentido adotar uma abordagem persistente. Se as pessoas normalmente tivessem seqüências de caracteres de um milhão de caracteres e estivessem extraindo milhares de substratos sobrepostos com tamanhos na faixa de cem mil caracteres, e esses substratos vivessem muito tempo na pilha, faria todo o sentido usar uma substring persistente aproximação; seria um desperdício e tolice não. Mas a maioria dos programadores de linha de negócios não faz nada nem um pouco vagamente como esse tipo de coisa. O .NET não é uma plataforma adaptada às necessidades do Projeto Genoma Humano; Os programadores de análise de DNA precisam resolver problemas com essas características de uso de cadeias todos os dias; as chances são boas de que você não. Os poucos que constroem suas próprias estruturas de dados persistentes que se aproximam de seus cenários de uso.

Por exemplo, minha equipe escreve programas que fazem análises dinâmicas de código C # e VB enquanto você digita. Alguns desses arquivos de código são enormes e, portanto, não podemos manipular O (n) string para extrair substrings ou inserir ou excluir caracteres. Nós construímos um monte de estruturas de dados imutáveis persistentes para representar edições para um buffer de texto que nos permite de forma rápida e eficiente re-utilizar a maior parte dos dados de cadeia existentes e as análises lexicais e sintáticas existentes mediante uma edição típica. Este foi um problema difícil de resolver e sua solução foi adaptada de maneira restrita ao domínio específico da edição de código em C # e VB. Não seria realista esperar que o tipo de string interno resolva esse problema para nós.

Eric Lippert
fonte
47
Seria interessante contrastar como o Java o faz (ou pelo menos em algum momento no passado): Substring retorna uma nova string, mas aponta para o mesmo caractere [] que o maior - isso significa que o maior caractere [] não pode mais ser coletado como lixo até que a substring fique fora do escopo. Eu prefiro a implementação do .net de longe.
Michael Stum
13
Eu já vi esse tipo de código um pouco: string contents = File.ReadAllText(filename); foreach (string line in content.Split("\n")) ...ou outras versões dele. Quero dizer, leia um arquivo inteiro e processe as várias partes. Esse tipo de código seria consideravelmente mais rápido e exigiria menos memória se uma string fosse persistente; você sempre teria exatamente uma cópia do arquivo na memória em vez de copiar cada linha e, em seguida, as partes de cada linha conforme o processa. No entanto, como Eric disse - esse não é o caso de uso típico.
Configurator
18
@ configurador: Além disso, no .NET 4, o método File.ReadLines divide um arquivo de texto em linhas para você, sem precisar ler tudo na memória primeiro.
Eric Lippert
8
@ Michael: Java's Stringé implementado como uma estrutura de dados persistente (que não é especificada nos padrões, mas todas as implementações que eu conheço fazem isso).
Joachim Sauer
33
Resposta curta: É feita uma cópia dos dados para permitir a coleta de lixo da sequência original .
Qtax
121

Precisamente porque as Strings são imutáveis, .Substringdeve fazer uma cópia de pelo menos uma parte da string original. Fazer uma cópia de n bytes deve levar O (n) tempo.

Como você acha que copiaria um monte de bytes em tempo constante ?


EDIT: Mehrdad sugere não copiar a string, mas mantendo uma referência a uma parte dela.

Considere em .Net, uma sequência de vários megabytes, na qual alguém chama .SubString(n, n+3)(para qualquer n no meio da sequência).

Agora, a sequência INTEIRA não pode ser coletada como lixo apenas porque uma referência contém 4 caracteres? Isso parece um desperdício ridículo de espaço.

Além disso, rastrear referências a substrings (que podem até estar dentro de substrings) e tentar copiar nos horários ideais para evitar derrotar o GC (como descrito acima), torna o conceito um pesadelo. É muito mais simples e mais confiável copiar .SubStringe manter o modelo imutável direto.


EDIT: Aqui está uma boa leitura sobre o perigo de manter referências a substrings em cadeias maiores.

abelenky
fonte
5
+1: Exatamente meus pensamentos. Internamente, provavelmente usa o memcpyque ainda é O (n).
Leppie
7
@abelenky: Eu acho que talvez não copie nada? Já está lá, por que você deveria copiá-lo?
user541686
2
@ Mehrdad: SE você está atrás do desempenho. Apenas fique inseguro neste caso. Então você pode obter uma char*substring.
leppie
9
@ Mehrdad - você pode estar esperando muito por lá, é chamado StringBuilder , e é bom construir cordas. Não é chamado StringMultiPurposeManipulator
MattDavey
3
@ SamuelNeff, @ Mehrdad: seqüências de caracteres no .NET não são NULLencerradas. Conforme explicado no post de Lippert , os primeiros 4 bytes contêm o comprimento da string. É por isso que, como Skeet aponta, eles podem conter \0caracteres.
Elideb
33

O Java (em oposição ao .NET) fornece duas maneiras de fazer Substring(), você pode considerar se deseja manter apenas uma referência ou copiar uma substring inteira para um novo local de memória.

O simple .substring(...)compartilha a charmatriz usada internamente com o objeto String original, que você new String(...)pode copiar para uma nova matriz, se necessário (para evitar dificultar a coleta de lixo da original).

Eu acho que esse tipo de flexibilidade é a melhor opção para um desenvolvedor.

sll
fonte
50
Você chama isso de "flexibilidade", eu chamo de "Uma maneira de inserir acidentalmente um bug difícil de diagnosticar (ou um problema de desempenho) no software porque eu não sabia que tinha que parar e pensar em todos os lugares em que esse código poderia estar chamado de (incluindo aqueles que somente seriam inventados na próxima versão) apenas para obter 4 caracteres no meio de uma string "
Nir
3
downvote retraído ... Após uma navegação um pouco mais cuidadosa do código, ele se parece com uma substring em java que faz referência a uma matriz compartilhada, pelo menos na versão openjdk. E se você deseja garantir uma nova string, há uma maneira de fazer isso.
Don Roby
11
@ Nir: Eu chamo de "status quo viés". Para você, a maneira como Java faz isso parece cheia de riscos e a maneira .Net é a única opção sensível. Para programadores Java, o oposto é o caso.
Michael Borgwardt
7
Eu prefiro o .NET, mas isso parece uma coisa que o Java acertou. É útil que um desenvolvedor ser autorizados a ter acesso a um O (1) Substring método verdadeiramente (sem rolar o seu próprio tipo de cadeia, o que iria dificultar a interoperabilidade com todos os outros biblioteca, e não seria tão eficiente quanto um built-in solução ) A solução do Java é provavelmente ineficiente (requer pelo menos dois objetos de heap, um para a string original e outro para a substring); idiomas que suportam fatias substituem efetivamente o segundo objeto por um par de ponteiros na pilha.
Qwertie
10
Como o JDK 7u6 não é mais verdade - agora o Java sempre copia o conteúdo da String para cada um .substring(...).
Xaerxess #
12

Java costumava fazer referência a cadeias maiores, mas:

Java mudou seu comportamento para copiar também, para evitar vazamento de memória.

Eu sinto que isso pode ser melhorado: por que não fazer a cópia condicionalmente?

Se a substring tiver pelo menos metade do tamanho do pai, é possível fazer referência ao pai. Caso contrário, pode-se apenas fazer uma cópia. Isso evita o vazamento de muita memória e ainda oferece um benefício significativo.

user541686
fonte
Sempre copiar permite remover a matriz interna. Metade do número de alocações de heap, economizando memória no caso comum de cadeias curtas. Isso também significa que você não precisa pular um indireção adicional para cada acesso de personagem.
CodesInChaos
2
Penso que o importante é tirar isso do Java, que passou de usar a mesma base char[](com indicadores diferentes para o início e o fim) para criar um novo String. Isso mostra claramente que a análise de custo-benefício deve mostrar uma preferência pela criação de um novo String.
Filogenia
2

Nenhuma das respostas aqui abordou "o problema de bracketing", ou seja, as strings no .NET são representadas como uma combinação de um BStr (o tamanho armazenado na memória "antes" do ponteiro) e um CStr (a string termina em um '\ 0').

A cadeia "Olá" é assim representada como

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

(se atribuído a um char*em uma fixed-Declaração o ponteiro seria apontar para a 0x48.)

Essa estrutura permite uma pesquisa rápida do comprimento de uma string (útil em muitos contextos) e permite que o ponteiro seja passado em uma API P / Invoke to Win32 (ou outra) que espera uma string terminada em nulo.

Quando você faz Substring(0, 5)a regra "ah, mas eu prometi que haveria um caractere nulo após o último caractere", diz que você precisa fazer uma cópia. Mesmo que você tenha a substring no final, não haveria lugar para colocar o comprimento sem danificar as outras variáveis.


Às vezes, porém, você realmente quer falar sobre "o meio da cadeia" e não se importa necessariamente com o comportamento P / Invoke. A ReadOnlySpan<T>estrutura adicionada recentemente pode ser usada para obter uma substring sem cópia:

string s = "Hello there";
ReadOnlySpan<char> hello = s.AsSpan(0, 5);
ReadOnlySpan<char> ell = hello.Slice(1, 3);

A ReadOnlySpan<char>"substring" armazena o comprimento independentemente e não garante que haja um '\ 0' após o final do valor. Ele pode ser usado de várias maneiras "como uma string", mas não é "uma string", pois não possui características BStr ou CStr (muito menos as duas). Se você nunca (diretamente) P / Invoke, não há muita diferença (a menos que a API que você deseja chamar não tenha ReadOnlySpan<char>sobrecarga).

ReadOnlySpan<char>não pode ser usado como o campo de um tipo de referência, então também há ReadOnlyMemory<char>( s.AsMemory(0, 5)), que é uma maneira indireta de ter um ReadOnlySpan<char>, portanto as mesmas diferenças stringexistem.

Algumas das respostas / comentários das respostas anteriores falaram sobre ser um desperdício fazer com que o coletor de lixo mantenha uma sequência de milhões de caracteres enquanto você continua falando sobre 5 caracteres. Esse é precisamente o comportamento que você pode obter com a ReadOnlySpan<char>abordagem. Se você está apenas fazendo cálculos curtos, a abordagem ReadOnlySpan provavelmente é melhor. Se você precisar persistir por um tempo e manter apenas uma pequena porcentagem da string original, é melhor fazer uma substring adequada (para aparar o excesso de dados). Há um ponto de transição em algum lugar no meio, mas isso depende do seu uso específico.

bartonjs
fonte