Algoritmo de classificação para Excel / SharedStrings

No Excel, eles 'compactam' seqüências de caracteres em um mapeamento numérico (embora não tenha certeza de que a palavra compactar esteja correta neste caso). Aqui está um exemplo mostrado abaixo:

Embora isso ajude a reduzir o tamanho total do arquivo e o espaço ocupado pela memória, como o Excel faz a classificação em um campo de seqüência de caracteres? Cada cadeia de caracteres precisaria passar pelo mapeamento de pesquisa: e, nesse caso, isso não aumentaria muito o custo de desacelerar a classificação em um campo de string (e se houvesse valores de 1 milhão, as pesquisas de chave de 1 milhão não seriam trivial). Duas perguntas sobre isso:

1. As seqüências compartilhadas são usadas no próprio aplicativo Excel ou apenas ao salvar os dados?
2. Qual seria um exemplo de algoritmo para classificar no campo? Qualquer linguagem é adequada (c, c #, c ++, python).

Não consigo encontrar exatamente como o Excel armazena células com SharedStringTableelementos na memória em tempo de execução, mas armazená-las como um índice do item SharedStringTablerequer apenas uma desreferência extra para acessá-las, supondo que os elementos sejam armazenados como uma matriz. Então, meu palpite é que é assim que é feito. Essa é a maneira mais simples e a única maneira de torná-la mais rápida é ter uma representação em tempo de execução SharedStringTablejá classificada por elementos. Nesse caso, classificar por um índice é equivalente a classificar pelo valor. Essa abordagem, no entanto, torna a operação de inserção dispendiosa, como quando uma nova string é inserida no meio da tabela, todos os índices maiores do que deveriam ser incrementados e o número de células desse documento no documento pode ser muito grande, até todos os índices. células referentes a SharedStringTable.

Se as células contiverem índices iguais aos do arquivo, veja como ordenar as células representadas pelo columnValuevetor com base nas cadeias que elas apontam para armazenadas no sharedStringsvetor (em C ++, pois você disse que não há diferença) a um custo de 2 desreferências extras por operação de comparação:

// sort indexes from columnValue based on comparing values in sharedStrings
sort(columnValue.begin(), columnValue.end(), 
     [&sharedStrings](size_t i1, size_t i2){return sharedStrings[i1] < sharedStrings[i2];});

Não estava no OP, mas a SharedStringTableoperação de pesquisa inversa é lenta e o armazenamento em cache de elementos em um dicionário ajuda.

Tabela de cadeias compartilhadas do Microsoft Excel

A tabela de cadeias compartilhadas é e o padrão Open XML, conforme definido pelo padrão ISO - ISO / IEC 29500-1: 2016 (E)

Definição oficial de strings compartilhadas (citadas no documento ISO)

Tabela de cadeias compartilhadas

Os valores de sequência podem ser armazenados diretamente dentro dos elementos das células da planilha; no entanto, armazenar o mesmo valor dentro de vários elementos de célula pode resultar em partes da planilha muito grandes, possivelmente resultando em degradação do desempenho. A Tabela de cadeias compartilhadas é uma lista indexada de valores de cadeias, compartilhada na pasta de trabalho, que permite que as implementações armazenem valores apenas uma vez.

O padrão ISO em Shared Strings pode ser baixado em

https://standards.iso.org/ittf/PubliclyAvailableStandards/c071691_ISO_IEC_29500-1_2016.zip

Respostas às perguntas sobre este tópico

Pergunta 1: As cadeias compartilhadas são usadas no próprio aplicativo Excel ou apenas ao salvar os dados?

Resposta: As seqüências compartilhadas são usadas pelo Excel somente no momento de salvar o documento, IE, apenas com o objetivo de armazenar a planilha como um arquivo no armazenamento.

No entanto, quando o arquivo é aberto para exibição, as células são preenchidas com valores de cadeia reais extraídos da tabela de cadeias compartilhadas.

-

Pergunta 2: Qual seria um exemplo de algoritmo para classificar no campo? Qualquer linguagem é adequada (c, c #, c ++, python).

Resposta: Para um aplicativo como o Excel, acho que uma variação proprietária especial da classificação Rápida é o algoritmo mais provável a ser usado para classificar os valores das strings.

O Excel tem um limite de 1.048.576 linhas. Para esse tamanho, a classificação rápida é definitivamente um vencedor. A ordenação rápida pode produzir resultados muito eficientes para um conjunto de dados dessa magnitude.

Aqui está o link para a implementação da Classificação Rápida em C ++ para classificar seqüências de caracteres:

http://www.cplusplus.com/forum/beginner/101599/