Melhor abordagem para a realização de grandes documentos editáveis ??na memória

StackOverflow https://stackoverflow.com/questions/838712

Pergunta

Eu preciso para manter uma representação de um documento na memória, e estou procurando a maneira mais eficiente de fazer isso.

Pressupostos

  • Os documentos podem ser muito grande, até 100MB.
  • Mais frequentemente do que não o documento permanecerá inalterada - (ou seja, eu não quer fazer frente até desnecessário processamento).
  • Alterações será tipicamente muito perto um ao outro no documento (isto é, quanto o usuário digita).
  • Deve ser possível aplicar alterações rápidas (sem copiar todo o documento)
  • As alterações serão aplicadas em termos de compensações e / texto excluído nova (não como linha / col).
  • Para trabalho em C #

Considerações atuais

  • Armazenar os dados como uma string. Fácil de código, rápido de conjunto, muito lento para atualização.
  • Array of Lines, moderatly fácil de código, mais lento para set (como nós temos que analisar a cadeia em linhas), mais rápido para atualização (como podemos inserir linhas sair facilmente, mas encontrar compensações requer soma comprimentos de linha).

Deve haver uma carga de algoritmos padrão para este tipo de coisa (não é um milhão de milhas de alocação de disco e fragmentação).

Obrigado por seus pensamentos.

Foi útil?

Solução

Eu sugeriria para quebrar o arquivo em blocos. Todos os blocos têm o mesmo comprimento quando você carregá-los, mas o comprimento de cada bloco pode mudar se o usuário edita este blocos. Isso evita que se deslocam de 100 megabytes de dados se o usuário insere um byte na frente.

Para gerenciar os blocos, apenas, mas eles - juntamente com o deslocamento de cada bloco - em uma lista. Se o usuário modifica um comprimento blocos só deve atualizar os deslocamentos dos blocos após este. Para encontrar um offset, você pode usar busca binária.

Tamanho: 100 MiB
Tamanho do bloco: 16 Kib
Blocks: 6400

Encontrar uma busca binária utilizando offset (pior caso): 13 passos
Modificar um bloco (pior caso): Copiar 16384 bytes de dados e atualização de 6400 compensações bloco
Modificar um bloco (caso médio): copiar 8192 bytes de dados e atualização de 3200 compensações bloco

16 tamanho do bloco Kib é apenas um exemplo aleatório - você pode equilibrar os custos das operações, escolhendo o tamanho do bloco, talvez com base no tamanho do arquivo e a probabilidade de operações. Fazendo alguma matemática simples irá produzir o tamanho de bloco ideal.

Carregando vai ser muito rápido, porque você carga fixa blocos de tamanho, e salvando deve executar bem, também, porque você terá que escrever alguns milhares de blocos e não milhões de linhas simples. Você pode otimizar o carregamento por blocos de carga apenas sob demanda e você pode otimizar salvar apenas por salvar todos os blocos que mudou (conteúdo ou offset).

Finalmente, a implementação não será para o disco também. Você poderia usar apenas a classe StringBuilder para representar um bloco. Mas esta solução não vai funcionar bem para muito longas linhas com comprimentos comparáveis ??ao tamanho do bloco ou maiores, porque você vai ter que carregar vários blocos e exibir apenas pequenas partes com o resto sendo à esquerda ou à direita da janela. Eu suponho que você terá que usar um modelo de particionamento bidimensional neste caso.

Outras dicas

Boa matemática, Bad Math escreveu um excelente artigo sobre cordas e gap tampão sa tempo atrás que detalha os métodos padrão para representar arquivos de texto em um editor de texto, e até mesmo compara-los para simplicidade de implementação e desempenho. Em poucas palavras: um buffer lacuna - uma matriz de caracteres grande, com uma seção vazia imediatamente após a posição atual do cursor - é a sua aposta mais simples e melhor

.

Você pode encontrar este papel útil --- Estruturas de Dados de Sequências de texto que descreve e analisa experimentalmente alguns algoritmos padrão, e compara [entre outras coisas] buffers gap e mesas peça.

FWIW, conclui tabelas peças são ligeiramente melhor no geral; embora net.wisdom parece preferir buffers gap.

eu usaria um b-árvore ou lista de linhas ou blocos maiores pule se você não está indo para editar muito.

Você não tem muito custo extra determinar extremidades da linha de carga, desde que você tem que visitar cada personagem no carregamento de qualquer maneira.

Você pode mover linhas dentro de um nó sem muito esforço.

O comprimento total do texto em cada nó é armazenado no nó e mudanças propagadas até nós pai.

Cada linha é representado por uma matriz de dados, e o índice inicial, comprimento e capacidade. quebra de linha / símbolos de retorno não são colocados na matriz de dados. operações comuns, tais como linhas de ruptura requer apenas alterações às referências na matriz; editar linhas requer uma cópia se a capacidade é excedida. Uma estrutura similar pode ser usado por linha temporariamente ao editar essa linha, então você não executar uma cópia em cada tecla-prima.

Em cima da minha cabeça, eu teria pensado que uma lista ligada indexados seria bastante eficiente para esse tipo de coisa, a menos que você tenha algum muito linhas longas.

A lista ligada iria dar-lhe uma forma eficiente de armazenar os dados e adicionar ou remover linhas como as edições do usuário. A indexação permite saltar rapidamente para um ponto específico no seu arquivo. Este tipo de idéia se presta bem a operações do tipo undo / redo também como ele deve ser razoavelmente fácil de edições de ordenação em pequenas operações atômicas.

Eu concordo com o ponto de crisb embora, provavelmente é melhor para obter algo simples trabalhar primeiro e depois ver se ele realmente é lento ..

De sua descrição parece muito com o seu documento for um texto não formatado única -. Modo a stringbuilder faria muito bem

Se seu um documento formatado, eu estaria inclinado a usar a Palavra APIs MS ou similar e apenas descarregar a sua processamento de documentos a eles - você vai economizar uma enorme quantidade de tempo que a análise de documentos pode muitas vezes ser uma dor no a * *: -)

Eu não ficar muito preocupado com o desempenho ainda - isso soa muito como você não ter implementado um ainda, então você também não sei o que as características de desempenho do resto do seu aplicativo tem - pode ser que você não pode realmente dar ao luxo de manter vários documentos na memória em tudo quando você realmente chegar redonda para perfilar-lo.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top