Dados os dados classificados, a solução de pesquisa é óbvia. Dados dados não classificados, as opções sensatas são classificadas e depois pesquisadas ou apenas lineares.
Esta pergunta é sobre o que fazer se os dados forem classificados de algum modo , mas não puderem ser reorganizados (as operações de gravação exigem a exclusão do setor e os setores não cabem no RAM).
os detalhes:
Os registros de dados são registrados sequencialmente com um carimbo de data / hora . No entanto, o relógio de data e hora é redefinido de tempos em tempos para a Epoch por um tempo antes de ser sincronizado ou simplesmente ajustado de volta devido ao horário de verão etc.
O resultado da pesquisa deve ser o registro de log com o carimbo de data e hora mais próximo do tempo especificado. Ao executar uma pesquisa binária de registro em um carimbo de data / hora específico, é possível pousar em um patch de dados de log descontínuos e girar na direção errada.
Além de um método linear bruto, existe uma heurística da qual podemos tirar vantagem aqui? por exemplo, uma pesquisa simplex imune a mínimos locais?
atualizar:
Podemos supor que cerca de 95% dos registros estejam em sequência classificada. cerca de 5% (espalhados pelo tronco) são soluços sujos. O início dos soluços pode ser identificado quando o registro de data e hora retrocede no tempo e tem um carimbo anterior ao início do log
fonte
Respostas:
Suposições adicionais
Esta resposta é baseada nas seguintes suposições adicionais:
Algoritmo de pesquisa
A pesquisa é dividida em dois algoritmos diferentes, na verdade. Caso você pesquise um log com um registro de data e hora posterior ao início do log, saiba que ele não será encontrado nos soluços e use a pesquisa que não é do soluço abaixo. Caso você pesquise um carimbo de data / hora antes do início do log, use a pesquisa de soluço . Se você não pesquisar pelo carimbo de data / hora, mas por alguns outros critérios, tente primeiro a pesquisa sem soluço devido à cobertura de 95% e tente a pesquisa por soluço se não encontrar nada.
Opcionalmente, você pode acelerar a pesquisa sem soluço por uma etapa de pré-processamento.
Pré-processamento (opcional)
Se possível, pré-analise seus dados com uma pesquisa linear para descobrir as posições dos dados do soluço. Isso depende inteiramente da viabilidade de poder armazenar esses intervalos, o que pode ser possível, uma vez que eles representam apenas 5% dos seus logs (ou talvez não, nesse caso, o desempenho diminui).
Observe que a estrutura de dados correspondente deve ser atualizada sempre que você escreve novos logs ou, pelo menos, deve poder informar até que ponto dos logs o pré-processamento foi executado.
Pesquisa sem soluço
A pesquisa de dados sem soluço é possível através de uma combinação de pesquisa binária e linear. Você realiza uma pesquisa binária normal, no entanto, quando o elemento dinâmico é marcado com data e hora antes do início do log, ou seja, o elemento dinâmico é um soluço, você precisa determinar a primeira entrada de log antes do elemento dinâmico e usá-la como o elemento dinâmico real da sua pesquisa binária.
Essa primeira entrada de registro com registro de data e hora após o início do registro é encontrada por meio de uma pesquisa linear a partir do elemento pivô do soluço. Se você souber do pré-processamento ou atualizações incrementais dos soluços em cache em que o elemento dinâmico relevante está posicionado, você poderá pular para lá em tempo constante. Se você tiver que executar a pesquisa linear completa, atualize uma estrutura de dados para armazenar que essas posições sejam cobertas por dados de soluço, para que da próxima vez você possa determinar rapidamente o elemento de articulação correto.
Soluço-pesquisa
Isso depende se você fez o pré-processamento. Caso contrário, é uma pesquisa linear por todos os seus dados (e você também pode executar as peças de pré-processamento neste momento). Caso contrário, sua estrutura de dados pré-processada poderá informar as posições dos dados do soluço e você poderá pesquisar diretamente através deles, ou seja, realizar uma pesquisa linear apenas através dos 5% dos dados do soluço.
atuação
Para pesquisa sem soluço com dados totalmente pré-processados, você pode obter quase o desempenho de uma pesquisa binária padrão. Em vez de uma comparação simples em cada etapa, você precisa de uma comparação adicional para determinar se você encontra um elemento soluço e, em caso afirmativo, precisa de um acesso à sua estrutura de dados para encontrar o elemento pivô real. Esse trabalho adicional, no entanto, é um pouco aliviado pelo fato de você não apenas descartar metade do seu conjunto de dados, mas também descartar a parte de dados do soluço.
Obviamente, se você precisar recorrer à pesquisa linear, isso será prejudicado.
A pesquisa de soluço é um caso ruim se você não tiver informações sobre soluços existentes disponíveis e precisar pesquisar linearmente todos os dados.
Por fim, se você não procurar um carimbo de data / hora, mas existem outros critérios e não existe essa entrada de log, esse é o seu pior caso. De fato, se você não possui uma estrutura de dados para os soluços, ela acaba sendo mais lenta que a pesquisa linear, pois as duas execuções de pesquisa podem varrer linearmente as mesmas posições de soluço (embora ainda seja O (n)).
Se você possui a estrutura de dados disponível e totalmente pré-processada, o pior tempo de execução se resume a O (max (log (M) * log (N), M)), em que M é a quantidade de dados do soluço, que é pesquisada linearmente, e supondo que você possa procurar o final dos dados do soluço, em qualquer posição do soluço da sua estrutura de dados em O (log (M)).
fonte