Existe algum cenário onde a Corda estrutura de dados é mais eficiente do que uma cadeia de construtor

Question

Relacionados esta pergunta, com base em um comentário do usuário Eric Lippert.

Há qualquer cenário onde o Corda estrutura de dados é mais eficiente do que uma cadeia de construtor?É que algumas pessoas da opinião de que a corda estruturas de dados, quase nunca são de melhor em termos de velocidade do que o nativo de seqüência de caracteres ou string o construtor de operações em casos típicos, por isso estou curioso para ver cenários realistas, onde, de fato, as cordas são melhores.

Answer 1

A documentação para a SGI implementação C++ vai para algum detalhe sobre o big O comportamentos versos os fatores constantes, que é muito instrutivo.

Sua documentação assume cadeias muito estar envolvido, os exemplos colocou para referência de falar sobre 10 MB de cadeias de caracteres.Muito poucos programas serão escritos que lidar com essas coisas e, para muitas classes de problemas com tais requisitos reformulação-los para ser corrente ao invés de exigir que a seqüência completa para estar disponível sempre que possível irá levar a resultados significativamente superior.Como os cabos para a transmissão de manipulação de multi megabyte seqüências de caracteres quando você é capaz de tratar adequadamente os de corda como as secções (si cordas), em vez de apenas uma seqüência de caracteres.

Significativo Prós:

• Concatenação/Inserção de tornar-se quase constante de tempo de operações
• Determinadas operações podem reutilizar o anterior corda seções para permitir o compartilhamento de memória.
  • Note-se que .Net cadeias, ao contrário de cadeias de java não compartilham o buffer de caracteres em textos - uma escolha com prós e contras em termos de espaço de memória.Cordas tendem a evitar esse tipo de problema.
• Cordas permitir diferidos carregamento de subcadeias de caracteres até que seja necessário
  • Note que isto é difícil de obter a direita, muito fácil de compor inútil, devido à excessiva ânsia de acesso e requer consumir código para tratá-lo como uma corda, não como uma seqüência de caracteres.

Significativo Contras:

• Leitura aleatória de acesso torna-se O(log n)
• Os fatores constantes no sequencial acesso de leitura parecem ser entre 5 e 10
• o uso eficiente da API requer tratando-o como uma corda, não apenas caindo em uma corda como um apoio a implementação do 'normal' cadeia de api.

Isto leva a alguns 'óbvio' usa (o primeiro mencionado explicitamente pela SGI).

• Editar buffers de grandes arquivos, permitindo a fácil desfazer/refazer
  • Observe que, em algum momento você pode precisar para gravar as alterações para o disco, envolvendo transmissão em sequência através de toda a cadeia, de modo que este só é útil se a maioria das edições, principalmente, residem na memória ao invés de exigir que frequente a persistência (diga-se através de uma função autosave)
• Manipulação de segmentos de DNA significativa de manipulação ocorre, mas muito pouco, de saída, na verdade, acontece
• Multi-threaded Algoritmos que transformam local subseções de seqüência de caracteres.Na teoria, tais casos pode ser dividida fora para separar linhas e núcleos sem precisar tirar cópias locais das subseções e, em seguida, combina-los, com uma notável economia de memória, bem como evitar o alto custo de série combinando operação no final.

Há casos em que o domínio específico de comportamento na cadeia de caracteres pode ser acoplado com relativamente simples implantes cibernéticos para a Corda de implementação de forma a permitir:

• Leia somente strings com um número significativo de subseqüências comuns são passíveis de simples estagiando para a significativa economia de memória.
• Cadeias de caracteres com escassa estruturas ou locais significativos de repetição são passíveis de codificação de comprimento de execução, permitindo ainda a níveis razoáveis de acesso aleatório.
• Onde a seqüência de sub-rotina limites são de si mesmos "nós", onde a informação pode ser armazenada, embora tais estruturas são bastante possível melhor feito como um Base Trie se eles são raramente modificadas, mas muitas vezes ler.

Como você pode ver a partir dos exemplos listados, todos caem bem para o 'nicho' categoria.Além disso, diversos pode muito bem ter alternativas superiores se você estiver disposto/capaz de reescrever o algoritmo como um fluxo de operação de processamento em vez disso.

Answer 2

A resposta curta a esta pergunta é sim, e isso requer pouca explicação. É claro que existem situações em que a estrutura de dados da corda é mais eficiente que um construtor de cordas. Eles funcionam de maneira diferente, por isso são mais adequados para diferentes propósitos.

(De uma perspectiva C#)

A estrutura de dados da corda como árvore binária é melhor em determinadas situações. Quando você está olhando para valores de string extremamente grandes (pense em mais de 100 Mb de XML do SQL), a estrutura de dados da corda pode manter todo o processo fora da pilha de objeto grande, onde o objeto String o atinge quando passa 85000 bytes.

Se você está olhando para strings de 5-1000 caracteres, provavelmente não melhora o desempenho o suficiente para valer a pena. Este é outro caso de uma estrutura de dados projetada para 5% das pessoas que têm uma situação extrema.

Answer 3

o 10º concurso de programação ICFP confiou, basicamente, nas pessoas que usam a estrutura de dados da corda para uma solução eficiente. Esse foi o grande truque para obter uma VM que passou por um tempo razoável.

A corda é excelente se houver muita prefixação (aparentemente a palavra "preventiva" é composta por pessoas e não é uma palavra adequada!) E potencialmente melhor para inserções; Os stringbuilders usam memória contínua; portanto, trabalhe apenas com eficiência para anexar.

Portanto, o StringBuilder é ótimo para construir seqüências de caracteres anexando fragmentos - um caso de uso muito normal. Como os desenvolvedores precisam fazer isso muito, os Stringbuilders são uma tecnologia muito popular.

As cordas são ótimas para editar buffers, por exemplo, a estrutura de dados por trás, digamos, uma textarea de força corporativa. Portanto (um relaxamento de cordas, por exemplo, uma lista vinculada de linhas em vez de uma árvore binária) é muito comum no mundo da interface do usuário, mas isso não é frequentemente exposto aos desenvolvedores e usuários desses controles.

Você precisa de quantidades realmente grandes de dados e rotatividade para fazer o pagamento da corda-os processadores são muito bons nas operações do fluxo e, se você tiver a RAM, simplesmente realista para prefixar funciona de forma aceitável para casos de uso normais. Essa concorrência mencionada no topo foi a única vez que eu vi isso.

Answer 4

Os editores de texto mais avançados representam o corpo de texto como um "tipo de corda" (embora na implementação, as folhas geralmente não sejam caracteres individuais, mas o texto é executado), principalmente para melhorar as inserções e exclusão frequentes em textos grandes.

Geralmente, o StringBuilder é otimizado para anexar e tenta minimizar o Número total de realações Sem geral, ocupar muito. A garantia típica é (alocações log2 n e menos de 2,5x a memória). Normalmente, a string é construída uma vez e pode ser usada por um bom tempo sem ser modificada.

A corda é otimizada para inserções e remoções frequentes e tenta minimizar quantidade de dados copiados (por um número maior de alocações). Em uma implementação linear de buffer, cada inserção e exclusão se torna O (n) e você geralmente precisa representar inserções de caracteres únicas.

Answer 5

As VMs JavaScript geralmente usam cordas para cordas.

Maxime Chevalier-Boisvert, desenvolvedor da Higgs JavaScript VM, diz:

No JavaScript, você pode usar matrizes de cordas e, eventualmente Construa -os incrementalmente. As cadeias de JS são imutáveis; portanto, se isso não for otimizado internamente, o anexo incremental é O (n2). Eu acho que é provável que as cordas tenham sido implementadas nos mecanismos JS especificamente por causa dos benchmarks de jogador solar que são anexos a string. Os implementadores do JS Engine usaram cordas para ganhar uma vantagem sobre os outros, fazendo algo que antes era mais lento. Se não foi por esses benchmarks, acho que choram da comunidade sobre a cordas que anexam o desempenho ruim podem ter sido recebidas com "Use Array.prototype.Join, Dummy!".

Também.