Algoritma untuk menghitung median berjalan?

18

Pada ukuran jendela yang lebih kecil, n log npengurutan mungkin berhasil. Apakah ada algoritma yang lebih baik untuk mencapai ini?

miku
sumber
1
Saya pikir ini adalah kandidat pertama yang akan dipindahkan ke Stack Overflow.
Mungkin, tetapi perlu penjelasan lebih banyak tentang SO.
walkytalky
2
Kebanyakan programmer tahu "median". (sort (array)) [length / 2] adalah petunjuk yang cukup besar bagi mereka yang lupa. Juga pada titik yang paling mendasar untuk setiap titik baru Anda hanya perlu melakukan pembelahan dua / memasukkan pada setengah dari array ...
Paul
1
Dibuka kembali setelah diskusi di meta.stats.stackexchange.com/questions/276/…
Rob Hyndman
2
Terlalu sepele untuk menjadi lebih dari sekedar komentar, tetapi kode untuk median 3s hanyalah + b + c - maks (a, b, c) - min (a, b. C). Itu bekerja dengan baik bahkan jika ada ikatan. Itu hanya jelas bagi saya setelah saya memikirkannya dari kode orang lain (mengapa dia (dalam hal ini) menambah dan mengurangi untuk mendapatkan median ???) dan beberapa orang lain mungkin memiliki reaksi yang sama. max () dan min () sering diimplementasikan sebagai fungsi super cepat. Sayangnya tidak ada trik seperti itu secara umum.
Nick Cox

Jawaban:

11

Bentuk buruk untuk mengurutkan array untuk menghitung median. Median (dan kuantil lainnya) biasanya dihitung menggunakan algoritma pemilihan cepat, dengan kompleksitas .HAI(n)

Anda mungkin juga ingin melihat jawaban saya untuk pertanyaan terkait baru-baru ini di sini .

pengguna603
sumber
7

Berikut adalah artikel yang menjelaskan satu algoritma yang mungkin. Kode sumber disertakan dan aplikasi yang cukup serius (deteksi gelombang gravitasi berdasarkan interferometri laser), sehingga Anda dapat mengharapkannya diuji dengan baik.

Łukasz Lew
sumber
1
Tautan rusak, dan tanpa informasi judul atau penulis, sulit untuk menemukan apa pun yang dimaksud.
Kristopher Johnson
6

Jika Anda bersedia mentolerir perkiraan, ada metode lain. Misalnya, satu perkiraan adalah nilai yang peringkatnya berada dalam jarak (ditentukan pengguna) dari median yang sebenarnya. Misalnya, median memiliki (dinormalisasi) peringkat 0,5, dan jika Anda menentukan istilah kesalahan 10%, Anda ingin jawaban yang memiliki peringkat antara 0,45 dan 0,55.

Jika jawaban seperti itu tepat, maka ada banyak solusi yang dapat bekerja pada sliding data windows. Ide dasarnya adalah mempertahankan sampel data dengan ukuran tertentu (kira-kira istilah 1 / kesalahan) dan menghitung median pada sampel ini. Dapat ditunjukkan bahwa dengan probabilitas tinggi, terlepas dari sifat input, median yang dihasilkan memenuhi sifat yang saya sebutkan di atas.

Dengan demikian, pertanyaan utama adalah bagaimana mempertahankan sampel data yang berjalan dengan ukuran tertentu, dan ada banyak pendekatan untuk itu, termasuk teknik yang dikenal sebagai pengambilan sampel reservoir. Misalnya, makalah ini: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.2.7.76

Suresh Venkatasubramanian
sumber
4

Jika Anda mempertahankan panjang-k jendela data sebagai daftar ditautkan yang diurutkan dua kali lipat, melalui pencarian biner (untuk menyisipkan setiap elemen baru saat digeser ke dalam jendela) dan array melingkar dari pointer (untuk segera menemukan elemen yang perlu dihapus), setiap pergeseran jendela membutuhkan upaya O (log (k)) untuk memasukkan satu elemen, hanya upaya O (1) untuk menghapus elemen yang digeser keluar dari jendela, dan hanya upaya O (1) untuk menemukan median (karena setiap kali satu elemen dimasukkan atau dihapus ke dalam daftar, Anda dapat memperbarui pointer ke median dalam O (1) waktu). Upaya total untuk memproses array dengan panjang N karena itu adalah O ((nk) log (k)) <= O (n log (k)). Ini lebih baik daripada metode lain yang diusulkan sejauh ini dan itu bukan perkiraan, itu tepat.

whuber
sumber
1
Bisakah Anda menguraikan bagaimana Anda mengusulkan untuk melakukan pencarian biner dalam daftar yang ditautkan dua kali lipat?
NPE
satu 'tautan' memungkinkan Anda untuk melintasi daftar dalam urutan yang diurutkan; yang lain memungkinkan Anda untuk melintasi urutan di mana elemen muncul. Tidak jelas bagaimana Anda akan melakukan ini dengan pointer, meskipun, sebagai pertanyaan @aix.
shabbychef
2
@ Alex Saya pikir keintiman Anda benar; Saya perlu daftar lewati yang dapat diindeks, bukan hanya daftar yang ditautkan dua kali lipat. Idenya adalah untuk memiliki struktur data yang memungkinkan penyisipan satu elemen, penghapusan satu elemen, dan menemukan median dalam waktu O (log (n)) yang diharapkan (atau lebih baik).
whuber
3

Seperti yang Anda sebutkan penyortiran akan O(n·log n)untuk jendela panjang n. Melakukan pemindahan ini menambah satu lagi l=vectorlengthmembuat total biaya O(l·n·log n).

Cara termudah untuk mendorong ini adalah dengan menjaga daftar urutan elemen n terakhir dalam memori ketika pindah dari satu jendela ke yang berikutnya. Karena menghapus / memasukkan satu elemen dari / ke dalam daftar yang dipesan keduanya O(n)akan menghasilkan biaya O(l·n).

Kodesemu:

l = length(input)
aidvector = sort(input(1:n))
output(i) = aid(n/2)
for i = n+1:l
    remove input(i-n) from aidvector
    sort aid(n) into aidvector
    output(i) = aid(n/2)
yihihere
sumber
2

Jika Anda dapat hidup dengan perkiraan alih-alih median sebenarnya, Algoritma Remedian (PDF) adalah satu langkah dengan persyaratan penyimpanan rendah dan akurasi yang terdefinisi dengan baik.

Penyembuhan dengan basis b dilanjutkan dengan menghitung median kelompok-kelompok pengamatan b, dan kemudian median median-median ini, hingga hanya satu estimasi yang tersisa. Metode ini hanya membutuhkan k array ukuran b (di mana n = b ^ k) ...

pembuat sepatu
sumber
0

Saya menggunakan RunningStats C ++ Library ini dalam aplikasi yang disematkan. Ini adalah perpustakaan statistik berjalan paling sederhana yang saya temukan.

Dari tautan:

Kode ini merupakan perpanjangan dari metode Knuth dan Welford untuk menghitung standar deviasi dalam satu kali melewati data. Ini menghitung skewness dan kurtosis juga dengan antarmuka yang sama. Selain hanya membutuhkan satu kali melewati data, algoritma ini stabil secara numerik dan akurat.

Chris K
sumber
Apakah halaman itu mengatakan sesuatu tentang median?
musiphil