[algorithm] 10 억 숫자의 중앙값 계산

아, 내 뇌는 이제 막 시작 됐습니다. 저는 현명한 제안을했습니다. 인터뷰를 한 경우 아마도 너무 늦었지만 신경 쓰지 마십시오.

기계 1은 “제어 기계”라고하며, 논쟁의 여지가 있기 때문에 모든 데이터로 시작하여 같은 소포로 다른 99 대의 기계로 보내거나 데이터가 기계간에 균등하게 분배되기 시작합니다. 데이터의 1/99를 서로에게 보냅니다. 파티션이 같을 필요는 없으며 닫기 만하면됩니다.

서로 다른 컴퓨터는 데이터를 정렬하며 더 낮은 값을 먼저 찾는 것을 선호합니다. 예를 들어, 빠른 정렬은 항상 파티션의 아래쪽을 먼저 정렬합니다 [*]. 데이터는 가능한 한 빨리 순서대로 제어 시스템에 다시 기록합니다 (정렬을 계속하기 위해 비동기 IO 사용, 아마도 Nagle on : 비트 테스트).

제어 시스템은 도착한 데이터에 대해 99-way 병합을 수행하지만, 표시된 값의 수만 유지하면서 병합 된 데이터를 버립니다. 중앙값을 1/2 십억 및 1/2 십억에 1을 더한 평균으로 계산합니다.

이것은 “무리가 가장 느린”문제로 어려움을 겪고 있습니다. 알고리즘은 중간 값보다 작은 모든 값이 정렬 기계에 의해 전송 될 때까지 완료 될 수 없습니다. 그러한 가치 중 하나가 데이터 소포 내에서 상당히 높을 가능성은 합리적입니다. 따라서 데이터의 초기 파티셔닝이 완료되면 예상 실행 시간은 데이터의 1/99를 정렬하여 제어 컴퓨터로 다시 보내는 시간과 컨트롤이 데이터의 1/2을 읽는 시간의 조합입니다. . “조합”은 최대 시간과 그 시간의 합계 사이에있을 수 있으며 아마도 최대에 가깝습니다.

내 본능은 네트워크를 통해 데이터를 전송하는 것보다 데이터를 정렬하는 것보다 빠르기 때문에 (중앙값을 선택하는 것만 제외하고) 상당히 빠른 네트워크 여야한다는 것입니다. 예를 들어 데이터가 포함 된 RAM에 동등한 액세스 권한을 가진 100 개의 코어가있는 경우 네트워크가 즉각적인 것으로 추정 될 수있는 경우 더 나은 전망이 될 수 있습니다.

네트워크 I / O가 한계가 있기 때문에 최소한 데이터가 제어 시스템으로 되돌아 오는 경우 약간의 트릭이있을 수 있습니다. 예를 들어, “1,2,3, .. 100″을 보내는 대신 정렬 시스템에서 “100보다 작은 100 개 값”을 의미하는 메시지를 보낼 수 있습니다. 그런 다음 제어 시스템은 수정 된 병합을 수행 할 수 있습니다. 여기서 병합 된 값 중 가장 작은 값 중 가장 작은 값을 찾은 다음 모든 정렬 시스템에 해당 값을 알려주므로 (a) 제어 시스템에 많은 값이 해당 값 아래로 “계산”되고 (b) 해당 지점에서 정렬 된 데이터 전송을 재개합니다.

보다 일반적으로, 컨트롤 머신이 99 개의 정렬 머신으로 플레이 할 수있는 영리한 도전-응답 추측 게임이있을 것입니다.

그러나 이것은 기계 사이의 왕복 여행과 관련이 있습니다. 단순한 첫 번째 버전은 피합니다. 나는 그들의 상대적인 성과를 맹목적으로 추정하는 방법을 정말로 모른다. 그리고 절충은 복잡하기 때문에, 이것이 실제 문제라고 가정하면, 내가 생각할 것보다 훨씬 더 나은 해결책이 있다고 생각한다.

[*] 사용 가능한 스택 허용-O (N) 추가 공간이없는 경우 먼저 수행 할 부분의 선택이 제한됩니다. 그러나 여분의 공간이 충분하면 선택을 할 수 있고 공간이 충분하지 않으면 처음 몇 개의 파티션에 대해 작은 부분을 먼저 수행하여 모서리를 자르는 데 필요한 것을 사용할 수 있습니다.

답변

sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"

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

#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;
}

time ./median < billion