Pada ukuran jendela yang lebih kecil, n log n
pengurutan mungkin berhasil. Apakah ada algoritma yang lebih baik untuk mencapai ini?
algorithms
median
miku
sumber
sumber
Jawaban:
Bentuk buruk untuk mengurutkan array untuk menghitung median. Median (dan kuantil lainnya) biasanya dihitung menggunakan algoritma pemilihan cepat, dengan kompleksitas .O ( n )
Anda mungkin juga ingin melihat jawaban saya untuk pertanyaan terkait baru-baru ini di sini .
sumber
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.
sumber
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
sumber
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.
sumber
Seperti yang Anda sebutkan penyortiran akan
O(n·log n)
untuk jendela panjangn
. Melakukan pemindahan ini menambah satu lagil=vectorlength
membuat total biayaO(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 biayaO(l·n)
.Kodesemu:
sumber
Berikut ini adalah solusi O (1) untuk menemukan median saat ini, dan O (log n) untuk menambahkan nomor baru http://www.dsalgo.com/RunningMedian.php
sumber
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.
sumber
Saya menggunakan RunningStats C ++ Library ini dalam aplikasi yang disematkan. Ini adalah perpustakaan statistik berjalan paling sederhana yang saya temukan.
Dari tautan:
sumber