엄청나게 많은 수의 수를 버킷으로 나누면

Question

숫자가 큽니다 (말은 1 조원). N 개의 버킷에 각각 어떤 범위가있는 것을 어떻게 나눌 수 있습니까? 사례 : 1. 배포가 비 균일하다고 가정합니다. 2. 배포가 균일하다고 가정합니다.

Answer 1

균일하지 않고 동등한 양의 버킷을 원한다면 자신의 람다 값을 사용하여 자신 만의 해시 테이블을 만들면됩니다.

숫자가 1-1000인데 10 개의 버킷이 필요한 경우 1-100의 해시 코드를 0으로, 101-200을 1로 지정하면됩니다. 이렇게하면 쉽습니다. do (maxNum (첫 번째 인스턴스는 100) -1)/100 (1000/numOfBuckets)을 사용하여 해시 테이블 내부의 배열 색인을 찾습니다.

분산을 원한다면 조금 더 어렵습니다. 이전의 고르지 않은 배포를 먼저 받아 들여야하고 각 버킷의 번호가 같아 지도록 다시 해시해야합니다.

다시 해쉬하려면 숫자 #을 가져 와서 (각 버킷을 반복하고 크기를 찾고 추가 한 다음) 버켓 수로 나눕니다. 이제 새로운 람다 값을 얻었습니다. 범위가 일정하지 않은 경우 (1-15, 15-20 등 대신 1-10, 11-20), 이전 해시 테이블을 반복하고 새 해시 테이블을 추가하십시오. 순차적으로 채우는 새로운 람다 값 - 가장 가까운 값입니다. (때로는 람다 값에서 -1을 얻습니다.)

균등 분포가 아니라 균등 한 분포를 신경 쓰지 않는다면, 가지고있는 숫자의 숫자를 취하고 quicksort와 같은 쉬운 정렬을 사용하여 정렬 한 다음 (람다 값) 개의 숫자를 버킷.

그게 무슨 뜻인지 확실하지 않지만 도움이 되길 바랍니다.