Ferramenta de linha de comando para expansão em pares de "cat" de todas as linhas em um arquivo

13

Suponha que eu tenha um arquivo (chamado de exemplo.txt) com esta aparência:

Row1,10
Row2,20
Row3,30
Row4,40

Eu quero ser capaz de trabalhar em um fluxo a partir deste arquivo que é essencialmente a combinação de pares de todas as quatro linhas (então devemos acabar com 16 no total). Por exemplo, estou procurando um comando de streaming (ou seja, eficiente) em que a saída é:

Row1,10 Row1,10
Row1,10 Row2,20
Row1,10 Row3,30
Row1,10 Row4,40
Row2,20 Row1,10
Row1,20 Row2,20
...
Row4,40 Row4,40

Meu caso de uso é que eu quero transmitir essa saída para outro comando (como o awk) para calcular alguma métrica sobre essa combinação de pares.

Eu tenho uma maneira de fazer isso no awk, mas minha preocupação é que o uso do bloco END {} significa que estou basicamente armazenando o arquivo inteiro na memória antes de gerar a saída. Exemplo de código:

awk '{arr[$1]=$1} END{for (a in arr){ for (a2 in arr) { print arr[a] " " arr[a2]}}}' samples/rows.txt 
Row3,30 Row3,30
Row3,30 Row4,40
Row3,30 Row1,10
Row3,30 Row2,20
Row4,40 Row3,30
Row4,40 Row4,40
Row4,40 Row1,10
Row4,40 Row2,20
Row1,10 Row3,30
Row1,10 Row4,40
Row1,10 Row1,10
Row1,10 Row2,20
Row2,20 Row3,30
Row2,20 Row4,40
Row2,20 Row1,10
Row2,20 Row2,20

Existe uma maneira eficiente de fazer isso sem ter que armazenar essencialmente o arquivo na memória e depois imprimir no bloco END?

    
por Tom Hayden 24.11.2014 / 02:57

9 respostas

12

Veja como fazer isso no awk para que não precise armazenar o arquivo inteiro em uma matriz. Este é basicamente o mesmo algoritmo do terdon.

Se você gosta, você pode até dar múltiplos nomes de arquivos na linha de comando e processar cada arquivo independentemente, concatenando os resultados juntos.

#!/usr/bin/awk -f

#Cartesian product of records

{
    file = FILENAME
    while ((getline line <file) > 0)
        print $0, line
    close(file)
}

No meu sistema, isso é executado em cerca de 2/3 do tempo da solução de Perl de Terdon.

    
por 24.11.2014 / 12:45
7

Não tenho certeza se isso é melhor do que fazer isso na memória, mas com sed que r extrai seu arquivo para cada linha em seu arquivo e outro no outro lado de um canal alternando H espaço antigo com linhas de entrada ...

cat <<\IN >/tmp/tmp
Row1,10
Row2,20
Row3,30
Row4,40
IN

</tmp/tmp sed -e 'i\
' -e 'r /tmp/tmp' | 
sed -n '/./!n;h;N;/\n$/D;G;s/\n/ /;P;D'

OUTPUT

Row1,10 Row1,10
Row1,10 Row2,20
Row1,10 Row3,30
Row1,10 Row4,40
Row2,20 Row1,10
Row2,20 Row2,20
Row2,20 Row3,30
Row2,20 Row4,40
Row3,30 Row1,10
Row3,30 Row2,20
Row3,30 Row3,30
Row3,30 Row4,40
Row4,40 Row1,10
Row4,40 Row2,20
Row4,40 Row3,30
Row4,40 Row4,40

Eu fiz isso de outra maneira. Ele armazena alguns na memória - armazena uma string como:

"$1" -

... para cada linha no arquivo.

pairs(){ [ -e "$1" ] || return
    set -- "$1" "$(IFS=0 n=
        case "${0%sh*}" in (ya|*s) n=-1;; (mk|po) n=+1;;esac
        printf '"$1" - %s' $(printf "%.$(($(wc -l <"$1")$n))d" 0))"
    eval "cat -- $2 </dev/null | paste -d ' \n' -- $2"
}

É muito rápido. É cat o arquivo quantas vezes houver linhas no arquivo para um |pipe . Do outro lado do canal, a entrada é mesclada com o arquivo em si, quantas vezes houver linhas no arquivo.

O material case é apenas para portabilidade - yash e zsh adicionam um elemento à divisão, enquanto mksh e posh perdem um. ksh , dash , busybox e bash são divididos em exatamente o mesmo número de campos que zeros impressos em printf . Como foi escrito acima, obtemos os mesmos resultados para cada um dos shells mencionados acima em minha máquina.

Se o arquivo for muito longo, pode haver $ARGMAX problemas com muitos argumentos, caso em que você precisaria introduzir xargs ou similar também.

Dada a mesma entrada que eu usei antes da saída ser idêntica. Mas, se eu fosse aumentar ...

seq 10 10 10000 | nl -s, >/tmp/tmp

Isso gera um arquivo quase idêntico ao que eu usei antes (sans 'Row') - mas em 1000 linhas. Você pode ver por si mesmo como é rápido:

time pairs /tmp/tmp |wc -l

1000000
pairs /tmp/tmp  0.20s user 0.07s system 110% cpu 0.239 total
wc -l  0.05s user 0.03s system 32% cpu 0.238 total

Em 1000 linhas há uma pequena variação no desempenho entre shells - bash é invariavelmente a mais lenta - mas porque o único trabalho que eles fazem é gerar a string arg (1000 cópias de filename - ) o efeito é mínimo. A diferença de desempenho entre zsh - como acima - e bash é 100º segundo aqui.

Aqui está outra versão que deve funcionar para um arquivo de qualquer tamanho:

pairs2()( [ -e "$1" ] || exit
    rpt() until [ "$((n+=1))" -gt "$1" ]
          do printf %s\n "$2"
          done
    [ -n "${1##*/*}" ] || cd -P -- "${1%/*}" || exit
    : & set -- "$1" "/tmp/pairs$!.ln" "$(wc -l <"$1")"
    ln -s "$PWD/${1##*/}" "$2" || exit
    n=0 rpt "$3" "$2" | xargs cat | { exec 3<&0
    n=0 rpt "$3" p | sed -nf - "$2" | paste - /dev/fd/3
    }; rm "$2"
)

Ele cria um link para seu primeiro argumento em /tmp com um nome semi-aleatório para que ele não seja colocado em nomes de arquivos estranhos. Isso é importante porque os argumentos de cat são enviados a ele por meio de um canal via xargs . A saída de cat é salva em <&3 , enquanto sed p solicita cada linha no primeiro argumento, quantas vezes houver linhas nesse arquivo - e seu script também é alimentado por meio de um pipe. Novamente paste mescla sua entrada, mas desta vez são necessários apenas dois argumentos - para sua entrada padrão e o nome do link /dev/fd/3 .

Esse último - o link /dev/fd/[num] - deve funcionar em qualquer sistema Linux e muito mais, mas se ele não criar um canal nomeado com mkfifo e usar isso, também deverá funcionar.

A última coisa que faz é rm do link que cria antes de sair.

Esta versão é realmente mais rápida ainda no meu sistema. Eu acho que é porque, embora ele execute mais aplicativos, ele começa a entregá-los seus argumentos imediatamente - enquanto antes eles empilhavam todos eles primeiro.

time pairs2 /tmp/tmp | wc -l

1000000
pairs2 /tmp/tmp  0.30s user 0.09s system 178% cpu 0.218 total
wc -l  0.03s user 0.02s system 26% cpu 0.218 total
    
por 24.11.2014 / 04:16
5

Bem, você sempre pode fazer isso em seu shell:

while read i; do 
    while read k; do echo "$i $k"; done < sample.txt 
done < sample.txt 

É muito mais lento que a sua solução awk (na minha máquina, demorou ~ 11 segundos para 1000 linhas, contra ~ 0,3 segundos em awk ), mas pelo menos nunca contém mais do que algumas linhas em memória.

O loop acima funciona para os dados muito simples que você tem em seu exemplo. Ele vai sufocar nas barras invertidas e vai comer espaços à direita e à esquerda. Uma versão mais robusta da mesma coisa é:

while IFS= read -r i; do 
    while IFS= read -r k; do printf "%s %s\n" "$i" "$k"; done < sample.txt 
done < sample.txt 

Outra opção é usar perl :

perl -lne '$line1=$_; open(A,"sample.txt"); 
           while($line2=<A>){printf "$line1 $line2"} close(A)' sample.txt

O script acima lerá cada linha do arquivo de entrada ( -ln ), salvará como $l , abrirá sample.txt novamente e imprimirá cada linha junto com $l . O resultado é todas as combinações de pares, enquanto apenas duas linhas são armazenadas na memória. No meu sistema, isso levou apenas cerca de 0.6 segundos em 1.000 linhas.

    
por 24.11.2014 / 03:53
4

com zsh :

a=(
Row1,10
Row2,20
Row3,30
Row4,40
)
printf '%s\n' $^a' '$^a

$^a em uma matriz ativa a expansão parecida com a chave (como em {elt1,elt2} ) para a matriz.

    
por 24.11.2014 / 09:16
4

Você pode compilar este código para obter informações bastante rápidas resultados.
Ele completa em torno de 0,19 - 0,27 segundo em um arquivo de 1000 linhas.

Atualmente, ele lê 10000 linhas na memória (para acelerar a impressão na tela), o que, se você tivesse 1000 caracteres por linha, usaria menos de 10mb de memória, o que não seria um problema. Você pode remover essa seção completamente e apenas imprimir diretamente na tela se isso causar um problema.

Você pode compilar usando g++ -o "NAME" "NAME.cpp"
Onde NAME é o nome do arquivo para salvá-lo e NAME.cpp é o arquivo em que esse código é salvo em

CTEST.cpp:

#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <sstream>
int main(int argc,char *argv[])
{

        if(argc != 2)
        {
                printf("You must provide at least one argument\n"); // Make                                                                                                                      sure only one arg
                exit(0);
   }
std::ifstream file(argv[1]),file2(argv[1]);
std::string line,line2;
std::stringstream ss;
int x=0;

while (file.good()){
    file2.clear();
    file2.seekg (0, file2.beg);
    getline(file, line);
    if(file.good()){
        while ( file2.good() ){
            getline(file2, line2);
            if(file2.good())
            ss << line <<" "<<line2 << "\n";
            x++;
            if(x==10000){
                    std::cout << ss.rdbuf();
                    ss.clear();
                    ss.str(std::string());
            }
    }
    }
}
std::cout << ss.rdbuf();
ss.clear();
ss.str(std::string());
}

Demonstração

$ g++ -o "Stream.exe" "CTEST.cpp"
$ seq 10 10 10000 | nl -s, > testfile
$ time ./Stream.exe testfile | wc -l
1000000

real    0m0.243s
user    0m0.210s
sys     0m0.033s
    
por 26.11.2014 / 13:56
2

Uma opção com Python é memory-map o arquivo e aproveitar o fato de que a biblioteca de expressões regulares do Python pode trabalhar diretamente com arquivos mapeados na memória. Embora isso tenha a aparência de executar loops aninhados sobre o arquivo, o mapeamento de memória garante que o SO traga a RAM física disponível de maneira ideal para a reprodução

import mmap
import re
with open('test.file', 'rt') as f1, open('test.file') as f2:
    with mmap.mmap(f1.fileno(), 0, flags=mmap.MAP_SHARED, access=mmap.ACCESS_READ) as m1,\
        mmap.mmap(f2.fileno(), 0, flags=mmap.MAP_SHARED, access=mmap.ACCESS_READ) as m2:
        for line1 in re.finditer(b'.*?\n', m1):
            for line2 in re.finditer(b'.*?\n', m2):
                print('{} {}'.format(line1.group().decode().rstrip(),
                    line2.group().decode().rstrip()))
            m2.seek(0)

Como alternativa, uma solução rápida em Python, embora a eficiência da memória ainda possa ser uma preocupação

from itertools import product
with open('test.file') as f:
    for a, b  in product(f, repeat=2):
        print('{} {}'.format(a.rstrip(), b.rstrip()))
Row1,10 Row1,10
Row1,10 Row2,20
Row1,10 Row3,30
Row1,10 Row4,40
Row2,20 Row1,10
Row2,20 Row2,20
Row2,20 Row3,30
Row2,20 Row4,40
Row3,30 Row1,10
Row3,30 Row2,20
Row3,30 Row3,30
Row3,30 Row4,40
Row4,40 Row1,10
Row4,40 Row2,20
Row4,40 Row3,30
Row4,40 Row4,40
    
por 24.11.2014 / 14:37
2
join -j 2 file.txt file.txt | cut -c 2-
  • junte-se por um campo não existente e remova o primeiro espaço

O campo 2 é vazio e igual para todo o elemento no arquivo.txt, então join irá concatenar cada elemento com todos os outros: ele está, de fato, calculando o produto cartesiano.

    
por 12.02.2017 / 00:43
1

No bash, o ksh deve funcionar também, usando apenas os built-ins do shell:

#!/bin/bash
# we require array support
d=( $(< sample.txt) )
# quote arguments and
# build up brace expansion string
d=$(printf -- '%q,' "${d[@]}")
d=$(printf -- '%s' "{${d%,}}' '{${d%,}}")
eval printf -- '%s\n' "$d"

Observe que, embora isso mantenha o arquivo inteiro na memória em uma variável do shell, ele precisa apenas de um único acesso de leitura a ele.

    
por 24.11.2014 / 15:19
0

sed solution.

line_num=$(wc -l < input.txt)
sed 'r input.txt' input.txt | sed -re "1~$((line_num + 1)){h;d}" -e 'G;s/(.*)\n(.*)/ /'

Explicação:

  • sed 'r file2' file1 - leia todo o conteúdo do arquivo do arquivo2 para cada linha do arquivo1.
  • Construção 1~i significa 1ª linha, depois 1 + i linha, 1 + 2 * i, 1 + 3 * i, etc. Portanto, 1~$((line_num + 1)){h;d} significa h linha pontiaguda antiga para o buffer, d elete o espaço padrão e inicia um novo ciclo.
  • 'G;s/(.*)\n(.*)/ /' - para todas as linhas, exceto a escolhida na etapa anterior, execute a seguinte linha: G et do buffer de retenção e anexe-a à linha atual. Em seguida, troque os lugares das linhas. Foi current_line\nbuffer_line\n , tornou-se buffer_line\ncurrent_line\n

Resultado

Row1,10 Row1,10
Row1,10 Row2,20
Row1,10 Row3,30
Row1,10 Row4,40
Row2,20 Row1,10
Row2,20 Row2,20
Row2,20 Row3,30
Row2,20 Row4,40
Row3,30 Row1,10
Row3,30 Row2,20
Row3,30 Row3,30
Row3,30 Row4,40
Row4,40 Row1,10
Row4,40 Row2,20
Row4,40 Row3,30
Row4,40 Row4,40
    
por 20.07.2017 / 14:10