고유 한 0에서 999까지 1000 개의 숫자를 생성하려면 어떻게해야합니까?
첫 번째 시도는 배열 {0, 1, 2, ..., 999}을 만들고 std::random_shuffle을 사용하여 순서를 뒤섞습니다. 그러나 긴 루프에서 숫자를 생성해야하므로 O (10^7)라고 가정 해 봅시다.이 방법은 실행 시간을 압도합니다.
이 문제를 해결하는 더 좋은 방법이 있습니까?임의로 n 개의 고유 번호를 생성합니다.
단계로 이동하고, std::random_shuffle 당신이 루프에 필요할 때마다 호출 실제로 당신이 필요로하는 방식으로 1000 개의 임의의 고유 번호를 생성 할 수있는 가장 빠른 방법입니다. 매번 배열을 다시 만들 필요는 없습니다.
루프에 O (10^7) 반복이 필요한지 여부는 중요하지 않습니다. 왜냐하면이 1000 개의 정수를 사용해야 할 필요가 있다고해서 다음과 같은 O (n) 연산이 필요하기 때문입니다. 당신이 그들을 사용할 때마다이 숫자들을 따라 지나간다. std::random_shuffle 시간 복잡도도 O (n)이므로 훨씬 더 느려지지는 않습니다.
shuffle의 구현을 요구합니다 (요구 사항에 대한 정확한 설명). 이는 표준 라이브러리보다 정확합니다. 그것은 긴 기회입니다.
하지만 시도해 보겠습니다. 나는 이렇게 말하고 싶다. 10^7 개의 그러한 순열을 가진 파일을 준비하고 그것으로부터 읽는다. 어쨌든 프리 페치를해야합니다. 그렇지 않으면 느려질 것입니다. 다른 스레드에서 프리 페치하면 실제로 더 빨라질 수 있습니다. 그러나 그것은 단지 야생의 추측입니다.
생각해 보면 다중 스레드를 실행할 수있는 경우 간단한 생산자 - 소비자 솔루션을 사용할 수 있습니다. 한 스레드가 순열을 쓰고, 다른 스레드가 순열을 읽는 것.
숫자 컨테이너를 다른 컨테이너에 저장하십시오. C2.
C1의 임의 요소를 선택하는 요소의 색인 생성. 인덱스를 생성 할 때마다 컨테이너 C1에서 인덱스를 삭제하십시오. 다음 번엔 고유 번호가 표시됩니다. C1이 비어하게되면
는 것을, C2와 C1을 다시 채 웁니다하고 저장 1000 개 숫자의 배열을 유지하는 경우 2
100 개의 숫자를 생성하는 데 왜 10^7이 걸릴까요? – aaronman
@aaronman OP가 말한 것이 아닙니다. 그는 약 10^7 번 실행되는 루프에서 생성해야합니다. 매번 다른 세트의 난수를 갖는 – Elazar
? 이것의 목적은 무엇입니까, 나는 우리가 더 많은 정보없이 문제를 해결할 수 있다고 생각하지 않습니다, 당신은 모든 1000 개의 숫자를 거치지 않고 매번 다른 난수 세트를 생성하지 않을 것입니다. – aaronman