Localizando o elemento que mais ocorre em um arquivo muito grande

Ouvi muito essa pergunta da entrevista e esperava obter algumas opiniões sobre quais seriam as boas respostas: você tem um arquivo grande com mais de 10 GB e deseja descobrir qual elemento ocorre mais, qual é uma boa maneira para fazer isso?

Iterar e acompanhar um mapa provavelmente não é uma boa ideia, pois você usa muita memória, e acompanhar as entradas não é a melhor opção, pois quando essa pergunta é feita, o arquivo geralmente já existe.

Outros pensamentos que eu incluí incluem dividir o arquivo para ser iterado e processado por vários threads e depois ter esses resultados combinados, mas o problema de memória para os mapas ainda está lá.

algorithms arrays Pat
fonte

Quais são os elementos do arquivo? Eles são cordas? Se você pegar caracteres para elementos, o mapa não terá problemas de memória. Se os elementos são palavras, acho que não seria um problema. Se você tem todas as substrings possíveis, então você pode ter problemas ...

Nejc

Se a condição fosse "um elemento que aparece mais da metade do total de elementos", haveria uma solução linear.

Stdle

Eu acredito que os elementos são geralmente cordas. Mas não vejo como o mapa não é um problema. Na pior das hipóteses, onde cada elemento é único, você não apenas duplicou seus requisitos de memória?

Pat

Se o algoritmo candidato a maioria de Boyer-Moore for aplicável, ele será executado em tempo linear e estará em vigor.

Juho

Respostas:

Quando você tem um arquivo muito grande e muitos elementos, mas o elemento mais comum é muito comum - ocorre fração do tempo - você pode encontrá-lo em tempo linear com palavras espaço (o A constante na notação é muito pequena, basicamente 2 se você não contar o armazenamento para itens auxiliares como hash). Além disso, isso funciona muito bem com armazenamento externo, pois o arquivo é processado em sequência, um elemento de cada vez, e o algoritmo nunca "olha para trás". Uma maneira de fazer isso é através de um algoritmo clássico de Misra e Gries, veja estas notas de aula $> 1/k$ $O(k)$ $O()$ . O problema agora é conhecido como problema dos rebatedores pesados (os elementos frequentes são os rebatedores pesados).

A suposição de que o elemento mais frequente aparece fração do tempo para um número pequeno pode parecer forte, mas é de certa forma necessário! Ou seja, se você tiver acesso seqüencial ao seu arquivo (e caso o arquivo seja enorme, o acesso aleatório será muito caro), qualquer algoritmo que sempre encontre o elemento mais frequente em um número constante de passes utilizará espaço linear no número de elementos . Portanto, se você não assume algo sobre a entrada, não pode vencer uma tabela de hash. A suposição de que o elemento mais frequente é muito frequente talvez seja a maneira mais natural de contornar os resultados negativos. $> 1/k$ $k$

Aqui está um esboço para , ou seja, quando existe um único elemento que ocorre mais da metade do tempo. Esse caso especial é conhecido como algoritmo de votação majoritária e é devido a Boyer e Moore. Manteremos um único elemento e uma única contagem. Inicialize a contagem para 1 e armazene o primeiro elemento do arquivo. Em seguida, processe o arquivo em sequência: $k = 2$

se o elemento atual do arquivo for o mesmo que o elemento armazenado, aumente a contagem em um
se o elemento atual do arquivo for diferente do elemento armazenado, diminua a contagem em um
se a contagem atualizada for 0, "expulse" o elemento armazenado e armazene o elemento atual do arquivo; aumentar a contagem para 1
prossiga para o próximo elemento do arquivo

Um pouco de reflexão sobre este procedimento o convencerá de que, se existir um elemento "majoritário", ou seja, um que ocorra mais da metade do tempo, esse elemento será o elemento armazenado após o processamento do arquivo inteiro.

Para geral , você mantém $k$ $k-1$ elementos e contagens e inicializa os elementos nos primeiros elementos distintos do arquivo e as contagens no número de vezes que cada um desses elementos aparece antes de ver ésimo elemento distinto. Em seguida, você executa essencialmente o mesmo procedimento: a contagem de um elemento é aumentada cada vez que é encontrada, todas as contagens de elementos são diminuídas se um elemento que não é armazenado for encontrado e, quando alguma contagem for zero, esse elemento será expulso em favor do elemento. elemento atual do arquivo. Este é o algoritmo de Misra-Gries. $k-1$ $k$ $k$

Obviamente, você pode usar uma tabela de hash para indexar o $k-1$ $1/k$ $O(k)$

Uma coisa final: depois de encontrar candidato "hitters pesados" (ou seja, elementos frequentes), você pode fazer mais uma passagem sobre o arquivo para contar a frequência de cada elemento. Dessa forma, você pode classificar os elementos entre si e verificar se todos eles ocorrem mais de $k$ $1/k$ $k-1$

Sasho Nikolov
fonte

Você não pode usar os algoritmos Boyer-Moore ou Misra-Gries-Demaine. O problema, conforme indicado, é diferente: você não está procurando por um elemento majoritário, mas por um elemento cujas ocorrências sejam> = das ocorrências de todos os elementos. Aqui está um contra-exemplo simples. Seja n o número total de elementos, de modo que n = 2k + 1 . Deixe os primeiros k elementos serem 0, os próximos k elementos sejam 1 e o último elemento seja 2. O algoritmo de Boyer-Moore relatará o último elemento, 2, como candidato potencial à maioria. Mas, para esse exemplo em particular, a saída deve ser 0 ou 1. #

Massimo Cafaro

O (1)

$O(1)$

Ω (n)

$\Omega(n)$

Acabei de salientar que, se você fizer uma suposição errada, poderá obter resultados errados. O que é melhor, uma pequena área ocupada por memória e um resultado potencialmente incorreto ou o resultado correto, mesmo que isso custe um pouco mais de memória? Se eu tivesse que escolher um resultado potencialmente incorreto, eu usaria um algoritmo aleatório, em vez de Boyer-Moore assumir que algo que eu não sei é realmente verdade.

Massimo Cafaro

@MassimoCafaro que não é uma troca que você precisa fazer. Como apontei, uma única passagem sobre o arquivo verifica facilmente se a suposição é satisfeita!

Sasho Nikolov 12/12/12

@MassimoCafaro e esta é apenas a solução trivial! a suposição pode ser verificada com alta probabilidade com um esboço CM sem passes adicionais.

Sasho Nikolov 12/12/12

A resposta óbvia é, obviamente, manter um mapa de hash e armazenar um contador da ocorrência de elementos à medida que você percorre o arquivo, como Nejc já sugeriu. Essa é (em termos de complexidade de tempo) a solução ideal.

$\Theta(n\log{n}).$

Jernej
fonte

Você poderia elaborar mais sobre a abordagem de codificação de Huffman? Eu escrevi um codificador Huffman antes, mas já faz um tempo, como exatamente você o usaria neste caso?

Pat

@ Pat Nevermind essa parte, era muito cedo pela manhã e de alguma forma eu pensei que faria sentido compactar a entrada.

Jernej

Se o elemento mais comum for mais comum do que o próximo por uma margem substancial e o número de elementos diferentes for pequeno comparado ao tamanho do arquivo, você poderá amostrar aleatoriamente alguns elementos e retornar o elemento mais comum em sua amostra.

adrianN
fonte

Além disso, se houver um pequeno número de elementos ocorrendo muitas vezes, você poderá encontrá-los por amostragem e contar apenas esses elementos exatamente.

Max