거의 10억 개의 고유한 정수 레코드를 생성해야 합니다. awk를 사용해 보았지만 500만 개 이상의 레코드가 생성되지 않았습니다. 내가 지금까지 시도한 것은 다음과 같습니다.
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)
}'
그러나 599160237개 이상의 레코드가 생성되지 않아 프로세스가 자동으로 종료되었습니다.
답변1
GNU seq
+를 사용 sort
하여 먼저 고유한 1B 정수 목록(순서대로)을 생성한 다음 sort -R
무작위로 섞을 수 있습니다. 이는 CPU 효율적이지는 않지만 정렬 시 사용 가능한 메모리를 최대한 많이 사용한 다음 임시 파일로 되돌리므로 메모리 독립적입니다.
이 작업은 몇 분 정도 소요됩니다(머신의 CPU/Ram/디스크에 따라 다름).
$ 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
RAM이 충분한 컴퓨터에 액세스할 수 있다면 GNU를 사용할 수 있습니다 shuf
.
$ shuf -i 1-1000000000 > 1B.random.txt
경험상 shuf
내 컴퓨터에는 약 8GB의 여유 메모리와 약 6분의 런타임이 필요합니다.
답변2
작업을 완료하는 데 너무 많은 메모리를 할당하지 않는 프로그램을 사용하는 것이 좋습니다. 그러나 난수 생성에는 문제가 있습니다. 완전히 난수가 필요한 경우 /dev/urandom과 같은 "좋은" 난수 소스를 사용해야 합니다.
제 생각에는이 C 프로그램이 작업에 도움을 줄 수 있습니다. 이는 사용자가 지정하는 세 가지 인수(start int, end int 및 생성할 숫자)를 사용하여 런타임에 숫자를 생성합니다. 따라서 (0..200) 범위에서 100개의 정수를 생성하려면 다음을 수행할 수 있습니다.
./mkrnd 0 200 100
파일로 리디렉션해야 할 수도 있으므로 다음을 수행하십시오.
./mkrnd 0 200 100 >randomints.txt
컴파일은 매우 간단합니다. 그냥 하세요 gcc mkrnd.c -o mkrnd
(아니면 제가 컴파일해 드릴 수도 있습니다).
충분히 빠르다고 생각하지만 작업하는 데 여전히 몇 시간이 걸릴 것 같습니다. Athlon64 5000+에 대한 내 경우:
% time null ./mkrnd 0 1000000000 10000000
real 0m33.471s
user 0m0.000s
sys 0m0.000s
#if 0 ... #endif를 제거하여 /dev/urandom에서 임의의 정수를 가져오도록 합니다(느릴 수 있음).
메모리 요구 사항 관련: musl 시스템에서는 전체 런타임 동안 4K RSS만 필요합니다.
편집하다:gettimeofday를 clock_gettime으로 바꾸면 속도가 두 배 향상됩니다.
답변3
Python3.4에서는 다음과 같이 거대한 숫자를 생성하고 사용할 수 있습니다.
#!/bin/python3.4
import random
print(random.sample(range(1, 1000000000000),1000000000))
그러면 10억 개의 고유 숫자가 인쇄됩니다.
대규모 샘플을 할당하는 데 메모리 문제가 있는 경우 범위를 사용하고 루프에서 숫자를 인쇄할 수 있지만 이는 무작위가 아닌 시퀀스입니다.
x=range(1, 1000000000000)
for i in x:
print (i) #or process i , whatever the operation is.
답변4
프로세스가 종료되는 이유는 awk
코드에 발생한 배열에 버그/제한이 있거나 코드가 너무 공간을 많이 소모하여 일부 프로세스 기반 제한에 도달하기 때문일 수 있습니다.
range
내 말은, 10억 개의 정의된 값을 포함하는 최대 인덱스가 100억(기준)인 배열을 구축하려고 한다는 것입니다 . 따라서 awk
100억 개의 변수를 위한 공간을 예약해야 할 수도 있습니다. 이것이 얼마나 많은 공간을 의미하는지 잘 모르겠지만 100억 개의 16비트 정수는 18.5GB를 의미하며, awk
이렇게 희소한 배열을 구축하는 것이 현명하더라도 1.8GB 이상이 필요하므로 숫자를 저장하는 것은 생성.
결과를 고유하게 유지하려면 이전 값을 모두 어딘가에 저장해야 하므로 공간을 많이 차지할 수밖에 없지만, 다른 언어에서는 알고리즘이 수행되도록 허용할 수도 있습니다.
그렇다면 막대한 메모리 요구 사항을 어떻게 제거할 수 있을까요?
A.Gordon은 시퀀스에 의존하고 무작위성을 얻기 위해 이를 섞는 옵션을 제안했습니다. 이 접근 방식은 결과가 실제로 숫자여야 하고 해당 결과가 지정된 범위에서 나오길 원할 때 잘 작동합니다. 범위가 1에서 N보다 더 복잡한 경우 생성 시퀀스를 사용한 awk
다음 에 전달할 수 있습니다 sort -R
. 생성된 숫자의 범위와 개수를 다르게 만드는 방법에 대한 답변에 대한 내 의견도 참조하세요.
한 가지 옵션은 암호화(해시) 함수를 사용하여 난수를 생성하는 것일 수 있지만 이 경우 이러한 함수는 일반적으로 N비트 출력을 생성하고 결과를 손상시킬 수 없기 때문에 범위를 1에서 N으로 정의할 수 없습니다. 충돌 위험이 없습니다(세트에 중복된 숫자가 있음). 그러나 이러한 함수는 쉽게 10억 개의 고유한 출력을 생성하도록 보장됩니다(이 해시 함수는 매우 많은 반복 호출에도 불구하고 동일한 출력을 두 번 생성하지 않도록 설계되었기 때문입니다). 구현에 따라 출력이 숫자가 아닌 문자열일 수도 있고 문자열 출력을 숫자로 변환할 수도 있지만 일반적으로 출력 크기가 매우 크기 때문에 변환으로 인해 발생하는 숫자의 범위도 엄청날 것입니다. 당신은부터 시작할 수 있습니다이 Stackoverflow 질문이 옵션을 살펴보는 데 관심이 있다면.
충돌 위험이 있는 경우 가능성이 낮더라도 좋은 무작위성 소스(/dev/urandom은 옵션)를 사용하여 10억 개의 숫자를 생성해 볼 수 있습니다. 수십억 개의 고유 숫자를 얻을 확률이 얼마나 될지는 모르겠지만 시도해 볼 가치는 확실히 있습니다. 그러나 결과 집합에 중복 항목이 있는지 알 수 있는 메모리 효율적인 방법은 없습니다. 이렇게 하려면 비교를 위해 모든 숫자를 메모리에 저장해야 하기 때문입니다.