Combinando linhas de um arquivo para linhas em outro arquivo

Question

Eu tenho uma lista bastante grande (1 milhão ou mais) e outra lista enorme (17gb), eu preciso combinar as linhas na lista1 com a primeira parte de um arquivo delimitado 2 como tal:

Lista1:

98433259@34
90345394@43
94335053@23

Lista2

54353456@35:nancy
98433259@34:jack
94335053@23:james
32409533@86:robert

Saída:

98433259@34:jack
94335053@23:james

Eu tentei o grep -Fwf list1 list2 mas é muito lento

Existe alguma maneira mais rápida de fazer isso?

    

Answer 1

Muito lento? O que você espera? Você tem cerca de um milhão de linhas nesse arquivo, digamos 12 MB. Agora, para cada linha do outro arquivo, você precisa digitalizar todo o arquivo. Você pode dizer que a comparação para depois do primeiro byte em nove de dez casos, mas mesmo assim você terá que continuar procurando pela próxima nova linha, então realmente para cada linha do segundo arquivo cada byte do primeiro arquivo para passar pela CPU.

Agora, esse segundo arquivo pode ter um bilhão de linhas. Então você precisa digitalizar um bilhão de vezes 12 MB, ou seja, 12 Exabyte! Agora, se a sua máquina desktop tiver 8 MB de cache L3, esses 12 MB não se encaixam e precisam ser buscados na sua RAM. Felizmente, a RAM é rápida hoje em dia, talvez sua máquina tenha um rendimento efetivo de 20 GB / s. Se eu calcular corretamente, leva 600.000 segundos para acessar 12 Exebyte com 20 GB / s. 10.000 minutos. 167 horas. 7 dias. Uma semana.

Mas isso não é lento, é muito rápido! Leva apenas muito tempo, pois é uma tarefa enorme.

Se você quiser mais rápido, precisa de uma ferramenta projetada para essa finalidade. Você não encontrará isso pronto para usar, então vá escrever você mesmo.

Como? Use uma linguagem rápida como C e primeiro organize seus dados file1 para não precisar digitalizar todos os dados. Coloque cada registro em uma árvore. A raiz tem dez ponteiros para subárvores, dependendo do primeiro dígito. Cada subárvore tem outros dez ponteiros para subárvores, a menos que um ponteiro nulo indique que não há folhas aqui.

Agora, ao varrer o arquivo2, você pega o primeiro byte e pega o ponteiro de acordo com aquele dígito; nessa subárvore, escolha o ponteiro para o segundo dígito e assim por diante. Para oito dígitos e ponteiros de 64 bits, está no pior caso (correspondência encontrada) apenas 64 bytes que você tem que carregar, mais os bytes armazenados que saem com o nome. Talvez 80 bytes por linha, um bilhão de tempo se multiplique para 80 GB, obtido da memória em 4 segundos. Soa melhor, não é?

Esta é a maneira mais rápida de fazer isso, mas isso não é relacionado ao unix. Se você não sabe escrever um programa como esse, o StackOverflow deve ser o lugar certo para perguntar. Você pode se referir aqui.