A maneira mais rápida de determinar se duas listas ordenadas contêm elementos exclusivos

Question

Eu tenho dois arquivos classificados A e B , em que o tamanho de A é muito maior que B , por exemplo, A é de 100 GB, enquanto B é de 50 MB. Quero rapidamente determinar se há linhas em B contidas em A , parando quando uma correspondência é feita. Eu atualmente tenho um script python para isso, mas ele é executado lentamente quando o processo tem que ser repetido milhares de vezes para diferentes B 's.

    

Answer 1

Usando comm , você pode obter um script para retornar na primeira correspondência usando head e um fifo:

#!/bin/bash -e 

[ -p tmpfifo ] || mkfifo tmpfifo
comm -12 A B | head -n1 >tmpfifo &

# If this wc is zero, no matches.  Otherwise, a match was found. 
# You can use this directly in the script, echo it, 
# change the script exit value, or however else you need to use it.
wc -l tmpfifo 

No momento, isso continuará a executar a comunicação em segundo plano, estou tendo problemas para encontrar o PID correto para matar ( $! está fornecendo head e não está matando comm ). Se tiver certeza de que esta é a única comunicação em execução, você pode usar killall , mas isso é potencialmente perigoso no caso de outras pessoas estarem em execução.

    

Answer 2

Você pode tentar o AWK para analisar os arquivos. No começo, eu estava pensando em dividir o arquivo maior, ou armazenar A em mem e percorrer B, comparando cada linha com A em mem. No entanto, acho que o AWK pode ser o que você está procurando.

link é uma cartilha

link está falando sobre comparação de arquivos. Eu não estou em um linux agora, ou tentaria testá-lo.

gawk link

    

Answer 3

Se os arquivos estiverem classificados, você poderá conseguir juntar-se (1) ou combinar (1) para trabalhar de forma razoavelmente eficiente. head -1 na saída irá parar na primeira linha e deve matar o resto do comando com um SIGPIPE quando ele sair.

Adicionalmente, você pode ser capaz de reduzir o tamanho do problema usando uniq (1) no arquivo maior A. Isto irá resumi-lo a um conjunto de linhas distintas, que podem então ser comparadas com sua lista de arquivos B .

Outra possibilidade seria adaptar seu script python para fazer algo como o seguinte.

For each B file:
    Read in each line
    Add the file name to a list of files keyed on a hash of the line 

Loop through the A file:
    Look up each line in the dictionary
    Output the file name when a match is found.

Isso consumirá uma grande quantidade de memória se o número de linhas distintas em seus arquivos 'B' for grande, então pode ou não ser prático. Se você não se importar com o pós-processamento para eliminar os falsos positivos, poderá cortar o consumo de memória nesse estágio apenas armazenando o hash.

Uma terceira forma seria carregar todo o lote em um banco de dados e fazer a junção, mas isso implica na sobrecarga de importar os dados, o que pode ser muito grande. Com os índices apropriados, a consulta real correspondente seria bastante rápida e poderia verificar todos os arquivos B de uma vez, ou seja,

Create table A (
       TextLine varchar (100) -- or whatever length you need
)

Create table B (
       TextLine varchar (100)
      ,Filename varchar (20)
)

Alter table B
  add constraint PK_B
      primary key (TextLine, FileName)


select distinct B.FileName
  from A
  join B
    on a.TextLine = B.TextLine

    

Answer 4

grep -F -x -f B A | head -n 1

Eu acho que este não é um recurso bem conhecido do grep, mas você pode passar vários padrões através de um único arquivo, colocando cada um em sua própria linha. Isso é útil principalmente em combinação com -F para procurar por cadeias exatas (com -E , o efeito é o mesmo que vários padrões separados por | ).

Eu não fiz comparativo, mas espero que seja o mais rápido possível sem fazer o pré-processamento em A