얻기 10000 개 고유 한 임의의 숫자 (성능)

Question

가능한 중복 :
Create Random Number Sequence with No Repeats

난 단지 숫자를 짧은 문자열을 사용하는 단축 URL을 작성하고 싶습니다.

저는 카운트하고 싶지 않습니다. 다음 번 번호를 무작위 (또는 의사 랜덤)로하고 싶습니다. 첫번째 생각 알고리즘에서

은 다음과 같을 것이다 (의사 코드) :

do 
{ 
number = random(0,10000) 
} 
while (datastore.contains(number)) 

datastore.store(number, url) 

이 구현 문제는 : 데이터 저장소가 더 숫자가 포함으로, 가능성은이 루프가 실행됩니다된다 여러 번. 시간이 지남에 따라 성능이 저하됩니다.

이미 사용중인 난수를 얻는 더 좋은 방법은 없습니까?

Answer 1

일부 관련 질문 : # 2394246, # 54059, # 158716, # 196017 및 # 1608181.

적절한 접근 방식은 실시간 성능이 필요한 경우 생성 할 숫자의 수에 따라 다릅니다. 특정 범위에서 사용할 수있는 숫자의 일부만 가져 오면 코드 조각의 숫자 당 평균 시간은 O (1)이며 나중에 번호가 약간 증가하지만 O (1)은 계속 유지됩니다. 예를 들어, #1608181 answer을 참조하십시오. k 숫자가 2*k 숫자보다 많고 그 숫자가 O(k) 인 것으로 나타났습니다. (이 대답은 M<N/2 일 때 O (M) 시간에 N 개의 숫자 범위에서 M 번호를 생성하는 C 코드를 가지고 있으며 M>=N/2 일 때 O (M) 시간에 사용하는 방법을 설명합니다.

원한다면 O (1) 성능을 힘들게 제한하는 경우 방금 언급 한 프로그램을 사용하여 배열을 미리로드하거나 Justin에서 설명한대로 전체 정수 범위를 섞을 수 있습니다. 그 전처리 후에 각 액세스는 O (1)입니다. Buf 당신이 당신의 1 ... 10000 범위에서 3000 개의 숫자를 말하는 것보다 더 많이 그리지 않을 것이라는 것을 안다면, 그리고 어려운 시간 제한이 없다면, 당신이 가지고있는 코드는 O (1) 시간에 확률로 달릴 것입니다 k은 0.3^k와 같이 감소합니다. 즉, 최악의 경우 1 회 통과 가능성은 약 70 %, 2는 21 %, 3은 6 %, 4는 2 %, 5는 0.6 % 등이 될 수 있습니다.

Answer 2

1) 순차 값

2) shuffle 어레이

Answer 3

사용 암호화 배열을 채운다. 암호화는 되돌릴 수 있기 때문에 고유 한 입력은 고유 한 출력을 생성합니다. 64 비트 숫자의 경우 64 비트 블록 크기의 사이퍼를 사용하십시오. 32 비트 또는 16 비트와 같은 더 작은 블록 크기의 경우 Hasty Pudding Cypher을 살펴보십시오.

필요한 블록 크기에 상관없이 0, 1, 2, ... (적절한 블록 크기로)를 암호화하여 필요한만큼 고유하지 않은 순차 번호를 생성하십시오.