Guia passo a passo para calcular o custo de junção na triagem externa
A ordenação externa é uma técnica usada para lidar com grandes conjuntos de dados que não se encaixam na memória principal. Um aspecto chave da ordenação externa é calcular o custo de mesclagem, o que ajuda a determinar a eficiência do processo de ordenação. Este guia fornece uma abordagem passo a passo para entender e calcular os custos de mesclagem na ordenação externa.
Compreender a Ordenação Externa
A ordenação externa envolve dividir os dados em blocos gerenciáveis, ordenar cada bloco individualmente e depois fundir estes blocos ordenados num único ficheiro ordenado. O processo de fusão pode ser executado em várias passagens, dependendo do número de blocos e da memória disponível.
Componentes do Custo de Mesclagem
O custo de mesclagem depende principalmente do número de passes e da quantidade de dados processados durante cada passagem. É influenciado por:
- O número de sequências iniciais ordenadas (chunks)
- O número de arquivos mesclados simultaneamente (fan-in)
- O tamanho total dos dados
Calculando o Custo de Mesclagem
O custo total da mesclagem pode ser calculado usando a fórmula:
Custo de fusão = Número de passes × Total de dados tratados em cada passe
Para determinar o número de passes, use a fórmula:
Número de passes = logfan-in (Número de execuções iniciais)
Por exemplo, se houver 16 execuções iniciais e o sistema puder mesclar 4 arquivos de uma vez, então:
Número de passes = log4 16 = 2
O total de dados processados em cada passagem é igual ao tamanho total de todos os dados que estão sendo mesclados durante esse passo. A soma de todos os passos dá o custo total da mesclagem.