Questão Como contar 900 milhões de linhas em um segundo


Eu sempre uso o comando wc-l para contar o número de linhas. Mas quando meus arquivos (900 mill) são grandes, eu tenho que esperar pelo menos 5 minutos para ver os resultados. Alguma idéia melhor?


2


origem


Qual é o seu caso de uso exato? - scravy
Contar linhas é uma tarefa de tempo linear, então não vejo nenhum truque algorítmico para fazer isso mais rápido. Talvez você possa criar uma ferramenta que divide o arquivo em vários segmentos e encadeá-lo, mas talvez novamente isso já seja o que wc -l faz. - zneak
É difícil dizer como funciona o wc-l, imagino que a fonte esteja lá fora ... Mas se contar todos os caracteres e verificar o novo caractere de linha, isso seria ineficiente. Se esse for o caso, você pode trapacear se souber mais sobre o conjunto de dados. Se as linhas forem todas do mesmo tamanho ou próximas a ele, você poderá verificar apenas todos os n bytes de um trecho para uma nova linha e, se não for, percorrer os próximos n bytes procurando por novas linhas. Então você está verificando uma ordem de grandeza menos bytes
O gargalo é quase certamente o disco de E / S, não o código que faz a contagem, a menos que o arquivo esteja todo armazenado em cache na RAM. - Barmar


Respostas:


Teoricamente, você poderia pegar as primeiras N linhas (onde N é um número que você determina por experimento), a média de seu comprimento e, em seguida, dividir o tamanho do arquivo pelo comprimento médio. Isso lhe dará uma aproximação muito grosseira (que será mais precisa, mas mais lenta, quanto maior for N) do número real de linhas.


3



Bom, acho que estávamos pensando nas mesmas linhas :)
Tome ~ 1500 linhas a partir de uma linha verdadeiramente aleatória, assumindo que o comprimento da linha se encaixa em uma distribuição normal (o que pode não ser uma boa suposição), então você tem 95% de chance de que o comprimento médio dessas linhas represente o comprimento médio real. ~ 1500 constituiria uma amostra estatisticamente válida. Então dividir (tamanho do registro médio / tamanho do arquivo) renderia uma estimativa muito boa. Isto é muito mais problemático que wc -l. O seu verdadeiro problema é que o seu wc -l é limitado por E / S, e mesmo com uma unidade SATA de 15.000 rpm ou uma SAN realmente boa ~ 99% do tempo decorrido será de espera de E / S. - jim mcnamara
Eu imagino que um SSD seria melhor? Que tipo de desempenho você poderia esperar de um? - Niet the Dark Absol
"seria você" ... palavras certas, não necessariamente a ordem certa! - Niet the Dark Absol
Os SSDs são realmente caros por GB de armazenamento e são mais eficazes em um ambiente SAN em que a classificação por níveis de software está ativa. Um hipotético arquivo de linha de 900 milhões com registros de 128 bytes (avg) usaria 11,5 GB, e um OCZ Vertex 4 de 128 GB custa US $ 140 na newegg. Armazenar um arquivo usaria $ 12,57 de armazenamento, sobrecarga do sistema de arquivos. Isso é louco. IMO - criar arquivos gigantescos é frequentemente mal aconselhado, um uso inadequado de um recurso e é sempre caro. Um SSD forneceria pelo menos um fator de 10 de velocidade em uma leitura de arquivo completa. - jim mcnamara