Grep faz com que o sistema inteiro congele ao comparar dois arquivos

Question

O que eu queria é comparar dois arquivos e verificar se todas as linhas em file1 existem em file2 . Minha primeira tentativa: grep -v -f file2 file1 . Isso resultou em muitos erros de sintaxe (, mas não congelou nada ). Eu rapidamente descobri que é porque eu preciso usar -F como explicado aqui . Então corri grep -Fvf file2 file2 e segundos depois todo o meu sistema ficou congelado por alguns minutos, até que o xorg travasse completamente.

Consegui tirar esta foto da tela congelada:

Equandofinalmenteconseguientrarnotty2,fuisaudadacomisso:

Perguntas:

1. Foi a causa do sistema congelado simplesmente que ele ficou sem RAM, ou há mais?
2. Por que o grep usa ~ 14GB de RAM (e quer mais) para comparar dois arquivos de 250MB?
3. Eu poderia usar ferramentas para limitar a RAM que o grep pode usar, mas todas as AFAIKs simplesmente matarão o processo quando ele atingir x GB de RAM, então isso não me ajudará. O que alguém faz em tal situação? Vamos supor que temos que usar o grep.

Editar: já encontrei uma solução sem grep. Estou muito curioso sobre por que e como isso pode acontecer ainda. + 14GB de RAM para dois arquivos de 250MB só parece estranho para mim. Não estou procurando uma alternativa sobre como posso comparar meus arquivos com essa pergunta.

    

Answer 1

1. O motivo foi definitivamente ficou sem memória.

2. Como você não está "comparando dois arquivos", está usando um arquivo de 250 MB como fonte de padrões para o grep. O Grep compila esses padrões em uma variante de um autômato finito determinístico , e a representação desses DFAs consome memória. Se você tem muitos padrões (como 250MB de padrões), ocupa um lote de espaço, porque transformar o autômatos finitos não determinísticos que correspondem a muitos padrões em um DFA podem causar um aumento exponencial.

grep é feito para parecer muito eficiente para alguns padrões em um ou vários arquivos grandes. Não é feito para "comparar" arquivos. Se você tentar usá-lo para isso, as coisas podem dar errado. Como eles fizeram no seu caso.

A complexidade é importante, é por isso que você aprende sobre a notação de O e sobre todas essas coisas extravagantes.

3. Em tal situação, você usa um programa que é feito para sua situação, não um programa que usa um algoritmo que é exponencial de espaço para o seu tipo de problema.

Você disse que não queria saber a alternativa, mas como ela envolve uma ferramenta menos conhecida, vou lhe dizer de qualquer maneira:

Se a pergunta for "toda linha do arquivo1 também existe no arquivo2, independentemente da ordem", o que você faz é classificar os dois arquivos e, em seguida, usar comm , que espera os arquivos classificados, e coloca fora (1 ) linhas no arquivo1, mas não no arquivo2, (2) linhas no arquivo2, mas não no arquivo1 e (3) linhas nos dois arquivos, conforme sua conveniência.