No momento, estou me preparando para uma entrevista e isso me lembrou de uma pergunta que me fizeram uma vez em uma entrevista anterior que foi mais ou menos assim:

"Você foi solicitado a desenvolver um software para exibir continuamente os 10 principais termos de pesquisa no Google. Você tem acesso a um feed que fornece um fluxo infinito em tempo real de termos de pesquisa que estão sendo pesquisados ​​no Google. Descreva quais algoritmos e estruturas de dados você usaria para implementar isso. Você deve projetar duas variações:

(i) Exibir os 10 principais termos de pesquisa de todos os tempos (ou seja, desde que você começou a ler o feed).

(ii) Exibir apenas os 10 principais termos de pesquisa do mês anterior, atualizados a cada hora.

Você pode usar uma aproximação para obter a lista dos 10 primeiros, mas deve justificar suas escolhas. "
Eu fui um fracasso nessa entrevista e ainda não tenho ideia de como implementar isso.

A primeira parte pede os 10 itens mais frequentes em uma subseqüência continuamente crescente de uma lista infinita. Pesquisei algoritmos de seleção, mas não consegui encontrar nenhuma versão online para resolver esse problema.

A segunda parte usa uma lista finita, mas devido à grande quantidade de dados sendo processados, você não pode realmente armazenar o mês inteiro de termos de pesquisa na memória e calcular um histograma a cada hora.

O problema torna-se mais difícil pelo fato de que a lista dos 10 primeiros está sendo continuamente atualizada, então de alguma forma você precisa calcular os 10 principais em uma janela deslizante.

Alguma ideia?

Bem, parece uma quantidade enorme de dados, com um custo talvez proibitivo para armazenar todas as frequências. Quando a quantidade de dados é tão grande que não podemos esperar armazenar tudo, entramos no domínio dos algoritmos de fluxo de dados .

Livro útil nesta área: Muthukrishnan - "Data Streams: Algorithms and Applications"

Referência intimamente relacionada ao problema em questão que escolhi acima: Manku, Motwani - "Approximate Frequency Counts over Data Streams" [pdf]

A propósito, Motwani, de Stanford, (editar) foi um autor do livro muito importante "Randomized Algorithms" . O capítulo 11 deste livro trata desse problema . Edit: Desculpe, má referência, esse capítulo específico é sobre um problema diferente. Depois de verificar, eu recomendo a seção 5.1.2 do livro de Muthukrishnan , disponível online.

Heh, boa pergunta da entrevista.

Visão geral da estimativa de frequência

Existem alguns algoritmos bem conhecidos que podem fornecer estimativas de frequência para tal fluxo usando uma quantidade fixa de armazenamento. One is Frequent, de Misra e Gries (1982). De uma lista de n itens, ele encontra todos os itens que ocorrem mais de n / k vezes, usando k - 1 contadores. Esta é uma generalização do algoritmo Majoritário de Boyer e Moore (Fischer-Salzberg, 1982), onde k é 2. LossyCounting de Manku e Motwani (2002) e SpaceSaving de Metwally (2005) de têm requisitos de espaço semelhantes, mas podem fornecer estimativas mais precisas sob certos condições.

O importante a lembrar é que esses algoritmos podem fornecer apenas estimativas de frequência. Especificamente, a estimativa de Misra-Gries pode subestimar a frequência real em (n / k) itens .

Suponha que você tenha um algoritmo que possa identificar positivamente um item apenas se ele ocorrer mais de 50% das vezes. Alimente esse algoritmo com um fluxo de N itens distintos e, em seguida, adicione outras N - 1 cópias de um item, x , para um total de 2N - 1 itens. Se o algoritmo informa que x excede 50% do total, ele deve estar no primeiro fluxo; se não, x não estava no fluxo inicial. Para que o algoritmo faça essa determinação, ele deve armazenar o fluxo inicial (ou algum resumo proporcional ao seu comprimento)! Assim, podemos provar a nós mesmos que o espaço requerido por tal algoritmo "exato" seria Ω ( N ).

Em vez disso, esses algoritmos de frequência descritos aqui fornecem uma estimativa, identificando qualquer item que exceda o limite, junto com alguns itens que caem abaixo dele por uma certa margem. Por exemplo, o algoritmo Majority , usando um único contador, sempre fornecerá um resultado; se qualquer item exceder 50% do fluxo, ele será encontrado. Mas também pode fornecer um item que ocorre apenas uma vez. Você não saberia sem fazer uma segunda passagem pelos dados (usando, novamente, um único contador, mas procurando apenas por aquele item).

O Algoritmo Freqüente

Aqui está uma descrição simples do algoritmo Frequent de Misra-Gries . Demaine (2002) e outros otimizaram o algoritmo, mas isso fornece a essência.

Especifique a fração limite, 1 / k ; qualquer item que ocorra mais de n / k vezes será encontrado. Crie um mapa vazio (como uma árvore vermelha e preta); as chaves serão termos de pesquisa e os valores serão um contador para esse termo.

1. Observe cada item do fluxo.
2. Se o termo existir no mapa, incremente o contador associado.
3. Caso contrário, se o mapa for menor que k - 1 entradas, adicione o termo ao mapa com um contador de um.
4. No entanto, se o mapa já tiver k - 1 entradas, diminua o contador em cada entrada. Se algum contador chegar a zero durante este processo, remova-o do mapa.

Observe que você pode processar uma quantidade infinita de dados com uma quantidade fixa de armazenamento (apenas o mapa de tamanho fixo). A quantidade de armazenamento necessária depende apenas do limite de interesse e o tamanho do fluxo não importa.

Contando pesquisas

Nesse contexto, talvez você armazene uma hora de pesquisas e execute esse processo nos dados dessa hora. Se você puder dar uma segunda passada no registro de pesquisa desta hora, poderá obter uma contagem exata das ocorrências dos principais "candidatos" identificados na primeira passada. Ou, talvez não haja problema em fazer uma única aprovação e relatar todos os candidatos, sabendo que qualquer item que deveria estar lá está incluído, e quaisquer extras são apenas ruídos que irão desaparecer na próxima hora.

Quaisquer candidatos que realmente excedam o limite de interesse são armazenados como um resumo. Guarde esses resumos por um mês, jogando fora os mais antigos a cada hora, e você terá uma boa aproximação dos termos de pesquisa mais comuns.

Este é um dos projetos de pesquisa que estou realizando atualmente. O requisito é quase exatamente igual ao seu, e desenvolvemos algoritmos interessantes para resolver o problema.

A entrada

A entrada é um fluxo infinito de palavras ou frases em inglês (nós as referimos como tokens).

A saída

1. Saída dos principais N tokens que vimos até agora (de todos os tokens que vimos!)
2. Produza os N tokens principais em uma janela histórica, digamos, último dia ou semana passada.

Uma aplicação desta pesquisa é encontrar o tema quente ou tendências de assunto no Twitter ou Facebook. Temos um rastreador que rastreia o site, que gera um fluxo de palavras, que vai alimentar o sistema. O sistema, então, produzirá as palavras ou frases de alta frequência de maneira geral ou histórica. Imagine nas últimas semanas a frase "Copa do Mundo" apareceria muitas vezes no Twitter. O mesmo acontece com "Paul, o polvo". :)

String em inteiros

O sistema possui um ID inteiro para cada palavra. Embora haja palavras quase infinitas possíveis na Internet, mas depois de acumular um grande conjunto de palavras, a possibilidade de encontrar novas palavras torna-se cada vez menor. Já encontramos 4 milhões de palavras diferentes e atribuímos um ID exclusivo para cada uma. Todo esse conjunto de dados pode ser carregado na memória como uma tabela hash, consumindo aproximadamente 300 MB de memória. (Implementamos nossa própria tabela de hash. A implementação do Java exige uma grande sobrecarga de memória)

Cada frase pode então ser identificada como um array de inteiros.

Isso é importante porque a classificação e as comparações em inteiros são muito mais rápidas do que em strings.

Dados de arquivo

O sistema mantém os dados do arquivo para cada token. Basicamente, são pares de (Token, Frequency). No entanto, a tabela que armazena os dados seria tão grande que teríamos que particionar a tabela fisicamente. Uma vez que o esquema de partição é baseado em ngrams do token. Se o token for uma única palavra, será 1 grama. Se o token for uma frase de duas palavras, será de 2 gramas. E isso continua. Aproximadamente em 4gram, temos 1 bilhão de registros, com a tabela dimensionada em torno de 60 GB.

Processando fluxos de entrada

O sistema absorverá as frases recebidas até que a memória seja totalmente utilizada (Sim, precisamos de um MemoryManager). Depois de pegar N frases e armazená-las na memória, o sistema faz uma pausa e começa a tokenizar cada frase em palavras e frases. Cada token (palavra ou frase) é contado.

Para tokens altamente frequentes, eles são sempre mantidos na memória. Para tokens menos frequentes, eles são classificados com base em IDs (lembre-se de que traduzimos a String em uma matriz de inteiros) e serializados em um arquivo de disco.

(No entanto, para o seu problema, uma vez que você está contando apenas palavras, você pode colocar todos os mapas de frequência de palavras apenas na memória. Uma estrutura de dados cuidadosamente projetada consumiria apenas 300 MB de memória para 4 milhões de palavras diferentes. Alguma dica: use caracteres ASCII para representam Strings), e isso é muito aceitável.

Enquanto isso, haverá outro processo que será ativado assim que encontrar qualquer arquivo de disco gerado pelo sistema e, em seguida, começará a mesclá-lo. Uma vez que o arquivo do disco é classificado, a fusão levaria um processo semelhante, como a classificação por fusão. Alguns projetos também precisam ser cuidados aqui, já que queremos evitar muitas buscas aleatórias de disco. A ideia é evitar ler (processo de mesclagem) / gravação (saída do sistema) ao mesmo tempo e permitir que o processo de mesclagem leia de um disco enquanto grava em um disco diferente. Isso é semelhante a implementar um bloqueio.

Fim do dia

No final do dia, o sistema terá muitos tokens frequentes com frequência armazenados na memória, e muitos outros tokens menos frequentes armazenados em vários arquivos do disco (e cada arquivo é classificado).

O sistema descarrega o mapa da memória em um arquivo de disco (classifique-o). Agora, o problema é mesclar um conjunto de arquivos de disco classificados. Usando um processo semelhante, obteríamos um arquivo de disco classificado no final.

Em seguida, a tarefa final é mesclar o arquivo de disco classificado no banco de dados de arquivo. Depende do tamanho do banco de dados do arquivo, o algoritmo funciona como abaixo se for grande o suficiente:

   for each record in sorted disk file
        update archive database by increasing frequency
        if rowcount == 0 then put the record into a list
   end for

   for each record in the list of having rowcount == 0
        insert into archive database
   end for

A intuição é que, depois de algum tempo, o número de inserções ficará cada vez menor. Mais e mais operação será apenas na atualização. E esta atualização não será penalizada por índice.

Espero que toda esta explicação ajude. :)

Você pode usar uma tabela hash combinada com uma árvore de pesquisa binária . Implemente um <search term, count>dicionário que informa quantas vezes cada termo de pesquisa foi pesquisado.

Obviamente, iterar toda a tabela de hash a cada hora para obter os 10 primeiros é muito ruim. Mas é do Google que estamos falando, então você pode assumir que os dez primeiros terão, digamos, mais de 10.000 acessos (provavelmente é um número muito maior). Portanto, sempre que a contagem de um termo de pesquisa ultrapassar 10.000, insira-o no BST. Então, a cada hora, você só precisa obter os primeiros 10 do BST, que deve conter relativamente poucas entradas.

Isso resolve o problema dos 10 melhores de todos os tempos.

A parte realmente complicada é lidar com um termo tomando o lugar de outro no relatório mensal (por exemplo, "estouro de pilha" pode ter 50.000 ocorrências nos últimos dois meses, mas apenas 10.000 no mês anterior, enquanto "amazon" pode ter 40 000 nos últimos dois meses, mas 30 000 no mês anterior. Você deseja que "amazon" venha antes de "estouro de pilha" em seu relatório mensal). Para fazer isso, eu armazenaria, para todos os principais termos de pesquisa (acima de 10.000 pesquisas de todos os tempos), uma lista de 30 dias que informa quantas vezes esse termo foi pesquisado em cada dia. A lista funcionaria como uma fila FIFO: você remove o primeiro dia e insere uma nova a cada dia (ou a cada hora, mas pode ser necessário armazenar mais informações, o que significa mais memória / espaço. Se a memória não for um problema, faça , caso contrário, vá para aquela "aproximação"

Parece um bom começo. Você pode então se preocupar em podar os termos que têm> 10.000 ocorrências, mas não tiveram muitos por um longo tempo e coisas assim.

caso i)

Mantenha uma tabela de hash para todos os termos de pesquisa, bem como uma lista dos dez primeiros classificados separada da tabela de hash. Sempre que ocorrer uma pesquisa, incremente o item apropriado na tabela de hash e verifique se esse item deve ser trocado pelo décimo item na lista dos dez primeiros.

O (1) pesquisa para a lista dos dez primeiros e máximo O (log (n)) inserção na tabela de hash (assumindo colisões gerenciadas por uma árvore binária de auto-equilíbrio).

caso ii) Em vez de manter uma tabela de hash enorme e uma pequena lista, mantemos uma tabela de hash e uma lista ordenada de todos os itens. Sempre que uma pesquisa é feita, esse termo é incrementado na tabela de hash e, na lista classificada, o termo pode ser verificado para ver se deve ser trocado pelo termo depois dele. Uma árvore binária de autobalanceamento pode funcionar bem para isso, pois também precisamos ser capazes de consultá-la rapidamente (mais sobre isso mais tarde).

Além disso, também mantemos uma lista de 'horas' na forma de uma lista FIFO (fila). Cada elemento de 'hora' conteria uma lista de todas as pesquisas feitas naquela hora específica. Portanto, por exemplo, nossa lista de horas pode ser assim:

Time: 0 hours
      -Search Terms:
          -free stuff: 56
          -funny pics: 321
          -stackoverflow: 1234
Time: 1 hour
      -Search Terms:
          -ebay: 12
          -funny pics: 1
          -stackoverflow: 522
          -BP sucks: 92

Então, a cada hora: se a lista tiver pelo menos 720 horas de duração (esse é o número de horas em 30 dias), olhe para o primeiro elemento da lista e, para cada termo de pesquisa, diminua esse elemento na tabela de hash pela quantidade apropriada . Depois, exclua o primeiro elemento de hora da lista.

Digamos que estamos na hora 721 e estamos prontos para ver a primeira hora em nossa lista (acima). Diminuiríamos as coisas grátis em 56 na tabela de hash, as fotos engraçadas em 321, etc., e então removeríamos a hora 0 da lista completamente, já que nunca precisaremos olhar para ela novamente.

O motivo pelo qual mantemos uma lista ordenada de todos os termos que permite consultas rápidas é porque a cada hora depois que examinamos os termos de pesquisa de 720 horas atrás, precisamos garantir que a lista dos dez primeiros permaneça ordenada. Assim, à medida que diminuímos 'coisas grátis' em 56 na tabela de hash, por exemplo, veríamos onde agora elas pertencem na lista. Por ser uma árvore binária de auto-equilíbrio, tudo isso pode ser realizado muito bem em tempo O (log (n)).

Editar: Sacrificando precisão pelo espaço ...

Pode ser útil também implementar uma grande lista no primeiro, como no segundo. Então, poderíamos aplicar a seguinte otimização de espaço em ambos os casos: Executar um cron job para remover todos, exceto os x primeiros itens da lista. Isso manteria o requisito de espaço baixo (e como resultado tornaria as consultas na lista mais rápidas). Claro, isso resultaria em um resultado aproximado, mas isso é permitido. x pode ser calculado antes de implantar o aplicativo com base na memória disponível e ajustado dinamicamente se houver mais memória disponível.

Pensamento duro ...

Para os 10 melhores de todos os tempos

• Usando uma coleção de hash onde uma contagem para cada termo é armazenada (higienizar termos, etc.)
• Uma matriz classificada que contém os 10 primeiros em andamento, um termo / contagem é adicionado a esta matriz sempre que a contagem de um termo torna-se igual ou maior que a menor contagem na matriz

Para as 10 principais atualizações mensais de hora em hora:

• Usando uma matriz indexada no número de horas decorridas desde o início do módulo 744 (o número de horas durante um mês), as entradas da matriz consistem em uma coleção de hash onde uma contagem para cada termo encontrado durante esse intervalo de hora é armazenada. Uma entrada é redefinida sempre que o contador do intervalo de horas muda
• as estatísticas no array indexado no intervalo de horas precisam ser coletadas sempre que o contador do intervalo de horas atual muda (uma vez por hora no máximo), copiando e nivelando o conteúdo deste array indexado em intervalos de horas

Errr ... faz sentido? Eu não pensei nisso como faria na vida real

Ah sim, esqueci de mencionar, a hora de "copiar / nivelar" necessária para as estatísticas mensais pode realmente reutilizar o mesmo código usado para os 10 primeiros de todos os tempos, um bom efeito colateral.

Solução exata

Primeiro, uma solução que garante resultados corretos, mas requer muita memória (um grande mapa).

Variante "de todos os tempos"

Mantenha um mapa hash com consultas como chaves e suas contagens como valores. Além disso, mantenha uma lista das 10 consultas mais frequentes até o momento e a contagem da décima contagem mais frequente (um limite).

Atualize constantemente o mapa à medida que o fluxo de consultas é lido. Sempre que uma contagem exceder o limite atual, faça o seguinte: remova a 10ª consulta da lista "10 principais", substitua-a pela consulta que você acabou de atualizar e atualize o limite também.

Variante do "mês anterior"

Mantenha a mesma lista "Top 10" e atualize-a da mesma forma que acima. Além disso, mantenha um mapa semelhante, mas desta vez armazene vetores de 30 * 24 = 720 contagens (um para cada hora) como valores. A cada hora, faça o seguinte para cada tecla: remova o contador mais antigo do vetor e adicione um novo (inicializado em 0) no final. Remova a chave do mapa se o vetor for zero. Além disso, a cada hora, você deve calcular a lista "Top 10" do zero.

Nota: Sim, desta vez estamos armazenando 720 inteiros em vez de um, mas há muito menos chaves (a variante de todos os tempos tem uma cauda muito longa).

Aproximações

Essas aproximações não garantem a solução correta, mas consomem menos memória.

1. Processe cada enésima consulta, ignorando o resto.
2. (Para a variante de todos os tempos apenas) Mantenha no máximo M pares de valores-chave no mapa (M deve ser o maior que você puder pagar). É uma espécie de cache LRU: toda vez que você ler uma consulta que não esteja no mapa, remova a consulta menos usada recentemente com contagem 1 e substitua-a pela consulta processada atualmente.

Os 10 principais termos de pesquisa do último mês

Usando a indexação / estrutura de dados com eficiência de memória, como tentativas compactadas (de entradas da Wikipédia em tentativas ), define aproximadamente alguma relação entre os requisitos de memória e n - número de termos.

Caso a memória necessária esteja disponível ( suposição 1 ), você pode manter a estatística mensal exata e agregá-la todos os meses na estatística de todos os tempos.

Há, também, uma suposição aqui que interpreta o 'último mês' como janela fixa. Mas mesmo que a janela mensal seja deslizante, o procedimento acima mostra o princípio (o deslizamento pode ser aproximado com janelas fixas de determinado tamanho).

Isso me lembra do banco de dados round-robin com a exceção de que algumas estatísticas são calculadas em 'todos os tempos' (no sentido de que nem todos os dados são retidos; rrd consolida períodos de tempo desconsiderando detalhes por média, somando ou escolhendo valores máx. / Mín., em determinada tarefa, o detalhe que se perde são as informações sobre itens de baixa frequência, que podem introduzir erros.

Premissa 1

Se não conseguirmos manter estatísticas perfeitas para o mês inteiro, devemos ser capazes de encontrar um determinado período P para o qual devemos ser capazes de manter estatísticas perfeitas. Por exemplo, supondo que temos estatísticas perfeitas em algum período de tempo P, que vai para o mês n vezes.
Estatísticas perfeitas definem a função f(search_term) -> search_term_occurance.

Se pudermos manter todas as ntabelas de estatísticas perfeitas na memória, as estatísticas mensais deslizantes podem ser calculadas assim:

• adicione estatísticas para o período mais recente
• remover estatísticas para o período mais antigo (por isso temos que manter ntabelas de estatísticas perfeitas)

No entanto, se mantivermos apenas os 10 primeiros no nível agregado (mensal), seremos capazes de descartar muitos dados das estatísticas completas do período fixo. Isso já fornece um procedimento de trabalho que fixou (assumindo o limite superior na tabela de estatísticas perfeitas para o período P) requisitos de memória.

O problema com o procedimento acima é que, se mantivermos as informações apenas nos 10 principais termos para uma janela deslizante (da mesma forma para todos os tempos), as estatísticas estarão corretas para os termos de pesquisa que atingem o pico em um período, mas podem não ver o estatísticas para termos de pesquisa que aparecem constantemente ao longo do tempo.

Isso pode ser compensado mantendo informações sobre mais de 10 termos principais, por exemplo, 100 termos principais, esperando que os 10 principais estejam corretos.

Acho que uma análise mais aprofundada poderia relacionar o número mínimo de ocorrências necessárias para que uma entrada se tornasse parte das estatísticas (que está relacionada ao erro máximo).

(Ao decidir quais entradas devem fazer parte das estatísticas, também se pode monitorar e rastrear as tendências; por exemplo, se uma extrapolação linear das ocorrências em cada período P para cada termo informa que o termo se tornará significativo em um ou dois meses, você já pode começar a rastreá-lo. Princípios semelhantes se aplicam à remoção do termo de pesquisa do pool rastreado.)

O pior caso para o acima é quando você tem muitos termos quase igualmente frequentes e eles mudam o tempo todo (por exemplo, se rastrear apenas 100 termos, então se os 150 principais termos ocorrerem com a mesma frequência, mas os 50 principais ocorrerem com mais frequência no primeiro mês e para que muitas vezes algum tempo depois, as estatísticas não sejam mantidas corretamente).

Também poderia haver outra abordagem que não é fixa no tamanho da memória (bem falando estritamente nenhuma das anteriores), que definiria uma significância mínima em termos de ocorrências / período (dia, mês, ano, de todos os tempos) para o qual manter o Estatísticas. Isso pode garantir o erro máximo em cada uma das estatísticas durante a agregação (consulte o round robin novamente).

Que tal uma adaptação do "algoritmo de substituição da página do relógio" (também conhecido como "segunda chance")? Posso imaginar que funcione muito bem se as solicitações de pesquisa forem distribuídas uniformemente (isso significa que a maioria dos termos pesquisados ​​aparecem regularmente em vez de 5 milhões de vezes consecutivas e nunca mais).

Aqui está uma representação visual do algoritmo:

Armazene a contagem de termos de pesquisa em uma tabela hash gigante, onde cada nova pesquisa faz com que um elemento específico seja incrementado em um. Acompanhe os 20 ou mais termos de pesquisa principais; quando o elemento em 11º lugar for incrementado, verifique se ele precisa trocar de posição com o nº 10 * (não é necessário manter os 10 primeiros classificados; tudo o que importa é fazer a distinção entre 10º e 11º).

* _{Verificações semelhantes precisam ser feitas para ver se um novo termo de pesquisa está em 11º lugar, então este algoritmo se estende a outros termos de pesquisa também - então estou simplificando um pouco.}

às vezes, a melhor resposta é "Não sei".

Vou dar uma facada mais profunda. Meu primeiro instinto seria alimentar os resultados em um Q. Um processo processaria continuamente os itens que chegam ao Q. O processo manteria um mapa de

termo -> contagem

cada vez que um item Q é processado, você simplesmente procura o termo de pesquisa e aumenta a contagem.

Ao mesmo tempo, manteria uma lista de referências às 10 principais entradas do mapa.

Para a entrada que foi implementada atualmente, veja se sua contagem é maior que a contagem da menor entrada entre os 10 primeiros (se ainda não estiver na lista). Se estiver, substitua o menor pela entrada.

Acho que funcionaria. Nenhuma operação consome muito tempo. Você teria que encontrar uma maneira de gerenciar o tamanho do mapa de contagem. mas isso deve ser bom o suficiente para uma resposta de entrevista.

Eles não estão esperando uma solução, que querem ver se você consegue pensar. Você não tem que escrever a solução naquele momento ....

Uma maneira é que, para cada pesquisa, você armazene esse termo de pesquisa e seu carimbo de data / hora. Dessa forma, encontrar os dez primeiros em qualquer período de tempo é simplesmente uma questão de comparar todos os termos de pesquisa dentro de um determinado período de tempo.

O algoritmo é simples, mas a desvantagem seria maior consumo de memória e tempo.

Que tal usar uma árvore Splay com 10 nós? Cada vez que você tentar acessar um valor (termo de pesquisa) que não está contido na árvore, jogue fora qualquer folha, insira o valor e acesse-o.

A ideia por trás disso é a mesma da minha outra resposta . Partindo do princípio de que os termos de pesquisa são acessados ​​de maneira uniforme / regular, essa solução deve funcionar muito bem.

editar

Pode-se também armazenar mais alguns termos de pesquisa na árvore (o mesmo vale para a solução que sugiro na minha outra resposta) para não excluir um nó que pode ser acessado novamente em breve. Quanto mais valores forem armazenados nele, melhores serão os resultados.

Não sei se entendi direito ou não. Minha solução é usar heap. Por causa dos 10 principais itens de pesquisa, eu construo um heap com tamanho 10. Em seguida, atualizo esse heap com uma nova pesquisa. Se a frequência de uma nova pesquisa for maior do que a parte superior do heap (Heap máx.), Atualize-a. Abandone aquele com menor frequência.

Mas, como calcular a frequência da pesquisa específica, será contado com outra coisa. Talvez, como todos afirmaram, o algoritmo de fluxo de dados ....

Use o cm-sketch para armazenar a contagem de todas as pesquisas desde o início, mantenha um min-heap de tamanho 10 com ele para o top 10. Para o resultado mensal, mantenha 30 cm-sketch / hash-table e min-heap com ele, cada um inicia contagem e atualização dos últimos 30, 29 .., 1 dia. Como um dia passa, limpe o último e use-o como dia 1. O mesmo para o resultado por hora, mantenha a tabela de hash 60 e o heap mínimo e comece a contar para os últimos 60, 59, ... 1 minuto. Conforme um minuto passa, elimine o último e use-o como minuto 1.

O resultado mensal é preciso no intervalo de 1 dia, o resultado horário é preciso no intervalo de 1 min

O problema não pode ser resolvido universalmente quando você tem uma quantidade fixa de memória e um fluxo "infinito" (pense muito grande) de tokens.

Uma explicação aproximada ...

Para ver o porquê, considere um fluxo de token que tem um token específico (ou seja, palavra) T a cada N tokens no fluxo de entrada.

Além disso, assuma que a memória pode conter referências (id da palavra e contagens) para no máximo M tokens.

Com essas condições, é possível construir um fluxo de entrada onde o token T nunca será detectado se o N for grande o suficiente para que o fluxo contenha diferentes tokens M entre os Ts.

Isso é independente dos detalhes do algoritmo top-N. Depende apenas do limite M.

Para ver por que isso é verdade, considere o fluxo de entrada composto de grupos de dois tokens idênticos:

T a1 a2 a3 ... a-M T b1 b2 b3 ... b-M ...

onde os a's e b's são tokens válidos diferentes de T.

Observe que neste fluxo, o T aparece duas vezes para cada ai e bi. No entanto, raramente parece ser eliminado do sistema.

Começando com uma memória vazia, o primeiro token (T) ocupará um slot na memória (limitado por M). Então a1 consumirá um slot até a- (M-1) quando o M se esgotar.

Quando aM chega, o algoritmo tem que descartar um símbolo, portanto, que seja o T. O próximo símbolo será b-1, o que fará com que a-1 seja liberado, etc.

Assim, o T não permanecerá residente na memória tempo suficiente para construir uma contagem real. Em suma, qualquer algoritmo perderá um token de frequência local suficientemente baixa, mas de alta frequência global (ao longo do comprimento do fluxo).