Hitung median angka satu miliar

127

Jika Anda memiliki satu miliar angka dan seratus komputer, apa cara terbaik untuk menemukan median angka-angka ini?

Salah satu solusi yang saya miliki adalah:

  • Pisahkan set secara merata di antara komputer.
  • Sortir mereka.
  • Temukan median untuk setiap set.
  • Sortir set pada median.
  • Gabungkan dua set sekaligus dari median terendah ke tertinggi.

Jika kita telah m1 < m2 < m3 ...terlebih dahulu bergabung Set1dan Set2dan dalam himpunan yang dihasilkan kita dapat membuang semua angka lebih rendah dari median Set12(digabung). Jadi pada setiap titik waktu kita memiliki set ukuran yang sama. Omong-omong, ini tidak dapat dilakukan secara paralel. Ada ide?

anony
sumber
3
@ John Boker: sebenarnya masalahnya terdiri dari dua sub-masalah: 1) urutkan daftar dan 2) dapatkan elemen dengan indeks 5'000'000'000. Saya hampir tidak percaya bahwa angka diurutkan.
Roman
3
@ Roman: masalahnya tidak harus terdiri dari dua submasalah yang Anda jelaskan, misalnya pemilihan cepat. Tapi pemilihan cepat tidak paralel, setidaknya tidak sepele. Dan tentu saja Anda benar bahwa jika angka-angkanya sudah disortir, itu pertanyaan yang tidak ada gunanya.
Steve Jessop
5
@ fmsf: Saya rasa negara berbahasa Inggris tidak menggunakan miliaran panjang dalam bahasa Inggris untuk tujuan resmi apa pun. Sebagai contoh di sini di Inggris, kami berhenti menggunakannya pada tahun 1974. Saya akan menganggap penggunaan "miliar" berarti satu juta juta, dalam bahasa Inggris menjadi pertanyaan tipuan tipuan, bukan "miliar nyata" sama sekali. Tentu saja dalam bahasa Prancis itu akan menjadi masalah yang sama sekali berbeda, tetapi pertanyaannya bukan dalam bahasa Prancis.
Steve Jessop
5
Anda tidak perlu menyortir! en.wikipedia.org/wiki/…
glebm
2
Angka 1 miliar hanya beberapa gigabyte data, Anda tidak perlu banyak PC atau algoritma kompleks untuk menyelesaikan tugas ini. Jangan terlalu rumit.
user626528

Jawaban:

54

Ah, otakku baru saja mulai bergerak, aku punya saran yang masuk akal sekarang. Mungkin terlambat jika ini adalah wawancara, tetapi tidak apa-apa:

Mesin 1 harus disebut "mesin kontrol", dan demi argumen apakah itu dimulai dengan semua data, dan mengirimkannya dalam paket yang sama ke 99 mesin lainnya, atau jika data mulai terdistribusi secara merata di antara mesin, dan itu mengirimkan 1/99 datanya ke masing-masing. Partisi tidak harus sama, cukup tutup.

Masing-masing mesin memilah datanya, dan melakukannya dengan cara yang lebih dulu menemukan nilai yang lebih rendah. Jadi misalnya quicksort, selalu mengurutkan bagian bawah partisi terlebih dahulu [*]. Ini menulis data kembali ke mesin kontrol dalam urutan yang meningkat sesegera mungkin (menggunakan asinkron IO untuk melanjutkan penyortiran, dan mungkin dengan Nagle pada: bereksperimen sedikit).

Mesin kontrol melakukan penggabungan 99-arah pada data saat diterima, tetapi membuang data yang digabungkan, hanya menjaga jumlah nilai yang dilihatnya. Ini menghitung median sebagai nilai rata-rata dari 1/2 milyar dan 1/2 milyar plus.

Ini menderita masalah "paling lambat dalam kawanan". Algoritma tidak dapat menyelesaikan sampai setiap nilai kurang dari median telah dikirim oleh mesin sortasi. Ada kemungkinan yang masuk akal bahwa satu nilai semacam itu akan cukup tinggi di dalam paket datanya. Jadi begitu partisi awal data selesai, perkiraan waktu berjalan adalah kombinasi waktu untuk menyortir 1/99 data dan mengirimkannya kembali ke komputer kontrol, dan waktu untuk kontrol membaca 1/2 data . "Kombinasi" ada di suatu tempat antara maksimum dan jumlah dari waktu-waktu itu, mungkin mendekati maks.

Insting saya adalah bahwa untuk mengirim data melalui jaringan menjadi lebih cepat daripada menyortirnya (apalagi hanya memilih median) itu perlu jaringan yang sangat cepat. Mungkin prospek yang lebih baik jika jaringan dapat dianggap instan, misalnya jika Anda memiliki 100 core dengan akses yang sama ke RAM yang berisi data.

Karena jaringan I / O cenderung terikat, mungkin ada beberapa trik yang dapat Anda mainkan, setidaknya untuk data yang kembali ke mesin kontrol. Misalnya, alih-alih mengirim "1,2,3, .. 100", mungkin mesin sortir dapat mengirim pesan yang berarti "100 nilai kurang dari 101". Mesin kontrol kemudian dapat melakukan penggabungan yang dimodifikasi, di mana ia menemukan paling sedikit dari semua nilai-nilai top-of-a-range, kemudian memberitahu semua mesin sortir apa itu, sehingga mereka dapat (a) memberi tahu mesin kontrol bagaimana banyak nilai untuk "dihitung" di bawah nilai itu, dan (b) melanjutkan pengiriman data yang diurutkan dari titik itu.

Secara umum, mungkin ada permainan tebak tantangan-respons yang cerdas yang dapat dimainkan oleh mesin kontrol dengan 99 mesin sortir.

Ini melibatkan bolak-balik di antara mesin, yang dihindari versi pertama saya yang lebih sederhana. Saya tidak benar-benar tahu bagaimana memperkirakan kinerja relatif mereka, dan karena pertukaran itu rumit, saya membayangkan ada banyak solusi yang lebih baik di luar sana daripada apa pun yang akan saya pikirkan sendiri, dengan asumsi ini adalah masalah nyata.

[*] tumpukan yang tersedia memungkinkan - pilihan Anda untuk melakukan bagian mana yang dibatasi terlebih dahulu jika Anda tidak memiliki ruang ekstra O (N). Tetapi jika Anda memiliki cukup ruang ekstra, Anda dapat memilih, dan jika Anda tidak memiliki cukup ruang, Anda setidaknya dapat menggunakan apa yang Anda lakukan untuk memotong beberapa sudut, dengan melakukan bagian kecil terlebih dahulu untuk beberapa partisi pertama.

Steve Jessop
sumber
Harap perbaiki saya jika saya salah, mengapa Anda melakukan penggabungan 99-arah pada data karena hanya akan dibuang nanti. Alih-alih, apakah cukup untuk tetap menghitung angka begitu sampai?
sreeprasad
4
@SREEPRASADGOVINDANKUTTY: langkah yang berulang adalah membuang nilai terkecil dari semua 99 kandidat, dan menambah hitungan. Tidak ada gunanya sama sekali untuk hanya menghitung semua nilai yang masuk tanpa langkah penggabungan 99 arah ini. Jika Anda tidak membandingkannya saat masuk, Anda tidak tahu bahwa nilai yang Anda buang berada di bawah median.
Steve Jessop
Tetapi tidakkah ada kemungkinan kecil bahwa partisi-partisi ini hanya berisi angka-angka yang lebih tinggi daripada median dan karenanya setiap partisi yang lebih rendah yang dikembalikan akan lebih tinggi daripada median, tetapi karena kontrol tidak tahu ini akan membuangnya sebagai lebih rendah daripada median dan gagal ...?
Gullydwarf
@Gullydwarf: gabungan multi-arah hanya membuang nilai terkecil dari 99 yang ada di tangannya, masing-masing merupakan nilai sisa terkecil dari salah satu mesin lainnya. Jika salah satu partisi sepenuhnya lebih besar dari median, maka itu tidak akan menjadi yang paling rendah dari 99 nilai sampai setelah median melewati (pada titik mana kita selesai). Jadi tidak akan dibuang.
Steve Jessop
52
sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"
DrPizza
sumber
2
LOL. Apakah itu benar-benar berfungsi atau akankah pembunuh OOM melepaskannya sebelum selesai? (pada komputer yang masuk akal)
Isak Savo
5
Harus dilakukan. sort tahu cara melakukan sortir out-of-core, sehingga tidak kehabisan memori.
DrPizza
6
@Zagfai Saya pikir itu tidak akan terlalu lama; satu miliar angka hanya 4 GB untuk 32-bit int / float, 8 GB untuk 64-bit ints / ganda. Tampaknya tidak ada yang sangat melelahkan.
DrPizza
13
Baru saja mencoba Intel i5-4200M @ 3.1 GHz (4 core). Menurut timeperintah yang diterapkan pada seluruh pipa, butuh real=36m24s("waktu jam dinding"), user=113m15s ("waktu paralel", semua core ditambahkan). Perintah terpanjang, jauh di depan yang lain, adalah sort, bahkan jika itu berulir ke empat core saya di 100%. Konsumsi RAM sangat diterima.
Morgan Touverey Quilling
12
Kemudian jalankan di 100 komputer, sehingga Anda dapat 100 kali lebih yakin bahwa hasilnya benar :)
dos
27

Saya benci menjadi pelawan di sini, tapi saya tidak percaya penyortiran diperlukan, dan saya pikir algoritma apa pun yang melibatkan penyortiran satu miliar / 100 angka akan lambat. Mari pertimbangkan algoritma pada satu komputer.

1) Pilih 1000 nilai secara acak dari miliar, dan gunakan untuk mendapatkan ide distribusi angka, terutama rentang.

2) Alih-alih menyortir nilai, alokasikan ke ember berdasarkan distribusi yang baru saja Anda hitung. Jumlah ember dipilih agar komputer dapat menanganinya secara efisien, tetapi seharusnya sebesar kenyamanan. Rentang bucket harus sedemikian sehingga kira-kira jumlah nilai yang sama masuk dalam setiap bucket (ini tidak penting untuk algoritme, tetapi ini membantu efisiensi. 100.000 ember mungkin sesuai). Catat jumlah nilai dalam setiap ember. Ini adalah proses O (n).

3) Cari tahu ember mana yang rentang median terletak. Ini dapat dilakukan dengan hanya memeriksa jumlah total di setiap ember.

4) Temukan median aktual dengan memeriksa nilai-nilai dalam ember itu. Anda dapat menggunakan pengurutan di sini jika mau, karena Anda hanya mengurutkan sekitar 10.000 angka. Jika jumlah nilai dalam ember itu besar maka Anda dapat menggunakan algoritme ini lagi hingga Anda memiliki jumlah yang cukup kecil untuk disortir.

Pendekatan ini diparalelkan secara sepele dengan membagi nilai antara komputer. Setiap komputer melaporkan total dalam setiap ember ke komputer 'kontrol' yang melakukan langkah 3. Untuk langkah 4 setiap komputer mengirimkan nilai (diurutkan) dalam ember yang relevan ke komputer kontrol (Anda juga dapat melakukan kedua algoritma secara paralel, tapi mungkin tidak sepadan).

Total proses adalah O (n), karena kedua langkah 3 dan 4 adalah sepele, asalkan jumlah ember cukup besar.

DJClayworth
sumber
1
Saya pikir ini adalah sesuatu di antara median median dan algoritma pemilihan cepat. en.wikipedia.org/wiki/Selection_algorithm
Dimath
Pada langkah 4, ember mungkin tidak hanya berisi 10.000. Mungkin terjadi bahwa distribusi condong ke arah tengah, di mana, mungkin berisi, katakanlah, 80% dari data, yang masih sangat besar.
justhalf
Diedit untuk memperhitungkan itu.
DJClayworth
4
Performa bukan O (n) dalam algoritma ini: Anda bisa memiliki sebagian besar angka jatuh dalam ember "median", dan itu bisa berkinerja seburuk menyortir semuanya.
Sklivvz
1
@ WULF Sebuah pertanyaan yang bagus. Ini kunci algoritma, dan langkah 1 mengatasinya. Pengambilan sampel angka-angka untuk membangun distribusi adalah yang terbaik yang pernah saya lakukan.
DJClayworth
12

Satu miliar sebenarnya tugas yang cukup membosankan untuk komputer modern. Kita berbicara tentang 4 GB senilai 4 byte integer di sini ... 4 GB ... itu adalah RAM dari beberapa smartphone.

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

Output pada mesin saya:

created array after 518 ms
initialized array after 10177 ms
sorted array after 102936 ms
median = 19196

Jadi ini selesai pada mesin saya dalam waktu kurang dari dua menit (1:43 yang 0:10 menghasilkan angka acak) menggunakan inti tunggal dan bahkan melakukan pengurutan penuh. Tidak ada yang benar-benar mewah.

Ini tentunya merupakan tugas yang menarik untuk set angka yang lebih besar. Saya hanya ingin menegaskan: satu miliar adalah kacang. Jadi pikirkan dua kali sebelum Anda mulai memberikan solusi kompleks pada tugas-tugas yang sangat sederhana;)

sfussenegger
sumber
ini adalah apa yang saya katakan di jawaban saya di sini :-) stackoverflow.com/a/31819222/363437
vidstige
1
@vidstige Jujur saya tidak membacanya, tetapi Anda benar. jawaban saya tentu lebih langsung, yang tampaknya orang lebih menghargai;)
sfussenegger
Itu bukan median, median adalah (numbers[numbers.length / 2]+numbers[numbers.length / 2+1])/2jika numbers.lengthadalah genap dan numbers[numbers.length / 2]hanya jika numbers.lengthaneh.
Sklivvz
@ Klivvz benar, tetapi seharusnya tidak terlihat memengaruhi waktu yang diperlukan untuk menghitung median.
vidstige
1
@ Klivvz Anda tentu saja benar. Saya baru saja memperbarui perhitungan median. Itu tidak mengubah sisa jawabannya.
sfussenegger
10

The estimasi statistik agar seperti persentil median dan 99 dapat didistribusikan secara efisien dengan algoritma seperti t-mencerna atau Q-dicerna .

Dengan menggunakan salah satu algoritma, setiap node menghasilkan intisari, yang mewakili distribusi nilai yang disimpan secara lokal. Intisari dikumpulkan pada satu simpul tunggal, digabung (secara efektif menjumlahkan distribusi), dan median atau persentil lainnya kemudian dapat dilihat.

Pendekatan ini digunakan oleh elasticsearch dan, mungkin, BigQuery (mengikuti deskripsi fungsi QUANTILES).

Richard Poole
sumber
5

Median untuk set angka ini

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89, 97

adalah 67.

Median untuk set angka ini

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89

adalah 40.

Dengan asumsi pertanyaan adalah sekitar 1.000.000.000 bilangan bulat (x) di mana 0> = x <= 2.147.483.647 dan bahwa OP sedang mencari (elemen (499.999.999) + elemen (500.000.000)) / 2 (jika angka-angka itu diurutkan). Juga dengan asumsi bahwa semua 100 komputer semuanya sama.

menggunakan laptop dan GigE saya ...

Apa yang saya temukan adalah laptop saya dapat mengurutkan 10.000.000 Int32 dalam 1,3 detik. Jadi perkiraan kasarnya adalah bahwa semacam miliar angka akan mengambil 100 x 1,3 detik (2 menit 10 detik);).

Perkiraan transfer file satu arah dari file 40MB pada gigabit Ethernet adalah 0,32 detik. Ini berarti bahwa hasil yang diurutkan dari semua komputer akan dikembalikan dalam waktu sekitar 32 detik (komputer 99 tidak mendapatkan file-nya sampai 30 detik setelah start). Dari sana tidak perlu waktu lama untuk membuang yang terendah 499.999.998 angka, tambahkan 2 berikutnya dan bagi 2.

dbasnett
sumber
3
Turunkan komentar pemilih? Itu akan membantu saya memahami bagaimana saya bisa melakukan yang lebih baik.
dbasnett
5
Saya bukan pemilih bawah, tetapi menyortir satu miliar angka tidak akan memakan waktu 100 kali lipat dari menyortir 10 juta, karena kompleksitas terburuk dari pengurutan daftar adalah O (n log n). Penyortiran juga merupakan urutan besarnya lebih lambat ketika Anda kehabisan memori dan harus mulai menyortir pada disk.
Richard Poole
Saya pikir Anda berada di jalur yang benar; Jika tujuannya adalah jawaban tercepat yang pernah dibuat, mengurutkan beberapa mesin mungkin merupakan ide yang baik. Tetapi jika tujuannya adalah waktu rata-rata terendah, setiap mesin melakukan pencarian sendiri lebih masuk akal.
Charlie
Dengan asumsi mereka memiliki faktor yang sama (yang mungkin tidak disebabkan oleh masalah memori) kemudian a*(1e7)log(1e7) = 1.3sec=> a = 1.6e-9sec => a*(1e9)log(1e9) ~ 167sec, jadi perkiraan Anda tidak terlalu buruk.
bcorso
Estimasi Anda terlalu kasar. Pertama, beberapa algoritma pengurutan menjadi o (n ^ 2) dalam skenario kasus terburuk (misalnya quicksort yang umum digunakan). Kedua, Anda telah memilih dataset uji yang kira-kira seukuran cache L2 Anda. Ini mengacaukan hasilnya. Ketiga Anda (karena banyak penjawab lainnya) menganggap "angka" berarti "bilangan bulat". Ini bisa berarti float, double atau desimal, yang memiliki karakteristik kinerja yang sangat berbeda.
Sklivvz
5

Ini mungkin mengejutkan orang, tetapi jika bilangan bulat cukup kecil untuk muat di dalam 32-bit (atau lebih kecil) - Lakukan saja semacam ember! Hanya membutuhkan 16GB ram untuk sejumlah int 32-bit dan berjalan di O (n), yang akan mengungguli semua sistem terdistribusi untuk n masuk akal, misalnya satu miliar.

Setelah Anda memiliki daftar yang disortir, itu sepele untuk memilih median. Bahkan, Anda tidak perlu membuat daftar yang disortir, tetapi hanya melihat ember yang harus melakukannya.

Implementasi sederhana ditunjukkan di bawah ini. Hanya berfungsi untuk bilangan bulat 16-bit, tetapi ekstensi ke 32-bit seharusnya mudah.

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

Menggunakan file teks dengan satu miliar (10 9 ) angka dan berjalan dengan timeseperti itu

time ./median < billion

menghasilkan waktu berjalan pada mesin saya 1m49.293s. Sebagian besar waktu yang berjalan mungkin adalah disk IO juga.

vidstige
sumber
Ini tidak benar-benar menjawab pertanyaan dan itu bergantung pada asumsi. Misalnya, Anda bahkan tidak tahu itu bilangan bulat.
Sklivvz
Dengan cara apa itu tidak menjawab pertanyaan? Dan ya, jawaban saya menganggap angka adalah bilangan bulat. Saya telah mencoba menyatakan asumsi saya dengan jelas.
vidstige
Anda tampaknya tidak menyatakan bahwa memiliki bilangan bulat adalah asumsi, atau Anda membahas bagaimana menggunakan 100 komputer yang ditanyakan OP. Anda dapat menghitung median pada satu simpul tetapi itu bukan solusi "terbaik" kecuali Anda menunjukkan alasannya. Juga, radix sort bukan o (n) jika jumlah digit bervariasi, yang dalam hal ini tentu saja, menurut en.wikipedia.org/wiki/Radix_sort#Efficiency , ini o (n log n)
Sklivvz
Saya mulai dengan mengatakan "jika bilangan bulat cukup kecil untuk muat dalam bilangan bulat 32-bit " ... Radix sort adalah O (n) untuk ukuran kata w konstan seperti yang dijelaskan dengan sangat jelas dalam tautan yang Anda pasang. Di sini saya mengasumsikan ukuran kata konstan 32.
vidstige
1
Apa yang Anda lakukan dengan 99 komputer lain tidak relevan dalam jawaban ini. Anda bisa menumpuknya di atas satu sama lain untuk membentuk piramida atau membakarnya. Atau abaikan saja.
vidstige
3

Anehnya, saya pikir jika Anda memiliki cukup komputer, Anda lebih baik menyortir daripada menggunakan O(n)algoritma median-finding. (Kecuali jika inti Anda sangat, sangat lambat, saya hanya akan menggunakan satu dan menggunakan O(n)algoritma mencari median hanya untuk angka 1e9; namun jika Anda memiliki 1e12, itu mungkin kurang praktis.)

Bagaimanapun, anggaplah kita memiliki lebih dari satu log n core untuk mengatasi masalah ini, dan kita tidak peduli dengan konsumsi daya, hanya mendapatkan jawabannya dengan cepat. Mari kita asumsikan bahwa ini adalah mesin SMP dengan semua data yang sudah dimuat dalam memori. (Misalnya, mesin 32-core Sun dari jenis ini.)

Satu utas memotong daftar secara membabi buta menjadi potongan berukuran sama dan memberi tahu utas M lainnya untuk menyortirnya. Utas itu rajin melakukannya, (n/M) log (n/M)tepat waktu. Mereka kemudian mengembalikan tidak hanya median mereka, tetapi, katakanlah, persentil ke 25 dan 75 mereka juga (kasus terburuk yang jahat lebih baik jika Anda memilih angka yang sedikit berbeda). Sekarang Anda memiliki rentang data 4M. Anda kemudian mengurutkan rentang ini dan bekerja ke atas melalui daftar sampai Anda menemukan nomor sehingga, jika Anda membuang setiap rentang yang lebih kecil dari atau berisi nomor, Anda akan membuang separuh data Anda. Itu batas bawah Anda untuk median. Lakukan hal yang sama untuk batas atas. Ini membutuhkan M log Mwaktu, dan semua core harus menunggu, jadi itu benar-benar sia-siaM^2 log Mwaktu potensial. Sekarang Anda memiliki utas tunggal Anda memberi tahu orang lain untuk melemparkan semua data di luar rentang (Anda harus membuang sekitar setengah pada setiap pass) dan ulangi - ini adalah operasi yang sangat cepat karena data sudah diurutkan. Anda tidak perlu mengulangi ini lebih dari beberapa log(n/M)kali sebelum lebih cepat untuk hanya mengambil data yang tersisa dan menggunakan O(n)pencari median standar di atasnya.

Jadi, kompleksitas total adalah sesuatu seperti O((n/M) log (n/M) + M^2 log M log (n/M)). Dengan demikian, ini lebih cepat daripada O(n)jenis median pada satu inti jika M >> log(n/M)dan M^3 log M < n, yang berlaku untuk skenario yang telah Anda jelaskan.

Saya pikir ini adalah ide yang sangat buruk mengingat betapa tidak efisiennya, tetapi lebih cepat.

Rex Kerr
sumber
o (n / M log (n / M)) secara harfiah adalah o (n log n), karena o (n / M log (n / M)) = 1 / M o (n (log n - log M) ) = o (n log n). Anda tidak dapat benar-benar membandingkannya dengan o (n) seperti itu, karena "o" pada dasarnya berarti "sebanding dengan untuk n sangat besar dengan beberapa konstanta yang tidak ditentukan". Kecuali Anda tahu konstanta-konstanta yang tidak dapat Anda bandingkan, namun untuk N yang cukup besar konstanta tidak dominan. Untuk angka yang lebih rendah, semua taruhan mati, o (1) dapat dengan mudah lebih lambat daripada o (n!).
Sklivvz
@ Klivvz - ndan Mmerupakan variabel yang dapat menskala secara sewenang-wenang, jadi salah satunya termasuk keduanya. Secara khusus, saya mendalilkan itu M> log n, yang berarti bahwa jika Anda peduli itu n log nbukan hanya n, Anda harus peduli Mjuga.
Rex Kerr
3

Ini dapat dilakukan lebih cepat daripada algoritma yang dipilih (n log n)

- Statistik pesanan Algoritma pemilihan terdistribusi - O (n)
Sederhanakan masalah dengan masalah awal dalam menemukan nomor k dalam array yang tidak disortir.
- Menghitung pengurutan histogram O (n)
Anda harus mengasumsikan beberapa properti tentang kisaran angka - dapatkah kisaran cocok dalam memori? - Urutan gabungan eksternal - O (n log n) - dijelaskan di atas.
Anda pada dasarnya mengurutkan angka pada pass pertama, kemudian menemukan median pada yang kedua.
- Jika ada yang diketahui tentang distribusi angka, algoritma lain dapat dihasilkan.

Untuk detail dan implementasi lebih lanjut, lihat:
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

pengguna1712376
sumber
2

Satu komputer lebih dari cukup untuk menyelesaikan masalah.

Tapi mari kita asumsikan ada 100 komputer. Satu-satunya hal rumit yang harus Anda lakukan adalah mengurutkan daftar. Membagi menjadi 100 bagian, mengirim satu bagian ke setiap komputer, membiarkannya disortir di sana, dan menggabungkan bagian-bagian setelah itu.

Kemudian ambil nomor dari tengah daftar yang disortir (yaitu dengan indeks 5 000 000 000).

Roma
sumber
3
Pokoknya sekarang perwakilan saya cukup bulat :)
Roman
Penggabungan adalah yang terbaik O (n), dan Anda dapat menemukan median pada inti tunggal di O (n), jadi ini tampaknya membuat banyak pekerjaan tambahan tanpa hasil.
Rex Kerr
2

Itu tergantung pada data Anda. Skenario kasus terburuk adalah bahwa angka itu terdistribusi secara seragam.

Dalam hal ini Anda dapat menemukan median dalam waktu O (N) seperti dalam contoh ini:

Misalkan angka Anda adalah 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (kisaran 1-10) .

Kami membuat 3 ember: 1-3, 4-7, 8-10. Perhatikan bahwa atas dan bawah memiliki ukuran yang sama.

Kami mengisi ember dengan angka, menghitung berapa banyak yang jatuh masing-masing, maksimal dan minimum

  • rendah (5): 2,1,1,3,3, min 1, maks 3
  • tengah (10): 7,5,6,4,4,6,4,7,4,4, min 4, maks 7
  • tinggi (5): 10, 10, 8, 9, 9, min 8, maks 10

Berarti jatuh di ember tengah, kami mengabaikan sisanya

Kami membuat 3 ember: 4, 5-6, 7. Rendah akan mulai dengan hitungan 5 dan dengan maksimal 3 dan tinggi dengan minimal 8 dan hitungan 5.

Untuk setiap angka, kami menghitung berapa banyak yang jatuh di ember rendah dan tinggi, maks dan minimum, dan simpan ember tengah.

  • old rendah (5)
  • rendah (5): 4, 4, 4, 4, 4, maks 4
  • menengah (3): 5,6,6
  • tinggi (2): 7, 7, min 7
  • old high (5)

Sekarang kita dapat menghitung median secara langsung: kita memiliki situasi seperti ini

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

jadi mediannya adalah 4,5.

Dengan asumsi Anda tahu sedikit tentang distribusi, Anda dapat menyesuaikan cara menentukan rentang untuk mengoptimalkan kecepatan. Bagaimanapun, kinerja harus pergi dengan O (N), karena 1 + 1/3 + 1/9 ... = 1,5

Anda perlu min dan maks karena tepi kasus (mis. Jika median adalah rata-rata antara maks rendah lama dan elemen berikutnya).

Semua operasi ini dapat diparalelkan, Anda dapat memberikan 1/100 data ke setiap komputer dan menghitung 3 ember di setiap node, lalu mendistribusikan ember yang Anda simpan. Ini lagi membuat Anda menggunakan jaringan secara efisien karena setiap angka dilewatkan rata-rata 1,5 kali (jadi O (N)). Anda bahkan dapat mengalahkan itu jika Anda hanya melewatkan angka minimal di antara node (mis. Jika simpul 1 memiliki 100 angka dan simpul 2 memiliki angka 150, maka simpul 2 dapat memberikan 25 angka ke simpul 1).

Kecuali Anda tahu lebih banyak tentang distribusi, saya ragu Anda bisa melakukan lebih baik daripada O (N) di sini, karena Anda benar-benar perlu menghitung elemen setidaknya sekali.

Sklivvz
sumber
1
Bukankah ini kasus terburuk yang sebenarnya (untuk algoritme Anda) ketika semua angkanya sama? Jika saya benar, tidak satu pun dari ember Anda akan terisi terpisah dari yang di tengah, dengan semua elemen. Dengan demikian, Anda harus melintasi semua elemen setiap kali, maju secara eksponensial cepat ke tengah interval. Saya percaya itu akan menjadi O(n log n)dalam kasus itu. Apakah masuk akal ? Ngomong-ngomong, aku suka idemu
Dici
1
@Dici tidak juga: pertama Anda dapat dengan mudah memotong skenario "semua sama" karena Anda tahu min dan maks. Seperti yang saya katakan dalam jawaban, mengetahui distribusi dapat mendorong pilihan ember Anda; kedua, masih akan mengambil o(n)+o(n/3)+o(n/9)+...yang diam o(n)dan tidak o(n log n).
Sklivvz
Di sisi lain, mungkin ada skenario kasus terburuk yang berbeda, distribusi berbentuk huruf U. Saya perlu berpikir sedikit tentang itu, memformalkan kasus terburuk, tetapi mungkin bisa lebih buruk daripada o(n)dalam kasus itu, dengan partisi yang naif.
Sklivvz
Mmm ya, min dan maks akan membantu menangani kasus "semua sama" dengan mudah
Dici
2

Metode yang lebih mudah adalah memiliki angka tertimbang.

  • Pisahkan perangkat besar di antara komputer
  • Sortir setiap set
  • beralih melalui set kecil, dan hitung bobot untuk elemen berulang
  • menggabungkan masing-masing 2 set menjadi 1 (masing-masing sudah diurutkan) memperbarui bobot
  • terus gabungkan set hingga Anda hanya mendapatkan satu set
  • iterate melalui set ini akumulasi bobot sampai Anda mencapai OneBillion / 2
Ziad Nasser
sumber
1

Pisahkan 10 ^ 9 angka, 10 ^ 7 untuk setiap komputer ~ 80MB untuk masing-masing. Setiap komputer mengurutkan angkanya. Kemudian komputer 1 menggabungkan-mengurutkan angka-angka sendiri dengan yang dari komputer 2, komputer 3 dan 4, dll ... Kemudian komputer 1 menulis setengah dari angka-angka kembali ke 2, 3 hingga 4, dll. Kemudian 1 menggabungkan jenis angka-angka dari komputer 1,2,3,4, tulis kembali. Dan seterusnya. Bergantung pada ukuran RAM pada komputer yang Anda gunakan untuk tidak menulis semua angka kembali ke masing-masing komputer, Anda mungkin dapat mengakumulasikan angka pada komputer 1 untuk beberapa langkah, tetapi Anda melakukan perhitungan.

Oh, akhirnya dapatkan nilai rata-rata 500000000 dan 500000001st (tapi periksa ada cukup 00 di sana, saya belum).

EDIT: @Roman - baik jika Anda tidak percaya bahkan itu benar maka tidak ada gunanya saya mengungkapkan kebenaran atau kepalsuan proposisi. Apa yang saya maksudkan adalah bahwa kekuatan brutal terkadang mengalahkan kecerdasan dalam suatu perlombaan. Butuh waktu sekitar 15 detik untuk menyusun algoritma yang saya yakin bisa diterapkan, yang akan berfungsi, dan yang akan dapat disesuaikan dengan berbagai ukuran input dan jumlah komputer, dan dapat disesuaikan dengan karakteristik komputer dan pengaturan jaringan. Jika diperlukan, atau siapa pun, katakan 15 menit untuk menyusun algoritma yang lebih canggih, saya memiliki keunggulan 14m45 untuk menyusun solusi saya dan mulai menjalankannya.

Tapi saya dengan bebas mengakui ini semua pernyataan, saya belum mengukur apa pun.

Tanda Kinerja Tinggi
sumber
di sini kita hanya menggabungkan semua angka. Bisakah kita melakukannya dengan cara yang lebih baik menggunakan: - "kita dapat menemukan median dari dua daftar yang diurutkan dalam waktu logn. N adalah panjang setiap daftar."
anony
1
@ anony - selagi Anda menjawab pertanyaan Anda sendiri, solusi saya akan dikodekan, diuji, dan dilakukan. Saya berharap ada cara yang lebih baik, tetapi kadang-kadang memparalelkan cara sederhana membuat saya bebas untuk menggaruk-garuk kepala pada masalah yang sangat sulit.
High Performance Mark
apakah Anda benar-benar melakukannya dalam 7 menit? Aku tidak percaya itu meskipun itu benar. Saya melakukan tugas yang sama (itu adalah tugas universitas) dan butuh sekitar 2 jam untuk mengimplementasikan dan menguji semua hal remoting (saya menggunakan java RMI).
Roman
Saya mengerti apa yang Anda katakan, tetapi dengan cara yang sama, DrPizza memiliki solusi yang bahkan lebih cepat untuk dipikirkan, yaitu memilah semua data pada satu node dan mengabaikan yang lain 99. Tidak seorang pun dari kita yang tahu betapa mahalnya data transfer harus dipertimbangkan, jadi kita semua hanya memilih kompromi yang kedengarannya masuk akal. Solusi Anda mentransfer semua data beberapa kali, jadi saya agak curiga terhadapnya, tetapi tentu saja ini solusi.
Steve Jessop
'Samar-samar masuk akal' - itu cukup baik bagi saya @Steve! Terutama dalam menanggapi pertanyaan yang agak tidak masuk akal.
High Performance Mark
1

Ini bisa dilakukan pada node menggunakan data yang tidak diurutkan melintasi node (katakanlah dari file log) dengan cara berikut.

Ada 1 simpul orangtua dan 99 simpul anak. Node anak memiliki dua panggilan api:

  • stats (): mengembalikan min, maks, dan hitung
  • bandingkan (median_guess): mengembalikan nilai pencocokan hitungan, menghitung kurang dari nilai dan menghitung lebih besar dari nilai

Node induk memanggil stats () pada semua node anak, mencatat minimum dan maksimum semua node.

Pencarian biner sekarang dapat dilakukan dengan cara berikut:

  1. Membagi dua pembulatan minimum dan maksimum - ini adalah median 'tebak'
  2. Jika lebih besar dari jumlah lebih dari kurang dari jumlah, atur minimum ke tebakan
  3. Jika lebih besar dari jumlah kurang dari kurang dari jumlah, atur maksimal ke tebakan
  4. Jika hitungan ganjil, selesai bila minimum dan maksimum sama
  5. Jika hitungan bahkan selesai ketika maksimum <= minimum + guess.match_count Ini bisa dilakukan pada node menggunakan data yang tidak disortir (katakan dari file log) dengan cara berikut.

Ada 1 simpul orangtua dan 99 simpul anak. Node anak memiliki dua panggilan api:

  • stats (): mengembalikan min, maks, dan hitung
  • bandingkan (median_guess): mengembalikan nilai pencocokan hitungan, menghitung kurang dari nilai dan menghitung lebih besar dari nilai

Node induk memanggil stats () pada semua node anak, mencatat minimum dan maksimum semua node.

Pencarian biner sekarang dapat dilakukan dengan cara berikut:

  1. Membagi dua pembulatan minimum dan maksimum - ini adalah median 'tebak'
  2. Jika lebih besar dari jumlah lebih dari kurang dari jumlah, atur minimum ke tebakan
  3. Jika lebih besar dari jumlah kurang dari kurang dari jumlah, atur maksimal ke tebakan
  4. Jika hitungan ganjil, selesai bila minimum dan maksimum sama
  5. Jika hitungan bahkan selesai ketika maksimum <= minimum + guess.match_count

Jika statistik () dan bandingkan () dapat dihitung sebelumnya dengan jenis O (N / Mlogn / M), maka pra-perhitungan O (N / M) dengan kompleksitas memori O (N) untuk pra- perhitungan. Kemudian Anda dapat melakukan perbandingan () dalam waktu yang konstan, sehingga semuanya (termasuk pra-perhitungan) akan berjalan di O (N / MlogN / M) + O (logN)

Beri tahu saya jika saya melakukan kesalahan!

teambob
sumber
ya saya hanya akan melakukan pencarian biner. Akan menghemat bandwidth jaringan hanya memanggil setiap komputer beberapa kali. Juga setiap mesin dapat memiliki "poros" di tempat itu bertukar nomor kedua sisi poros untuk menghemat waktu. (pivot akan menjadi perkiraan median sebelumnya, jadi lain kali, hanya perlu melewati semua angka di satu sisi pivot)
robert king
0

Bagaimana dengan ini: - setiap node dapat mengambil 1Billion / 100 angka. Pada setiap node elemen dapat diurutkan dan median dapat ditemukan. Temukan median median. kita bisa, dengan menjumlahkan jumlah angka yang kurang dari median-of-median pada semua node mengetahui x%: y% split yang dibuat median-of-median. Sekarang minta semua node untuk menghapus elemen kurang dari median median (mengambil contoh 30%: 70% split) .30% angka dihapus. 70% dari 1 Milyar adalah 700 juta. Sekarang semua node yang menghapus kurang dari 3 juta node dapat mengirim kembali node-node tambahan itu ke komputer utama. Komputer utama mendistribusikan kembali sedemikian rupa sehingga sekarang semua node akan memiliki jumlah node yang hampir sama (7 juta). Sekarang masalahnya berkurang menjadi angka 700 juta .... terus berlanjut hingga kita memiliki set yang lebih kecil yang dapat dihitung pada satu komputer.

anony
sumber
Intinya kami selalu mengurangi masalah yang ditetapkan oleh setidaknya 30% dan kami mencapai banyak komputasi paralel melalui ini. Setiap node dimulai dengan 10 juta dan mengurangi set datanya sebesar 30% di setiap iterasi.
anony
Dalam iterasi pertama kami mencari nomor 500 juta. Dalam iterasi kedua - jika jumlah angka yang dihapus adalah 300 juta maka kita mencari nomor 200 juta dan seterusnya ...
anony
2
Ini sepertinya berada di jalur yang benar, tetapi Anda tidak menjelaskan dengan jelas bagaimana menghindari membuang median secara tidak sengaja dengan 30% / 70% split Anda. Ambil contoh tandingan berikut: anggap 29% Anda yang pertama adalah nol, dan semua blok lainnya dihitung dengan 1000, dan setiap rangkaian blok adalah satu lebih dari yang terakhir. Median persentil ke-30 akan membuang semua 29% dari data, dan hanya di bawah setengah dari 61% dari data, yaitu 29 + 30% = 59% dari data. Ups, kami baru saja membuang median yang sebenarnya! Jadi tampaknya Anda tidak bermaksud seperti itu, atau setidaknya maksud Anda lebih cerdik daripada yang saya tafsirkan.
Rex Kerr
0

Pertama-tama mari kita cari cara menemukan median n angka pada satu mesin: Saya pada dasarnya menggunakan strategi partisi.

Masalah: pemilihan (n, n / 2): Temukan nomor n / 2 dari angka terkecil.

Anda memilih mengatakan elemen tengah k dan data partisi menjadi 2 sub array. 1 berisi semua elemen <k dan 2 berisi semua elemen> = k.

jika sizeof (sub-array 1)> = n / 2, Anda tahu bahwa sub-array ini berisi median. Anda kemudian dapat membuang sub-array ke-2. Selesaikan pemilihan masalah ini (ukuran sub-array 1, n / 2) .

Dalam kasus lain, buang subarray 1 ini dan selesaikan seleksi (subarray kedua, n / 2 - sizeof (subarray 1)

Lakukan secara rekursif.

kompleksitas waktu adalah O (n) waktu yang diharapkan.

Sekarang jika kita memiliki banyak mesin, dalam setiap iterasi, kita harus memproses array untuk dibagi, kita mendistribusikan array ke mesin yang berbeda. Setiap mesin memproses sejumlah array dan mengirimkan kembali ringkasan ke mesin pengontrol hub yaitu ukuran subarray pertama dan ukuran subarray kedua. Mesin hub menambahkan ringkasan dan memutuskan subarray mana (1 atau 2) untuk memproses lebih lanjut dan parameter pemilihan 2 dan mengirimkannya kembali ke setiap mesin. dan seterusnya.

Algoritma ini dapat diimplementasikan dengan sangat rapi menggunakan peta reduksi?

Bagaimana kelihatannya?

xyz
sumber
0

Saya pikir jawaban Steve Jessop akan menjadi yang tercepat.

Jika ukuran transfer data jaringan adalah hambatan, berikut adalah pendekatan lain.

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.
Cem
sumber
Masing-masing 32 MB, maksud Anda?
Dici
Apa yang Anda maksud dengan melanjutkan di bagian bawah daftar?
Ruthvik Vaila
0

Saya akan melakukannya seperti ini:

pada awalnya semua 100 pekerjaan untuk menemukan angka tertinggi dan terendah; setiap komputer memiliki bagiannya dari database / file yang ditanyakannya;

ketika angka tertinggi dan terendah ditemukan, satu komputer membaca data, dan mendistribusikan setiap angka, secara merata, ke 99 lainnya; jumlahnya didistribusikan dengan interval yang sama; (satu dapat mengambil dari -100 juta hingga 0, yang lain - dari 0 hingga 100 juta, dll);

Saat menerima angka, masing-masing dari 99 komputer sudah mengurutkannya;

Maka, mudah untuk menemukan median ... Lihat berapa banyak angka yang memiliki masing-masing komputer, tambahkan semuanya (jumlah dari berapa angka yang ada, bukan angka itu sendiri), bagi dengan 2; menghitung di mana komputer adalah angka, dan indeks mana;

:) voilla

PS Sepertinya ada banyak kebingungan di sini; MEDIAN - adalah NOMOR DI TENGAH-TENGAH DAFTAR NOMOR!

Johny
sumber
0

Anda dapat menggunakan metode pohon turnamen untuk menemukan median. Kita dapat membuat pohon dengan 1000 node meninggalkan sehingga setiap node daun adalah array. Kami kemudian melakukan turnamen n / 2 antara berbagai array. Nilai pada root setelah turnamen n / 2 adalah hasilnya.

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/

karan kapoor
sumber
0

Jika angkanya tidak berbeda, dan hanya milik rentang tertentu, yaitu diulang, maka solusi sederhana yang muncul di benak saya adalah mendistribusikan angka-angka di antara 99 mesin secara merata, dan menjadikan satu mesin sebagai master. Sekarang setiap mesin mengulangi angka-angka yang diberikan, dan menyimpan hitungan masing-masing angka dalam satu set hash. Setiap kali angka diulang dalam himpunan angka yang dialokasikan untuk komputer tertentu, ia memperbarui hitungannya dalam hash set.

Semua mesin kemudian mengembalikan hash set ke mesin master. Mesin master menggabungkan set hash, menjumlahkan jumlah kunci yang sama yang ditemukan dalam set hash. Misalnya set hash mesin # 1 memiliki entri ("1", 7), dan set hash mesin # 2 memiliki entri ("1", 9), jadi mesin master saat menyisir set hash membuat entri dari ("1", 16), dan seterusnya.

Setelah hash set telah digabung, maka cukup sortir kunci, dan sekarang Anda dapat dengan mudah menemukan item th (n / 2) dan item th (n + 2/2), dari hash set yang diurutkan.

Metode ini tidak akan bermanfaat jika angka miliar berbeda.

Eric B.
sumber
0

Nah, misalkan Anda tahu bahwa jumlah bilangan bulat yang berbeda adalah (katakanlah) 4 miliar, maka Anda dapat memasukkannya ke dalam ember 64k dan mendapatkan jumlah yang didistribusikan untuk setiap ember dari setiap mesin di cluster (100 komputer). Gabungkan semua jumlah ini. Sekarang, cari ember yang memiliki median, dan kali ini hanya meminta ember untuk elemen 64k yang akan terletak di ember target Anda. Ini membutuhkan O (1) (khusus 2) kueri atas "gugus" Anda. : D

gandharv garg
sumber
0

Nilai sen saya, setelah semua yang telah dibesarkan oleh orang lain:

Menemukan median pada satu mesin adalah O (N): https://en.wikipedia.org/wiki/Selection_algorithm .

Mengirim nomor N ke 100 mesin juga O (N). Jadi, untuk membuat menggunakan 100 mesin menarik, komunikasi harus relatif cepat, atau N begitu besar sehingga satu mesin tidak dapat mengatasinya ketika N / 100 dapat dilakukan, atau kami hanya ingin mempertimbangkan masalah matematika tanpa peduli tentang komunikasi data.

Singkatnya, saya berasumsi bahwa dalam batas yang wajar, kami dapat mengirim / mendistribusikan angka tanpa memengaruhi analisis efisiensi.

Pertimbangkan pendekatan berikut, di mana satu mesin ditugaskan untuk menjadi "master" untuk beberapa pemrosesan umum. Ini akan relatif cepat, sehingga "master" juga berpartisipasi dalam tugas-tugas umum yang dilakukan setiap mesin.

  1. Setiap mesin menerima N / 100 dari angka-angka, menghitung mediannya sendiri dan mengirimkan informasi itu kepada master.
  2. Master mengkompilasi daftar semua median yang berbeda dan mengirimkannya kembali ke setiap mesin, menentukan urutan ember yang telah dipesan (pada setiap mesin yang sama), satu untuk setiap nilai median (ember bernilai tunggal) dan satu untuk setiap interval antara median yang berdekatan. Tentu saja ada juga bucket kelas bawah dan kelas atas untuk nilai di bawah median terendah dan di atas yang tertinggi.
  3. Setiap mesin menghitung berapa banyak angka yang jatuh di setiap ember dan mengkomunikasikan informasi itu kembali ke master.
  4. Master menentukan ember mana yang berisi median, berapa banyak nilai yang lebih rendah (total) jatuh di bawah ember itu, dan berapa banyak di atas.
  5. Jika ember yang dipilih adalah ember bernilai tunggal (salah satu median) atau buang ember yang dipilih hanya berisi 1 (N ganjil) atau 2 (bahkan N) nilai yang telah kami lakukan. Kalau tidak, kami ulangi langkah-langkah di atas dengan modifikasi (jelas) berikut:
  6. Hanya angka-angka dari ember yang dipilih yang (kembali) didistribusikan dari master ke 100 mesin, dan lebih dari itu
  7. Kami tidak akan menghitung median (pada setiap mesin), tetapi nilai k-th, di mana kami memperhitungkan berapa banyak angka yang lebih tinggi telah dibuang dari total, dan berapa banyak angka yang lebih rendah. Secara konseptual setiap mesin juga memiliki bagian dari angka rendah / tinggi yang dibuang dan memperhitungkannya saat menghitung median baru dalam himpunan yang (secara konseptual) mencakup (bagiannya) dari angka-angka yang dibuang.

Kompleksitas waktu:

  1. Sedikit pemikiran akan meyakinkan Anda bahwa pada setiap langkah jumlah total nilai yang akan dianalisis dikurangi dengan faktor setidaknya dua (2 akan menjadi kasus yang agak sakit; Anda mungkin mengharapkan pengurangan yang jauh lebih baik). Dari ini kita dapatkan:
  2. Dengan asumsi bahwa menemukan median (atau nilai k-th), yaitu O (N), membutuhkan c * N waktu di mana prefactor c tidak terlalu bervariasi dengan N sehingga kita dapat menganggapnya sebagai konstanta untuk saat ini, kami akan mendapatkan hasil akhir kami paling banyak 2 * c * N / 100 kali. Oleh karena itu, menggunakan 100 mesin memberi kita faktor kecepatan 100/2 (setidaknya).
  3. Seperti yang dikomentari pada awalnya: waktu yang digunakan untuk mengkomunikasikan angka-angka di antara mesin-mesin itu mungkin membuatnya lebih menarik untuk melakukan segala sesuatu pada satu mesin saja. Namun, JIKA kita menggunakan pendekatan terdistribusi, jumlah total angka yang dikomunikasikan dalam semua langkah bersama tidak akan melebihi 2 * N (N untuk pertama kalinya, <= N / 2 untuk kedua kalinya, <= setengah dari jumlah ketiga, dan seterusnya).
Bert te Velde
sumber
-1
  1. Bagilah 1 miliar angka menjadi 100 mesin. Setiap mesin akan memiliki 10 ^ 7 angka.

  2. Untuk setiap nomor yang masuk ke mesin, simpan nomor itu di peta frekuensi, angka -> hitung. Juga simpan nomor min di setiap mesin.

  3. Temukan median di setiap mesin: mulai dari angka minimum di setiap mesin, jumlah penghitungan hingga indeks median tercapai. Median di setiap mesin, akan menjadi sekitar. lebih rendah dan lebih besar dari 5 * 10 ^ 6 angka.

  4. Temukan median semua median, yang akan lebih rendah dan lebih besar dari kira-kira. 50 * 10 ^ 7 angka, yang merupakan median 1 miliar angka.

Sekarang beberapa optimasi dari langkah ke-2: Alih-alih menyimpan dalam peta frekuensi, simpan hitungan dalam array bit variabel. Sebagai contoh: Mari kita mulai dari nomor min di mesin, ini adalah jumlah frekuensi:

[min number] - 8 count
[min+1 number] - 7 count
[min+2 number] - 5 count

Di atas dapat disimpan dalam bit array sebagai:

[min number] - 10000000
[min+1 number] - 1000000
[min+2 number] - 10000

Perhatikan bahwa secara keseluruhan biayanya sekitar 10 ^ 7 bit untuk setiap mesin, karena setiap mesin hanya menangani 10 ^ 7 angka. 10 ^ 7bits = 1.25 * 10 ^ 6 byte, yaitu 1.25MB

Jadi dengan pendekatan di atas, setiap mesin akan membutuhkan ruang 1,25MB untuk menghitung median lokal. Dan median median dapat dihitung dari 100 median lokal, menghasilkan median 1 miliar angka.

Pisau
sumber
Bagaimana jika jumlahnya mengambang?
Sklivvz
-1

Saya menyarankan metode untuk menghitung sekitar Median. :) Jika satu miliar angka ini dalam urutan acak, saya pikir saya dapat memilih 1/100 atau 1/10 dari satu miliar angka secara acak, urutkan dengan 100 mesin, lalu pilih mediannya. Atau mari kita bagi miliar angka dalam 100 bagian, biarkan setiap mesin memilih 1/10 dari setiap bagian secara acak, hitung mediannya. Setelah itu kita memiliki 100 angka dan kita dapat menghitung median angka 100 lebih mudah. Hanya saran, saya tidak yakin apakah itu benar secara matematis. Tapi saya pikir Anda bisa menunjukkan hasilnya kepada manajer yang tidak terlalu pintar matematika.

anak laki-laki yang malas
sumber
Itu jelas tidak benar, dan saya sangat menyarankan Anda untuk tidak pernah menganggap pewawancara Anda adalah babi bodoh yang dapat Anda tipu
Dici
Haha ok, meskipun itu tidak mengubah fakta jawaban Anda salah. Sangat mudah untuk membuktikannya
Dici
OK, setelah membaca beberapa kuliah tentang statistik, saya pikir ide mengambil 1/100 atau bahkan 1/1000 secara acak dari satu miliar angka dan menghitung median mereka tidak terlalu buruk. Ini hanya perhitungan perkiraan.
lazyboy
-3

Jawaban Steve Jessop salah:

pertimbangkan empat kelompok berikut:

{2, 4, 6, 8, 10}

{21, 21, 24, 26, 28}

{12, 14, 30, 32, 34}

{16, 18, 36, 38, 40}

Median adalah 21, yang terkandung dalam kelompok kedua.

Median dari empat kelompok adalah 6, 24, 30, 36, Total median adalah 27.

Jadi setelah loop pertama, empat grup akan menjadi:

{6, 8, 10}

{24, 26, 28}

{12, 14, 30}

{16, 18, 36}

21 sudah salah dibuang.

Algoritma ini hanya mendukung kasus ketika ada dua kelompok.

penguasa kegelapan
sumber