Se strings são imutáveis ​​no .NET, por que o Substring toma O (n) time?

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

ou seja, quais foram os tradeoffs, se houver?

ATUALIZAÇÃO: Gostei muito dessa pergunta, acabei de blogar. Veja Cordas, imutabilidade e persistência


A resposta curta é: O (n) é O (1) se n não crescer muito. A maioria das pessoas extrai substrings minúsculas de strings minúsculas, então, como 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 memory do original com apenas uma pequena quantidade (tipicamente 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 são tipicamente feitas em cadeias de caracteres em programas .NET, é de todo modo relevante dificilmente pior para simplesmente criar uma string inteiramente nova. A despesa e a dificuldade de construir uma estrutura de dados persistente complexa não se pagam.

As pessoas normalmente usam “substring” para extrair uma string curta – digamos, dez ou vinte caracteres – de uma string 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á dúzia. Alocação de strings e cópia de memory de cinquenta bytes é incrivelmente rápida em hardware moderno. Que criar uma nova estrutura de dados que consista em um ponteiro para o meio de uma string existente mais um comprimento também seja surpreendentemente rápido é irrelevante; “rápido o suficiente” é por definição rápido o suficiente.

Os substrings extraídos são tipicamente pequenos em tamanho e curtos na vida; o coletor de lixo vai recuperá-los em breve, e eles não ocuparam muito espaço na pilha em primeiro lugar. Portanto, usar uma estratégia persistente que incentive a reutilização da maior parte da memory também não é uma vitória; Tudo o que você fez foi fazer com que seu coletor de lixo ficasse mais lento, porque agora ele precisa se preocupar com o manuseio de indicadores internos.

Se as operações de substring que as pessoas normalmente faziam em strings fossem completamente diferentes, faria sentido seguir uma abordagem persistente. Se as pessoas normalmente tinham cadeias de milhões de caracteres e extraíam milhares de substrings sobrepostas com tamanhos na faixa de cem mil caracteres, e essas substrings viviam muito tempo na pilha, então faria todo o sentido ir com uma substring persistente abordagem; seria um desperdício e uma tolice não. Mas a maioria dos programadores de linha de negócios não faz nada nem que seja vagamente parecida com esse tipo de coisa . O .NET não é uma plataforma adaptada às necessidades do Projeto Genoma Humano; Os programadores de análise de DNA têm que resolver problemas com essas características de uso de string todos os dias; as probabilidades são boas que você não faz. Os poucos que constroem suas próprias estruturas de dados persistentes que correspondem de perto a seus cenários de uso.

Por exemplo, minha equipe escreve programas que fazem análises dinâmicas de códigos C # e VB à medida que você os digita. Alguns desses arquivos de código são enormes e, portanto, não podemos fazer manipulação de strings O (n) para extrair substrings ou inserir ou excluir caracteres. Criamos várias estruturas de dados persistentes e imutáveis ​​para representar edições a um buffer de texto que nos permitem reutilizar com eficiência e rapidez a maior parte dos dados de string existentes e as análises lexicais e sintáticas existentes em uma edição típica. Este foi um problema difícil de resolver e sua solução foi estreitamente adaptada ao domínio específico da edição de código C # e VB. Seria irreal esperar que o tipo de string interno resolvesse esse problema para nós.

Precisamente porque Strings são imutáveis, .Substring deve 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 vários bytes em tempo constante ?


EDIT: Mehrdad sugere não copiar a seqüência de caracteres, mas mantendo uma referência a uma parte dela.

Considere no .net, uma seqüência de vários megabytes, em que alguém chama .SubString(n, n+3) (para qualquer n no meio da seqüência de caracteres).

Agora, a string INTEIRO não pode ser Coleta de lixo apenas porque uma referência está mantendo 4 caracteres? Isso parece um desperdício de espaço ridículo.

Além disso, o rastreamento de referências a substrings (que podem até estar dentro de substrings) e a tentar copiar em momentos ideais para evitar a derrota do GC (como descrito acima), torna o conceito um pesadelo. É muito mais simples, e mais confiável, copiar em .SubString e manter o modelo simples e imutável.


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

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 memory.

O simples .substring(...) compartilha a matriz de char usada internamente com o object String original, que você, então, com a new String(...) pode copiar para uma nova matriz, se necessário (para evitar impedir a garbage collection da original 1).

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

Java usado para referenciar strings maiores, mas:

O Java também mudou seu comportamento para copiar , evitando vazamentos de memory.

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

Se a substring tiver pelo menos metade do tamanho do pai, pode-se fazer referência ao pai. Caso contrário, pode-se apenas fazer uma cópia. Isso evita vazamento de muita memory enquanto ainda fornece um benefício significativo.

Nenhuma das respostas aqui abordou “o problema de bracketing”, o que significa que strings no .NET são representadas como uma combinação de um BStr (o comprimento armazenado na memory “antes” do ponteiro) e um CStr (a string termina em um ‘\ 0’).

A string “Hello there” é 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 declaração fixed o ponteiro apontaria para o 0x48.)

Essa estrutura permite a pesquisa rápida do tamanho 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 null.

Quando você faz Substring(0, 5) o “oh, mas eu prometi que haveria um caractere nulo após o último caractere” regra diz que você precisa fazer uma cópia. Mesmo se você obtivesse a substring no final, não haveria lugar para colocar o comprimento sem corromper as outras variables.


Às vezes, porém, você realmente quer falar sobre “o meio da string”, e você não necessariamente se preocupa com o comportamento do P / Invoke. A estrutura ReadOnlySpan adicionada recentemente pode ser usada para obter uma substring no-copy:

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

O ReadOnlySpan “substring” armazena o comprimento de forma independente 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”, já que não possui características BStr ou CStr (muito menos ambas). Se você nunca (diretamente) P / Invoke, então não há muita diferença (a menos que a API que você deseja chamar não tenha uma sobrecarga ReadOnlySpan ).

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

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