Como contar no pior dos casos no tempo linear?

8

Essa pergunta e essa pergunta me fizeram pensar um pouco. Para classificar uma matriz de comprimenton com kelementos únicos em , precisamos ser capazes de armazenar contagens de valores na matriz. Existem algumas sugestões, mas estou procurando uma maneira de fazer isso no pior dos casos, no tempo linear. Mais especificamente:O(n+kregistrok)

Dada uma lista dos elementos com elementos distintos, determinar uma lista de tuplos de todos os elementos exclusivos, tal que é a contagem de elemento em .UMAnkvocê={(xEu,cEu)}kxEuUMAcEuxEuUMA

Aqui estão algumas idéias (com falha) que tive e foram sugeridas:

  1. Árvore de Pesquisa Binária Balanceada - Com isso, será necessário para inserir na árvore e aumentar os valores. Após as inserções, poderíamos fazer uma travessia de árvore em . Assim, o tempo total sai para que é muito lento.O(registrok)O(k)O(nregistrok)
  2. Hash Map - Com isso, podemos obter inserções esperadas e, portanto, tempo esperado . No entanto, este ainda não é pior caso.O(1) O(n) O(n)
  3. Espaço vazio Mapeamento - Encontrar o elemento mínimo e máximo em . Aloque (mas não inicialize) memória suficiente para cobrir esse intervalo. Use essa memória basicamente como um mapa de hash e inclua um hash aleatório para que não tentemos acessar a memória corrompida. Essa estratégia apresenta problemas. (1) É probabilístico com muito, muito, muito baixa probabilidade de falhar, mas ainda não é garantido. Usar memória como essa nos limita a restrições de ponto flutuante ou inteiro.UMA
  4. Matrizes associativas - Existem muitas outras matrizes associativas que podem ser usadas, semelhantes aos mapas de hash e BSTs, mas não estou encontrando nenhuma que corresponda a essas restrições.

Talvez esteja faltando algum método óbvio, mas também acho que poderia não ser possível. Quais são seus pensamentos?

ryan
fonte
3
Isso não pode ser feito no modelo de comparação, já que o problema da distinção entre elementos tem um limite inferior deΩ(nlogn)complexidade da árvore de decisão.
John L.
@ Apass.Jack, oh certo, está correto. Uma redução trivial que não considerei. Se você escrever isso como uma resposta rápida do Blurb, eu aceito.
ryan
Por que o HashMap não tem garantia de O (n) amortizado ?
Javadba
1
@javadba Por exemplo, suponha que todos os elementos sejam hash com o mesmo valor.
John L.
Ah ok, então se é um hash imperfeito.
Javadba

Respostas:

6

Esta é uma boa pergunta.

No modelo de comparação ou, o que é mais geral, no modelo algébrico de árvore de decisão, o problema da distinção de elementos tem um limite inferior de Θ(nregistron)complexidade do tempo, na pior das hipóteses, como dito neste artigo da Wikipedia . Portanto, não há algoritmo para contar elementos distintos em tempo linear no pior dos casos, mesmo sem contar as duplicidades.

No entanto, não está claro se isso pode ser feito em outro modelo computacional. Parece improvável em qualquer modelo computacional determinístico razoável.

John L.
fonte
Isso é realmente uma instância do problema de distinção de elementos? Apenas gerar as tuplas não requer a verificação de distinção. Não discordo, apenas curioso.
Mascrej
2
O que estou dizendo é que, se você pode produzir essa tupla de elementos distintos, também pode resolver o problema da distinção de elementos, verificando se o tamanho da tupla é n.
31419 John L.
Boa decisão. Graças
mascoj
1

Existem algoritmos aleatórios cujo tempo de execução esperado é O(n); ou onde a probabilidade de o tempo de execução demorar mais do quecn é exponencialmente pequeno em c.

Em particular, escolha aleatoriamente uma função de hash 2-universal e use-a para misturar todos os elementos da matriz. Isso atinge os tempos de execução indicados, se você escolher o comprimento da saída do hash 2-universal adequadamente.

Como outro exemplo, você pode criar um algoritmo aleatório cujo pior tempo de execução é O(n) (sempre é executado em tempo linear, não importa o quê) e tem uma probabilidade de erro de no máximo 1/2100. (Como? Execute o algoritmo acima e encerre-o se executar mais do quecn passos para alguns escolhidos adequadamente c.) Na prática, isso é bom o suficiente, pois a probabilidade de o seu computador dar a resposta errada devido a um raio cósmico já é muito maior do que 1/2100.

DW
fonte
1

Sua abordagem 3 pode ser protegida usando uma solução para o exercício 2.12 de Aho, Hopcroft e Ullman (1974) The Design and Analysis of Computer Algorithms, como descrito, por exemplo, em Usando memória não inicializada para diversão e lucro .

Basicamente, além da sua matriz de N elementos com as contagens, você tem duas matrizes de N elementos e uma contagem auxiliar para criar um conjunto esparso indicando quais das contagens são válidas.

No pseudocódigo do tipo C:

uint* a = malloc(n);
uint* b = malloc(n);
uint* c = malloc(n);
uint len = 0;

get_count(uint x) {
    uint idx = a[x];
    return idx >= 0 && idx < len && b[idx] == x ? c[idx] : 0;
}

increment_count(uint x) {
    uint idx = a[x];
    if (idx < 0 || idx >= len || b[idx] != x) {
        idx = len;
        len++;
        a[x] = idx;
        b[idx] = x;
        c[idx] = 0;
    }
    c[idx]++;
}

A implementação prática do conjunto esparso é discutida nesta resposta do StackOverflow .

Peter Taylor
fonte
O PS cpode ser indexado em xou idx, mas eu usei idxpara uma melhor localidade do cache.
Peter Taylor
Gosto da resposta, mas confuso sobre o que torna isso seguro. Embora, totalmente improvável, você não possa acessar uma célula de memória, que por algum milagre possui uma entrada "válida", mesmo que nunca tenha sido colocada lá. Se você acabou de azar com malloc?
ryan
1
Esta solução funciona apenas se você tiver uma memória grande o suficiente: se todos os elementos da matriz estiverem no intervalo 1 ..você, então você precisa de pelo menos memória de tamanho você. Na prática, isso é muito limitante. A maneira como criamos um grande espaço de endereço virtual na prática é usar tabelas de páginas, que são uma estrutura de dados baseada em árvore; o hardware segue invisivelmente as tabelas de páginas para nós. Como resultado, embora pensemos no acesso à memória comoO(1)tempo, se você estiver trabalhando em um grande espaço de endereço de memória, cada acesso à memória realmente leva tempo logarítmico (para percorrer a estrutura da árvore da tabela de páginas).
DW
@ryan, consulte research.swtch.com/sparse para saber o que a torna segura. É definitivamente um truque muito inteligente.
DW
@DW, 3você+1, mas se vocêé muito grande, você pode fazer isso em vários níveis, usando uma matriz de {a,b,c,len}estruturas para, em cvez de uma matriz de contagens. Por exemplo, se você usar o radix 512 para que cada uma das matrizes caiba em uma página (com ponteiros de 8 bytes), poderá ir atévocê=5123=134217728 usando no máximo (3×512+1)(1+2k) memória onde ké o número de elementos distintos vistos.
22619 Peter Peter Taylor