10 억 숫자의 중앙값 계산
10 억 개의 컴퓨터와 100 대의 컴퓨터가 있다면이 숫자의 중앙값을 찾는 가장 좋은 방법은 무엇입니까?
내가 가진 한 가지 해결책은 다음과 같습니다.
- 컴퓨터간에 세트를 동일하게 분할하십시오.
- 그것들을 정렬하십시오.
- 각 세트의 중앙값을 찾으십시오.
- 중앙값 세트를 정렬하십시오.
- 가장 낮은 중앙값에서 가장 높은 중앙값까지 한 번에 두 세트를 병합하십시오.
우리가있는 경우 m1 < m2 < m3 ...먼저 병합을 Set1하고 Set2그 결과 세트에서 우리는 모든 숫자의 평균보다 낮은 삭제할 수 있습니다 Set12(통합). 따라서 어느 시점에서나 동일한 크기의 세트가 있습니다. 그런데 이것은 병렬 방식으로 수행 할 수 없습니다. 어떤 아이디어?
아, 내 뇌는 이제 막 시작 됐습니다. 저는 현명한 제안을했습니다. 인터뷰를했다면 아마도 너무 늦었을 것입니다.
기계 1은 "제어 기계"라고하며, 논쟁의 여지가 있기 때문에 모든 데이터로 시작하여 같은 소포로 다른 99 대의 기계로 보내거나 데이터가 기계간에 균등하게 분배되기 시작합니다. 데이터의 1/99를 서로에게 보냅니다. 파티션이 같을 필요는 없으며 닫기 만하면됩니다.
서로 다른 시스템은 데이터를 정렬하며 낮은 값을 먼저 찾는 것을 선호합니다. 예를 들어, 빠른 정렬은 항상 파티션의 아래쪽을 먼저 정렬합니다 [*]. 그것은 가능한 한 빨리 순서대로 데이터를 제어 시스템에 다시 씁니다 (정렬을 계속하기 위해 비동기 IO를 사용하고 아마도 Nagle을 켜면 약간 실험).
제어 시스템은 도착하는 데이터에 대해 99-way 병합을 수행하지만, 표시된 값의 수를 유지하면서 병합 된 데이터를 버립니다. 중앙값을 1/2 십억 및 1/2 십억에 1을 더한 평균으로 계산합니다.
이것은 "무리가 가장 느린"문제로 어려움을 겪고 있습니다. 알고리즘은 중간 값보다 작은 모든 값이 정렬 기계에 의해 전송 될 때까지 완료 될 수 없습니다. 그러한 가치 중 하나가 데이터 소포 내에서 상당히 높을 가능성은 합리적입니다. 따라서 데이터의 초기 파티셔닝이 완료되면 예상 실행 시간은 데이터의 1/99를 정렬하여 제어 컴퓨터로 다시 보내는 시간과 컨트롤이 데이터의 1/2을 읽는 시간의 조합입니다. . "조합"은 최대 시간과 그 시간의 합계 사이에있을 수 있으며 아마도 최대에 가깝습니다.
내 본능은 네트워크를 통해 데이터를 전송하는 것보다 데이터를 정렬하는 것보다 빠르기 때문에 (중앙값을 선택하는 것만 제외하고) 상당히 빠른 네트워크 여야한다는 것입니다. 예를 들어 데이터가 포함 된 RAM에 동등한 액세스 권한을 가진 100 개의 코어가있는 경우 네트워크가 즉각적인 것으로 추정 될 수있는 경우 더 나은 전망이 될 수 있습니다.
네트워크 I / O가 한계가 있기 때문에 최소한 데이터가 제어 시스템으로 되돌아 오는 경우 약간의 트릭이있을 수 있습니다. 예를 들어, "1,2,3, .. 100"을 보내는 대신 정렬 시스템에서 "100보다 작은 100 개 값"을 의미하는 메시지를 보낼 수 있습니다. 그런 다음 제어 시스템은 수정 된 병합을 수행 할 수 있습니다. 여기서 병합 된 값 중 가장 작은 값 중 가장 작은 값을 찾은 다음 모든 정렬 시스템에 해당 값이 무엇인지 알려줍니다. 많은 값이 해당 값 아래로 "계산"되고 (b) 해당 지점에서 정렬 된 데이터 전송을 계속합니다.
보다 일반적으로, 컨트롤 머신이 99 개의 정렬 머신으로 플레이 할 수있는 영리한 도전-응답 추측 게임이있을 것입니다.
이것은 기계 사이의 왕복 여행과 관련이 있습니다. 단순한 첫 번째 버전은 피합니다. 나는 그들의 상대적인 성과를 맹목적으로 추정하는 방법을 정말로 모른다. 그리고 절충은 복잡하기 때문에, 이것이 실제 문제라고 가정하면, 내가 생각할 것보다 훨씬 더 나은 해결책이 있다고 생각한다.
[*] 사용 가능한 스택 허용-O (N) 추가 공간이없는 경우 먼저 수행 할 부분의 선택이 제한됩니다. 그러나 여분의 공간이 충분하면 선택을 할 수 있고 공간이 충분하지 않으면 처음 몇 개의 파티션에 대해 작은 부분을 먼저 수행하여 모서리를 자르는 데 필요한 것을 사용할 수 있습니다.
sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"
나는 여기에 반대되는 것을 싫어하지만 정렬이 필요하다고 생각하지 않으며 10 억 / 100 숫자 정렬과 관련된 알고리즘이 느릴 것이라고 생각합니다. 한 컴퓨터의 알고리즘을 생각해 봅시다.
1) 10 억에서 무작위로 1000 개의 값을 선택하고이를 사용하여 숫자, 특히 범위의 분포에 대한 아이디어를 얻습니다.
2) 값을 정렬하는 대신 방금 계산 한 분포를 기준으로 버킷에 할당하십시오. 버킷 수는 컴퓨터가 효율적으로 처리 할 수 있도록 선택되지만 그렇지 않으면 편리해야합니다. 버킷 범위는 각 버킷에 대략 동일한 수의 값이 들어가도록해야합니다 (이는 알고리즘에 중요하지 않지만 효율성에 도움이됩니다. 10 만 버킷이 적절할 수 있음). 각 버킷의 값 수를 기록하십시오. 이것은 O (n) 프로세스입니다.
3) 중앙값이 어느 버킷 범위인지 확인하십시오. 각 버킷의 총 수를 간단히 확인하면됩니다.
4) 해당 버킷의 값을 검사하여 실제 중앙값을 찾으십시오. 10,000 개의 숫자 만 정렬하기 때문에 원하는 경우 여기에서 정렬을 사용할 수 있습니다. 해당 버킷의 값 수가 크면 정렬하기에 충분히 작은 숫자가 될 때까지이 알고리즘을 다시 사용할 수 있습니다.
이 접근 방식은 컴퓨터간에 값을 나누어 사소하게 병렬화됩니다. 각 컴퓨터는 각 버킷의 총계를 3 단계를 수행하는 '제어'컴퓨터에보고합니다. 4 단계의 경우 각 컴퓨터는 관련 버킷의 (정렬 된) 값을 제어 컴퓨터에 보냅니다 (두 알고리즘 모두 병렬로 수행 할 수 있음) 그러나 가치가 없을 것입니다).
버킷 수가 충분히 많으면 3 단계와 4 단계가 모두 간단하므로 전체 프로세스는 O (n)입니다.
실제로 10 억은 현대 컴퓨터에서 지루한 작업입니다. 우리는 여기서 4GB 정수의 4 바이트 정수에 대해 이야기하고 있습니다 ... 4GB ... 그것은 일부 스마트 폰의 RAM입니다.
public class Median {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int[] numbers = new int[1_000_000_000];
System.out.println("created array after " + (System.currentTimeMillis() - start) + " ms");
Random rand = new Random();
for (int i = 0; i < numbers.length; i++) {
numbers[i] = rand.nextInt();
}
System.out.println("initialized array after " + (System.currentTimeMillis() - start) + " ms");
Arrays.sort(numbers);
System.out.println("sorted array after " + (System.currentTimeMillis() - start) + " ms");
if (numbers.length % 2 == 1) {
System.out.println("median = " + numbers[numbers.length / 2 - 1]);
} else {
int m1 = numbers[numbers.length / 2 - 1];
int m2 = numbers[numbers.length / 2];
double m = ((long) m1 + m2) / 2.0;
System.out.println("median = " + new DecimalFormat("#.#").format(m));
}
}
내 컴퓨터의 출력 :
created array after 518 ms
initialized array after 10177 ms
sorted array after 102936 ms
median = 19196
그래서 이것은 단일 코어를 사용하여 2 분 이내에 (1:43은 임의의 숫자를 생성하는) 내 컴퓨터에서 완료되며 심지어 전체 정렬을 수행합니다. 정말 멋진 것은 없습니다.
이것은 분명히 더 큰 숫자 집합에 대한 흥미로운 작업입니다. 저는 여기서 지적하고자합니다. 10 억은 땅콩입니다. 놀랍도록 간단한 작업에서 복잡한 솔루션을 던지기 전에 두 번 생각하십시오.)
중간 값 및 99 번째 백분위 수와 같은 차수 통계 의 추정 은 t-digest 또는 Q-digest 와 같은 알고리즘으로 효율적으로 배포 될 수 있습니다 .
두 알고리즘 중 하나를 사용하여 각 노드는 다이제스트를 생성하여 로컬에 저장된 값의 분포를 나타냅니다. 다이제스트는 단일 노드에서 수집되어 병합 (분포를 효과적으로 합산) 한 다음 중앙값 또는 다른 백분위 수를 찾을 수 있습니다.
이 접근법은 elasticsearch 및 아마도 BigQuery (QUANTILES 함수의 설명으로 이동)에서 사용됩니다.
이 숫자 집합의 중앙값
2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89, 97
67입니다.
이 숫자 집합의 중앙값
2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89
40입니다.
질문이 약 1,000,000,000 정수 (x)에서 0> = x <= 2,147,483,647이고 OP가 (element (499,999,999) + element (500,000,000)) / 2 (숫자가 정렬 된 경우)를 찾고 있다고 가정합니다. 또한 100 대의 컴퓨터가 모두 같다고 가정합니다.
내 노트북과 GigE를 사용하여 ...
내가 찾은 것은 내 노트북이 1.3 초 만에 10,000,000 Int32를 정렬 할 수 있다는 것입니다. 따라서 대략적인 수치는 10 억 개의 숫자 정렬에 100 x 1.3 초 (2 분 10 초)가 소요될 것입니다.
기가비트 이더넷에서 40MB 파일의 단방향 파일 전송 예상치는 .32 초입니다. 이는 모든 컴퓨터에서 정렬 된 결과가 약 32 초 내에 반환됨을 의미합니다 (컴퓨터 99는 시작 후 30 초까지 파일을 얻지 못했습니다). 거기에서 가장 낮은 499,999,998 개의 숫자를 버리고 다음 2를 더하고 2로 나누는 데 시간이 오래 걸리지 않습니다.
이것은 사람들을 놀라게 할 수 있지만 숫자가 32 비트 (또는 더 작은) 안에 들어갈 정도로 작은 정수라면 버킷 정렬을하십시오! 32 비트 int 수에 제한없이 16GB 램만 필요하며 O (n)에서 실행되며, 이는 분산 시스템보다 성능이 뛰어나야합니다 (예 : 10 억).
정렬 된 목록이 있으면 중간 값을 선택하는 것이 쉽지 않습니다. 실제로 정렬 된 목록을 구성 할 필요는 없지만 버킷을 보는 것만으로도 목록을 작성해야합니다.
간단한 구현은 아래와 같습니다. 16 비트 정수에만 작동하지만 32 비트로의 확장은 쉬워야합니다.
#include <stdio.h>
#include <string.h>
int main()
{
unsigned short buckets[65536];
int input, n=0, count=0, i;
// calculate buckets
memset(buckets, 0, sizeof(buckets));
while (scanf("%d", &input) != EOF)
{
buckets[input & 0xffff]++;
n++;
}
// find median
while (count <= n/2)
{
count += buckets[i++];
}
printf("median: %d\n", i-1);
return 0;
}
10 억 (10 9 ) 숫자 의 텍스트 파일을 사용하여 다음 과 time같이 실행
time ./median < billion
내 컴퓨터에서 1m49.293s의 실행 시간을 얻습니다. 대부분의 실행 시간은 아마도 디스크 IO 일 것입니다.
이상하게도, 충분한 컴퓨터가 있다면 O(n)중간 값 찾기 알고리즘을 사용하는 것보다 정렬하는 것이 좋습니다 . (그러나 코어가 매우 느리게 진행되지 않는 한 하나만 사용하고 O(n)1e9 숫자에 대해서만 중간 값 찾기 알고리즘을 사용합니다 .하지만 1e12가 있으면 실용적이지 않을 수 있습니다.)
어쨌든, 우리가이 문제를 처리하기 위해 log n 코어 이상을 가지고 있다고 가정 해 봅시다. 우리는 전력 소비에 신경 쓰지 않고 응답을 빨리 얻습니다. 또한 메모리에 이미로드 된 모든 데이터가있는 SMP 머신이라고 가정하겠습니다. 예를 들어 Sun의 32 코어 시스템은이 유형입니다.
한 스레드는 목록을 맹목적으로 같은 크기의 조각으로 자르고 다른 M 스레드는 정렬하도록 지시합니다. 그 스레드는 (n/M) log (n/M)시간에 부지런히 그렇게 합니다. 그런 다음 중앙값뿐만 아니라 25 및 75 백분위 수도 반환합니다 (약간의 다른 숫자를 선택하면 최악의 최악의 경우가 더 좋습니다). 이제 4M 범위의 데이터가 있습니다. 그런 다음이 범위를 정렬하고 숫자 보다 작거나 포함 된 모든 범위를 버리면 데이터의 절반 을 버릴 수있는 숫자를 찾을 때까지 목록을 통해 위쪽으로 작업합니다 . 그것은 중앙값의 하한입니다. 상한에 대해서도 동일하게 수행하십시오. M log M시간 이 걸리고 모든 코어가 기다려야하므로 실제로 낭비됩니다.M^2 log M잠재적 인 시간. 이제 단일 스레드가 다른 스레드에게 범위를 벗어나 모든 데이터를 던져 (각 패스마다 약 절반을 버려야 함) 반복하도록 지시합니다. 데이터가 이미 정렬되어 있기 때문에 사소한 빠른 작업입니다. log(n/M)나머지 데이터를 가져 O(n)와서 표준 중앙값 파인더를 사용하는 것이 더 빠르기 전에이 작업을 여러 번 반복하지 않아도됩니다 .
따라서 총 복잡성은 다음과 같습니다 O((n/M) log (n/M) + M^2 log M log (n/M)). 따라서 이것은 and의 O(n)경우 하나의 코어에서 중간 정렬 보다 빠르며 , 이는 앞에서 설명한 시나리오에 해당됩니다.M >> log(n/M)M^3 log M < n
나는 이것이 비효율적이라고 생각 하면 정말 나쁜 생각 이라고 생각 하지만 더 빠릅니다.
한 대의 컴퓨터로 문제를 해결하기에 충분합니다.
그러나 100 대의 컴퓨터가 있다고 가정 해 봅시다. 당신이해야 할 유일한 복잡한 일은 목록을 정렬하는 것입니다. 그것을 100 개의 부분으로 나누고, 각 컴퓨터에 하나의 부분을 보내고, 그것들을 분류하고, 그 후 부분을 병합하십시오.
그런 다음 정렬 된 목록의 중간에서 번호를 가져옵니다 (예 : 색인 5 000 000 000).
이 방법은 투표 알고리즘 (n log n)
-주문 통계 분산 선택 알고리즘-O (n) 보다 빠르게 수행 할 수 있습니다
. 정렬되지 않은 배열에서 k 번째 숫자를 찾는 원래 문제로 문제를 단순화합니다.
-카운팅 정렬 히스토그램 O (n)
숫자 범위에 대한 몇 가지 속성을 가정해야합니다. 범위가 메모리에 맞을 수 있습니까? -외부 병합 정렬-O (n log n)-위에서 설명한
기본적으로 첫 번째 패스에서 숫자를 정렬 한 다음 두 번째 패스에서 중앙값을 찾습니다.
-숫자 분포에 대해 알려진 것이 있으면 다른 알고리즘을 생성 할 수 있습니다.
자세한 내용 및 구현은 http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html을 참조하십시오.
데이터에 따라 다릅니다. 최악의 시나리오는 균일하게 분포 된 숫자라는 것입니다.
이 경우 다음 예와 같이 O (N) 시간의 중앙값을 찾을 수 있습니다.
숫자가 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3이라고 가정합니다 (범위는 1-10). .
우리는 3 개의 버킷을 만듭니다 : 1-3, 4-7, 8-10. 상단과 하단의 크기는 동일합니다.
우리는 양동이에 숫자를 채우고, 각각 얼마나 많은 숫자를 세는지, 최대 및 최소
- 낮음 (5) : 2,1,1,3,3, 최소 1, 최대 3
- 중간 (10) : 7,5,6,4,4,6,4,7,4,4, 최소 4, 최대 7
- 높음 (5) : 10, 10, 8, 9, 9, 최소 8, 최대 10
평균은 중간 양동이에 빠지고 나머지는 무시합니다
3 개의 버킷 (4, 5-6, 7)을 만듭니다. 낮음은 5로 시작하고 최대 3은 3으로, 최소 8은 5로 계산합니다.
각 숫자에 대해 우리는 최대 및 최소 버킷 수, 최대 및 최소 수를 계산하고 중간 버킷을 유지합니다.
- 오래된 낮은 (5)
- 낮음 (5) : 4, 4, 4, 4, 4, 최대 4
- 중간 (3) : 5,6,6
- 높음 (2) : 7, 7, 7 분
- 올드 하이 (5)
이제 중앙값을 직접 계산할 수 있습니다.
old low low middle high old high
x x x x x 4 4 4 4 4 4 5 6 6 7 7 x x x x x
중앙값은 4.5입니다.
분포에 대해 조금 알고 있다고 가정하면 속도를 최적화하기 위해 범위를 정의하는 방법을 미세 조정할 수 있습니다. 어쨌든 1 + 1/3 + 1/9 ... = 1.5이기 때문에 성능은 O (N)과 함께 가야합니다.
에지 사례로 인해 최소값과 최대 값이 필요합니다 (예 : 중간 값이 이전 최대 값과 다음 요소 사이의 평균 인 경우).
이러한 모든 작업을 병렬화 할 수 있으며 각 컴퓨터에 1/100의 데이터를 제공하고 각 노드에서 3 개의 버킷을 계산 한 다음 유지하는 버킷을 배포 할 수 있습니다. 각 번호가 평균 1.5 번 전달되므로 네트워크를 효율적으로 다시 사용할 수 있습니다 (O (N)). 노드간에 최소 숫자 만 전달하면 (예 : 노드 1에 100 개의 숫자가 있고 노드 2에 150 개의 숫자가있는 경우 노드 2가 노드 1에 25 개의 숫자를 줄 수 있음) 이길 수도 있습니다.
분포에 대해 더 많이 알지 못한다면 실제로 요소를 적어도 한 번 계산해야하기 때문에 여기서 O (N)보다 더 잘 할 수 있을지 의심됩니다.
더 쉬운 방법은 가중치를 부여하는 것입니다.
- 컴퓨터간에 큰 세트를 분할
- 각 세트를 정렬
- 작은 세트를 반복하고 반복되는 요소의 가중치를 계산합니다.
- 각 2 개 세트를 1 개 (각각 이미 정렬되어 있음) 업데이트 가중치로 병합
- 하나의 세트 만 얻을 때까지 세트 병합
- OneBillion / 2에 도달 할 때까지이 누적 누적 가중치를 반복하십시오.
10 ^ 9, 10 ^ 7을 각 컴퓨터에 각각 80MB ~ 80MB로 나눕니다. 각 컴퓨터는 번호를 정렬합니다. 그런 다음 컴퓨터 1은 컴퓨터 2, 컴퓨터 3 및 4 등의 숫자와 자체 숫자를 병합 정렬합니다. 그런 다음 컴퓨터 1은 숫자의 절반을 2, 3-4 등으로 다시 씁니다. 그런 다음 1 병합은 컴퓨터에서 숫자를 정렬합니다. 1,2,3,4는 다시 쓴다. 등등. 컴퓨터의 RAM 크기에 따라 각 단계에서 개별 컴퓨터에 모든 숫자를 다시 쓰지 않아도 될 수 있습니다. 컴퓨터 1의 숫자를 여러 단계 동안 누적 할 수는 있지만 수학을 수행 할 수 있습니다.
오, 마침내 500000000th와 500000001st의 평균을 얻습니다 (그러나 충분한 00이 있는지 확인하십시오.)
편집 : @Roman-글쎄도 믿을 수 없다면 사실의 제안의 진실이나 허위를 밝히는 데 아무런 의미가 없습니다. 내가 말하고자하는 것은 때로 무차별 대결이 때로는 똑똑하게이기는 것입니다. 내가 구현할 수 있다고 확신하는 알고리즘을 고안하는 데 약 15 초가 걸렸으며 작동 할 것이며 광범위한 입력 및 수의 컴퓨터에 적용 가능하며 컴퓨터의 특성에 맞게 조정할 수 있습니다. 네트워킹 준비. 더 복잡한 알고리즘을 고안하는 데 15 분이 걸리면 솔루션을 코딩하고 실행하는 데 14m45s 이점이 있습니다.
그러나 나는 이것이 모든 주장이라고 자유롭게 인정하며, 아무것도 측정하지 않았습니다.
이는 노드에서 로그 파일 등으로 정렬되지 않은 데이터를 사용하여 다음과 같은 방식으로 노드에서 수행 할 수 있습니다.
1 개의 상위 노드와 99 개의 하위 노드가 있습니다. 자식 노드에는 두 개의 API 호출이 있습니다.
- stats () : 최소, 최대 및 개수를 반환
- compare (median_guess) : 개수 일치 값을 반환합니다. 값보다 작고 값보다 큽니다.
부모 노드는 모든 자식 노드에서 stats ()를 호출하여 모든 노드의 최소값과 최대 값을 나타냅니다.
이진 검색은 이제 다음과 같은 방식으로 수행 될 수 있습니다.
- 최소 및 최대 반올림 양분-중간 값 '추측'
- 보다 큼 개수가보다 작 으면 최소값을 추측으로 설정하십시오.
- 보다 큼 개수가보다 작음 개수보다 작 으면 최대 값을 추측 값으로 설정하십시오.
- 최소값과 최대 값이 같을 때 카운트가 홀수 인 경우
- 최대 <= 최소 + guess.match_count 일 때 카운트가 완료되면 다음과 같은 방식으로 정렬되지 않은 데이터 (로그 파일 등)를 사용하여 노드에서 수행 할 수 있습니다.
1 개의 상위 노드와 99 개의 하위 노드가 있습니다. 자식 노드에는 두 개의 API 호출이 있습니다.
- stats () : 최소, 최대 및 개수를 반환
- compare (median_guess) : 개수 일치 값을 반환합니다. 값보다 작고 값보다 큽니다.
부모 노드는 모든 자식 노드에서 stats ()를 호출하여 모든 노드의 최소값과 최대 값을 나타냅니다.
이진 검색은 이제 다음과 같은 방식으로 수행 될 수 있습니다.
- 최소 및 최대 반올림 양분-중간 값 '추측'
- 보다 큼 개수가보다 작 으면 최소값을 추측으로 설정하십시오.
- 보다 큼 개수가보다 작음 개수보다 작 으면 최대 값을 추측 값으로 설정하십시오.
- 최소값과 최대 값이 같을 때 카운트가 홀수 인 경우
- 최대 <= 최소 + 추측 일 때 카운트가 완료된 경우
stats () 및 compare ()를 O (N / Mlogn / M) 정렬로 사전 계산할 수있는 경우, 사전에 대한 메모리 복잡도 O (N)를 사용하여 O (N / M) 사전 계산 계산. 그런 다음 일정한 시간에 compare ()를 수행 할 수 있으므로 모든 사전 계산을 포함하여 O (N / MlogN / M) + O (logN)
내가 실수했다면 알려주세요!
How about this:- each node can take 1Billion/100 numbers. At each node the elements can be sorted and median can be found. Find the median of medians. we can, by aggregating the counts of numbers less than median-of-median on all nodes find out x%:y% split which the median-of-medians makes. Now ask all nodes to delete elements less than the median of medians( taking example of 30%:70% split).30% numbers are deleted. 70% of 1Billion is 700million. Now all nodes which deleted less than 3million nodes can send those extra nodes back to a main computer. The main computer redistributes in such a way that now all nodes will have almost equal number of nodes(7million). Now that the problem is reduced to 700million numbers.... goes on until we have a smaller set which can be computed on one comp.
Let's first work out how to find a median of n numbers on a single machine: I am basically using partitioning strategy.
Problem :selection(n,n/2) : Find n/2 th number from least number.
You pick say middle element k and partition data into 2 sub arrays. the 1st contains all elements < k and 2nd contains all elements >= k.
if sizeof(1st sub-array) >= n/2, you know that this sub-array contains the median. You can then throw-off the 2nd sub-array. Solve this problem selection(sizeof 1st sub-array,n/2).
In else case, throw off this 1st subarray and solve selection(2nd subarray , n/2 - sizeof(1st subarray))
Do it recursively.
time complexity is O(n) expected time.
Now if we have many machines, in each iteration, we have to process an array to split, we distribute the array into diff machines. Each machine processes their chunk of array and sends back the summary to hub controlling machine i.e. size of 1st subarray and size of 2nd subarray. The hub machines adds up summaries and decide which subarray (1st or 2nd) to process further and 2nd parameter of selection and sends it back to each machine. and so on.
This algorithm can be implemented very neatly using map reduce?
How does it look?
I think Steve Jessop's answer will be the fastest.
If the network data transfer size is the bottleneck, here is another approach.
Divide the numbers into 100 computers (10 MB each).
Loop until we have one element in each list
Find the meadian in each of them with quickselect which is O(N) and we are processing in parallel. The lists will be partitioned at the end wrt median.
Send the medians to a central computer and find the median of medians. Then send the median back to each computer.
For each computer, if the overall median that we just computed is smaller than its median, continue in the lower part of the list (it is already partitioned), and if larger in the upper part.
When we have one number in each list, send them to the central computer and find and return the median.
I would do it like this:
in the beginning all 100 work to find the highest and the lowest number; each of the computer has his part of the database/file which it queries;
when the highest and lowest numbers are found, one computer reads the data, and distributes each number, evenly, to the rest of the 99; the numbers are distributed by equal intervals; (one may take from -100 million to 0, another - from 0 to 100 million, etc);
While receiving numbers, each of the 99 of the computers already sorts them;
Then, it's easy to find the median... See how many numbers has each computer, add all of them (the sum of how many numbers there are, not the numbers themselves), divide by 2; calculate in which computer is the number, and at which index;
:) voilla
P.S. Seems there's a lot of confusion here; the MEDIAN - is the NUMBER IN THE MIDDLE OF A SORTED LIST OF NUMBERS!
You can use the tournament tree method for finding the median. We can create a tree with 1000 leave nodes such that each leaf node is an array. We then conduct n/2 tournaments between the different arrays.The value on the root after the n/2 tournaments is the result.
http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
If the numbers are not distinct, and only belong to a certain range, that is they are repeated, then a simple solution that comes to my mind is to distribute the numbers among 99 machines equally, and keep one machine as the master. Now every machine iterates over its given numbers, and stores the count of each number in a hash set. Each time the number gets repeated in the set of numbers allotted to that particular computer, it updates its count in the hash set.
All the machines then return their hash set to the master machine. The master machine combines the hash sets, summing the count of the same key found in a hash set. For example machine#1's hash set had an entry of ("1",7), and machine#2's hash set had an entry of ("1",9), so the master machine when combing the hash sets makes an entry of ("1", 16), and so on.
Once the hash sets have been merged, then just sort the keys, and now you can easily find the (n/2)th item and the (n+2/2)th item, from the sorted hash set.
This method won't be beneficial if the billion numbers are distinct.
Well, suppose you know that the number of distinct integers is (say) 4 billion, then you can bucket them into 64k buckets and get a distributed count for each bucket from each machine in the cluster(100 computers). Combine all these counts. Now, find the bucket which has the median, and this time only ask for buckets for the 64k elements that would lie in your target bucket. This requires O(1) (specifically 2) queries over your "cluster". :D
My penny worth, after all that has already been brought up by others:
Finding the median on a single machine is O(N): https://en.wikipedia.org/wiki/Selection_algorithm.
Sending N numbers to 100 machines is also O(N). So, in order to make using 100 machines interesting, either the communication must be relatively fast, or N is so large that a single machine cannot handle it while N/100 is doable, or we just want to consider the mathematical problem without bothering about datacommunication.
To cut things short I'll assume therefore that, within reasonable limits, we can send/distribute the numbers without affecting the efficiency analysis.
Consider then the following approach, where one machine is assigned to be the "master" for some general processing. This will be comparatively fast, so the "master" also participates in the common tasks that each machine performs.
- Each machine receives N/100 of the numbers, computes its own median and sends that information to the master.
- The master compiles a sorted list of all distinct medians and sends that back to each machine, defining an ordered sequence of buckets (on each machine the same), one for each median value (a single-value bucket) and one for each interval between adjacent medians. Of course there are also the lower-end and higher-end buckets for values below the lowest median and above the hightest.
- Each machine computes how many numbers fall in each bucket and communicates that information back to the master.
- The master determines which bucket contains the median, how many lower values (in total) fall below that bucket, and how many above.
- If the selected bucket is a single-value bucket (one of the medians) orelse the selected bucket contains only 1 (N odd) or 2 (N even) values we're done. Otherwise we repeat the steps above with the following (obvious) modifications:
- Only the numbers from the selected bucket are (re)distributed from the master to the 100 machines, and moreover
- We're not going to compute (on each machine) the median, but the k-th value, where we take into account how many higher numbers have been discarded from the total, and how many lower numbers. Conceptually each machine has also its share of the discarded low/high numbers and takes that into account when computing the new median in the set that (conceptually) includes (its share of) the discarded numbers.
Time-complexity:
- A little thinking will convince you that on each step the total number of values to analyse is reduced by a factor at least two (2 would be a rather sick case; you may expect a significantly better reduction). From this we get:
- Assuming that finding the median (or k-th value), which is O(N), takes c*N time where the prefactor c does not vary too wildly with N so that we can take it as a constant for the moment, we'll get our final result in at most 2*c*N/100 time. Using 100 machines gives us, therefore, a speedup factor of 100/2 (at least).
- As remarked initially: the time involved in communicating the numbers between the machines may make it more attractive to simply do everything on one machine. However, IF we go for the distributed approach, the total count of numbers to be communicated in all steps together will not exceed 2*N (N for the first time, <=N/2 the second time, <= half of that the third, and so on).
Divide the 1 billion numbers into 100 machines. Each machine will have 10^7 numbers.
For each incoming number to a machine, store the number in a frequency map, number -> count. Also store the min number in each machine.
Find median in each machine: starting from min number in each machine, sum the counts until median index is reached. The median in each machine, will be the approx. lesser and greater than 5*10^6 numbers.
Find median of all medians, which will be lesser and greater than approx. 50*10^7 numbers, which is the median of 1 billion numbers.
Now some optimization of 2nd step: Instead of storing in a frequency map, store the counts in a variable bit array. For example: Lets say starting from min number in a machine, these are frequency counts:
[min number] - 8 count
[min+1 number] - 7 count
[min+2 number] - 5 count
The above can be stored in bit array as:
[min number] - 10000000
[min+1 number] - 1000000
[min+2 number] - 10000
Note that altogether it will cost about 10^7 bits for each machine, since each machine only handles 10^7 numbers. 10^7bits = 1.25*10^6 bytes, which is 1.25MB
So with the above approach each machine will need 1.25MB of space to compute local median. And median of medians can be computed from those 100 local medians, resulting in median of 1 billion numbers.
I suggest a method to calculate approximately the Median. :) If these one billion numbers are in a randomly order, I think I can pick 1/100 or 1/10 of one billion number randomly, sort them with 100 machine, then pick the median of them. Or let's split billion numbers in 100 parts, let each machine pick 1/10 of each part randomly, calculate the median of them. After that we have 100 numbers and we can calculate the median of the 100 number easier. Just a suggestion, I'm not sure if it's mathematically correct. But I think you can show the result to a not-so-good-at-math manager.
Steve Jessop's answer is wrong:
consider the following four groups:
{2, 4, 6, 8, 10}
{21, 21, 24, 26, 28}
{12, 14, 30, 32, 34}
{16, 18, 36, 38, 40}
The median is 21, which is contained in the second group.
The median of the four groups are 6, 24, 30, 36, The total median is 27.
So after the first loop, the four groups will become:
{6, 8, 10}
{24, 26, 28}
{12, 14, 30}
{16, 18, 36}
The 21 is already wrongly discarded.
This algorithm only support the case when there are two groups.
참고URL : https://stackoverflow.com/questions/2571358/calculate-the-median-of-a-billion-numbers
'Programming' 카테고리의 다른 글
| 앰퍼샌드로 PHP 기능을 시작한다는 것은 무엇을 의미합니까? (0) | 2020.07.10 |
|---|---|
| MyAssembly.XmlSerializers.dll은 (는) 무엇 이죠? (0) | 2020.07.10 |
| 스칼라에서 '20 초 '는 어떻게 작동합니까? (0) | 2020.07.10 |
| 마진을 0으로 맞추지 못하는 이유는 무엇입니까? (0) | 2020.07.07 |
| GitHub의 이슈에서 기존 브랜치를 어떻게 참조합니까? (0) | 2020.07.07 |