O que são algoritmos eficientes para dicionários / conjuntos imutáveis? [fechadas]

5

O que são algoritmos eficientes para dicionários / conjuntos imutáveis? Por eficiente quero dizer que eles têm melhor ou comparável tempo e / ou desempenho de memória em comparação com suas versões mutáveis. Eu não quero necessariamente dizer isso no contexto da programação funcional, onde eu vi imutabilidade igualada a estruturas de dados persistentes.

Um exemplo concreto é Guava , em que tenho visto economia de memória quando usado com conjuntos que não precisam para ser modificado.

    
por Paul 15.12.2017 / 21:00
fonte

2 respostas

5

Existem estruturas de dados que são fáceis de ler e (relativamente) lentas de compilar, por isso tendem a ser mais adequadas para estruturas de dados imutáveis.

Por exemplo, para um conjunto mutável, você normalmente usa algum tipo de estrutura em árvore (por exemplo, árvore vermelha-preta ou árvore AVL). Essa árvore tem uma complexidade razoável para pesquisas e modificações (tipicamente O (log N) para ambos). Uma árvore, no entanto, tem dois (ou três) ponteiros por item de dados. Isso reduz a densidade de dados, portanto, você obtém um uso de cache relativamente ruim.

Se o seu dicionário é imutável, você pode usar uma matriz ordenada. Isso elimina os ponteiros, aumentando a densidade de dados, para que você obtenha (pelo menos um pouco) melhor uso do cache.

Em um caso típico, usar uma matriz ordenada permitirá que você dê um passo além disso. Uma árvore suporta pesquisa binária para encontrar o item de interesse. Se as suas chaves tiverem uma distribuição razoavelmente previsível (na maioria das vezes aproximadamente uniforme, mas outras distribuições também podem ser tratadas), você pode usar uma pesquisa de interpolação.

Por exemplo, considere procurar uma palavra em um dicionário (físico). Se você está procurando por "táxi", sabe que quer olhar para algum lugar perto do começo; Se você está procurando "sim", você sabe que quer olhar perto do fim.

Uma pesquisa de interpolação faz aproximadamente o mesmo - usa a chave para calcular uma aproximação decente da localização inicial para a pesquisa, em vez de sempre começar no meio (e o mesmo nas buscas subseqüentes).

Supondo que a distribuição de chaves é pelo menos um pouco previsível, isso normalmente melhorará sua complexidade de pesquisa para aproximadamente O (log log N), que é geralmente chamado de "pseudo-constante", porque é essencialmente constante para praticamente qualquer tamanho da coleção encontrada na realidade.

Por exemplo, vamos supor logaritmos comuns (base 10). Cada tamanho de 10 0 a 10 9 tem log de log N = 1. Cada tamanho de 10 10 a 10 99 tem log log N = 2.

Para qualquer propósito prático, N = 2 já ultrapassou o máximo que podemos esperar - para chegar a N = 3, precisaríamos de uma coleção de pelo menos 10 100 itens. Para colocar isso em perspectiva, existem cerca de 10 57 átomos no sistema solar, então se você pudesse armazenar cada item usando apenas um único átomo, você ainda precisaria dos átomos de aproximadamente 10 43 sistemas solares para armazenar uma coleção de 10 100 itens.

    
por 15.12.2017 / 21:44
fonte
0

By efficient I mean they either have better or comparable time and/or memory performance compared to their mutable versions.

A rigor, eu não acredito que isso possa existir, porque você sempre pode me mostrar uma estrutura de dados imutável e eu posso encontrar maneiras de tornar algo mais barato se ele puder ser feito mutável. Por exemplo, eu poderia eliminar o requisito de coleta de lixo ou contagem de referência se fosse mutável.

Existem estruturas de dados que são adequadas para se tornarem imutáveis, embora os custos sejam relativamente baixos. A maioria dos não-triviais é tipicamente pelo menos parcialmente contígua. Isso permite que os custos de contagem ref ou GC sejam banalizados se os nós forem desenrolados e armazenar vários elementos cada, não um elemento por nó.

Também há um ato de equilíbrio entre copiar mais ponteiros versus copiar menos elementos não exclusivos porque qualquer estrutura de dados pode ser imutável se você copiar toda a coisa toda vez que quiser mudar alguma coisa, mas isso pode ser explosivo em requisitos de memória e processamento. Por outro lado, se você faz referência superficial a cada elemento individual, isso pode ser explosivo na memória e nos requisitos de processamento com todos os ponteiros extras, toda a indireta extra e possível fragmentação de memória, o custo de contagem ou GC a ser pago para cada elemento, etc.

Muitas vezes, acho que as estruturas de dados imutáveis mais eficientes para conjuntos e dicionários serão parcialmente contíguas, como uma tabela hash usando endereçamento aberto, mas em vez de usar uma matriz gigante para toda a tabela, ela usa blocos desenrolados, digamos 64 chaves cada. Outro exemplo seria uma árvore n-ária armazenando muitas chaves em um nó.

É claro que uma tabela de hash usando encadeamento separado é realmente simples de se tornar imutável, já que criar listas LIFO unidas de forma única requer apenas o armazenamento de um ponteiro de cabeçalho diferente por lista imutável. No entanto, é simples, mas não muito barato, já que isso implica, novamente, contagem de referência ou GC pago em um nível por elemento.

Também é provável que você precise de algo como um "construtor" ou "transitório" para expressar o que deseja fazer com ele, já que não quer pagar o custo de gerar uma nova instância imutável a cada vez você acabou de inserir ou remover uma chave.

A concrete example is Guava, where I have seen memory savings when used with sets that don't need to be modified.

Aqui, talvez não seja apenas sobre imutabilidade, mas apenas uma estrutura de dados capaz de supor que os elementos serão simplesmente inseridos e conhecidos antecipadamente, sem precisar lidar com a remoção dinâmica e a inserção de elementos após sua construção. .

Nesse caso, por exemplo, você pode usar um alocador de memória sequencial como uma otimização, porque não precisa manipular a memória para elementos individuais, pois os elementos nunca serão removidos individualmente da estrutura de dados. Tudo o que você precisa fazer é eliminar toda a memória de todos os elementos quando a estrutura de dados é destruída.

Além disso, se todos os elementos forem conhecidos antecipadamente, você poderá evitar a necessidade de fazer realocações para expandir o tamanho da estrutura. Você pode deixá-lo com tamanho perfeito desde o início, pois conhece todos os elementos que serão inseridos com antecedência, de modo que não é necessário reservar memória adicional para futuras inserções.

As estruturas de dados que só precisam atender a esses tipos de requisitos "estáticos" e não "dinâmicos" também fornecem muito espaço para o pós-processamento depois que são construídos. Uma árvore binária pode ser pós-processada para realocar seus nós em um padrão de acesso amigável ao cache, por exemplo. Você pode arcar com isso com um tipo de estrutura de dados estático que não lida com inserções e remoções dinâmicas, pois há uma fase de criação clara que deixa espaço para o pós-processamento, após o qual você não precisa mais lidar com alterações na estrutura de dados.

Ex: Método "Limpar" mutável

Qualquer estrutura de dados que tenha menos requisitos funcionais para lidar geralmente terá mais espaço para otimizar. Mas aqui não são estruturas de dados imutáveis, mas sim estruturas de dados que podem ser construídas com antecedência e não precisam lidar com inserções e remoções dinâmicas. Tais estruturas de dados ainda poderiam ser mutáveis e permanecer tão baratas. Por exemplo, essa estrutura de dados ainda pode fornecer um método clear mutável para limpar todo o conteúdo do conjunto / dicionário, e fornecer esse método mutável não exigiria a perda dessas otimizações potenciais descritas acima. Então, não há nenhum caso, até onde eu vejo, onde a imutabilidade torna qualquer coisa mais barata, já que a imutabilidade impõe mais requisitos funcionais em uma estrutura de dados, por assim dizer, não menos.

    
por 16.12.2017 / 09:33
fonte