Geração de dados em massa

Question

Eu preciso gerar quase 1 bilhão de registros de inteiros únicos. Eu tentei com o awk, mas não está gerando mais de 5 milhões de registros. Abaixo está o que eu tentei até agora -

 awk -v loop=10000000000 -v range=10000000000 'BEGIN{
  srand()
  do {
    numb = 1 + int(rand() * range)
    if (!(numb in prev)) {
       print numb
       prev[numb] = 1
       count++
    }
  } while (count<loop)
}' 

Mas não está gerando mais de 599160237 registros e processos foram mortos automaticamente

    

Answer 1

Você pode usar o GNU seq + sort para primeiro gerar uma lista de inteiros únicos de 1B (em ordem sequencial), depois sort -R para embaralhá-los aleatoriamente. Embora isso não seja eficiente para a CPU, ela é independente da memória, pois a classificação usará a quantidade de memória disponível e, em seguida, será revertida para arquivos temporários.

Isso levará vários minutos (dependendo da CPU / RAM / disco da sua máquina):

$ seq 1000000000 > 1B.txt

$ ls -lhog 1B.txt 
-rw-rw-r-- 1   9.3G Dec 26 17:31 1B.txt

$ sort -R 1B.txt > 1B.random.txt

Se você tiver acesso a uma máquina com RAM suficiente, poderá usar o GNU shuf :

$ shuf -i 1-1000000000 > 1B.random.txt

Empiricamente, shuf precisava de ~ 8GB de RAM livre e ~ 6 minutos de tempo de execução na minha máquina.

    

Answer 2

Será melhor usar um programa que não aloque muita memória para concluir a tarefa. No entanto, há um problema com a geração de números aleatórios: se você precisa de números completamente aleatórios, então você precisa usar uma fonte de números aleatórios "boa" como / dev / urandom.

Acho que este programa em C pode ajudá-lo nessa tarefa. Ele gera números na execução e, com três argumentos, você especifica: start int, end int e number deles para gerar. Então, para gerar 100 ints ao alcance em (0..200), você faz:

./mkrnd 0 200 100

Você provavelmente desejará um redirecionamento para o arquivo, então

./mkrnd 0 200 100 >randomints.txt

A compilação é simples, basta fazer gcc mkrnd.c -o mkrnd (ou eu posso compilá-lo para você).

Acredita-se que seja rápido o suficiente, mas ainda vai exigir horas para trabalhar, eu acho. Para mim no Athlon64 5000 +:

% time null ./mkrnd 0 1000000000 10000000                                                          

real    0m33.471s
user    0m0.000s
sys 0m0.000s

Remova #if 0 ... #endif para fazer com que ele pegue números inteiros aleatórios de / dev / urandom (talvez mais lento).

E sobre os requisitos de memória: é necessário apenas 4K RSS no sistema musl durante todo o tempo de execução.

EDIT: Substituir gettimeofday por clock_gettime oferece velocidade dupla.

    

Answer 3

em python3.4 você pode gerar e jogar com números enormes como este:

    #!/bin/python3.4
    import random
    print(random.sample(range(1, 1000000000000),1000000000))

isto imprimirá um bilhão de números únicos

se houver problema de memória ao alocar uma amostra enorme, então é possível usar o intervalo e imprimir os números em um loop, mas isso será em uma sequência, não aleatório:

    x=range(1, 1000000000000)
    for i in x:
      print (i)     #or process i , whatever the operation is.

    

Answer 4

A razão para o processo ser morto pode ser que awk tem um bug / limitação em matrizes que seu código está atingindo, ou seu código consome muito espaço e atinge algum limite baseado em processo.

Quero dizer, você está tentando construir uma matriz com índice máximo de 10 bilhões (com base no range ) com 1 bilhão de valores definidos. Portanto, awk precisa potencialmente reservar espaço para 10 bilhões de variáveis. Não estou familiarizado o suficiente para dizer quanto espaço significaria, mas 10 bilhões de números inteiros de 16 bits significariam 18,5 GB, e mesmo que awk seja inteligente na criação de um array tão esparso, seria necessário mais de 1,8 GB os números que você está gerando.

Para poder manter os resultados exclusivos, você precisará ter todos os valores anteriores em algum lugar, portanto, ele será necessariamente pesado em requisitos de espaço, mas pode ser que alguma outra linguagem permita que o algoritmo seja concluído.

Como escapar dos enormes requisitos de memória, então?

A.Gordon apresenta uma opção, confiando em uma sequência e simplesmente embaralhando-a para aleatoriedade. Isso funciona bem quando há uma exigência de que o resultado seja verdadeiramente números e você deseja que eles sejam de um determinado intervalo. Se o intervalo for mais complexo do que de um para N, você poderá gerar a sequência com awk e, em seguida, passá-la para sort -R . Veja também meu comentário sobre a resposta de como tornar o intervalo e a contagem de números produzidos diferentes.

Uma opção poderia ser usar uma função criptográfica (hash) para produzir os números aleatórios, mas, nesse caso, você não pode definir o intervalo como 1 a N, pois essas funções geralmente produzem saída de N bits e você não pode mangle os resultados sem arriscar produzir uma colisão (um número duplicado no conjunto). Tais funções, no entanto, seriam garantidas para produzir facilmente 1 bilhão de saídas únicas (como essas funções hash são projetadas para não produzir a mesma saída duas vezes mesmo com um extremamente grande número de chamadas repetidas). Dependendo da implementação, sua saída pode não ser números, mas strings, e é possível converter a saída da string em números, mas como o tamanho da saída é geralmente muito grande, o intervalo dos números resultantes da conversão seria muito grande. Você pode começar de esta pergunta do Stackoverflow se você Estou interessado em explorar esta opção.

Se você puder arriscar a chance de ter uma colisão, mesmo que isso seja improvável, você pode tentar usar uma boa fonte de aleatoriedade (/ dev / urandom é uma opção) para gerar os 1 bilhão de números. Eu não sei qual a probabilidade de você conseguir 1 bilhão de números únicos, mas tentar valer certamente valeria a pena. Não há uma maneira eficiente de dizer se há uma duplicata no conjunto de resultados, já que isso exigiria ter todos os números na memória para comparação.