Algoritma nontrivial untuk menghitung median sliding window

Saya perlu menghitung median berjalan:

Input: , , vektor . $n$ $k$ $(x_1, x_2, \dotsc, x_n)$
Output: vektor , di mana adalah median dari . $(y_1, y_2, \dotsc, y_{n-k+1})$ $y_i$ $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$

(Tidak ada kecurangan dengan perkiraan; Saya ingin memiliki solusi yang tepat. Elemen adalah bilangan bulat besar.) $x_i$

Ada algoritma sepele yang memelihara pohon pencarian ukuran ; total waktu berjalan adalah . (Di sini "pohon pencarian" mengacu pada beberapa struktur data efisien yang mendukung penyisipan, penghapusan, dan kueri median dalam waktu logaritmik.) $k$ $O(n \log k)$

Namun, ini agak bodoh bagi saya. Kami akan secara efektif mempelajari semua statistik pesanan dalam semua jendela ukuran , bukan hanya median. Selain itu, ini tidak terlalu menarik dalam praktiknya, terutama jika besar (pohon pencarian besar cenderung lambat, overhead dalam konsumsi memori adalah non-sepele, efisiensi cache sering buruk, dll). $k$ $k$

Bisakah kita melakukan sesuatu yang jauh lebih baik?

Adakah batas bawah (misalnya, apakah algoritma trivial asimtotik optimal untuk model perbandingan)?

Sunting: David Eppstein memberikan batas bawah yang bagus untuk model perbandingan! Saya bertanya-tanya apakah mungkin untuk melakukan sesuatu yang sedikit lebih pintar daripada algoritma sepele?

Sebagai contoh, dapatkah kita melakukan sesuatu di sepanjang baris ini: membagi vektor input ke bagian-bagian berukuran ; mengurutkan setiap bagian (melacak posisi asli setiap elemen); dan kemudian menggunakan vektor disortir piecewise untuk menemukan median berjalan secara efisien tanpa struktur data tambahan? Tentu saja ini masih , tetapi dalam praktiknya sortasi array cenderung jauh lebih cepat daripada mempertahankan pohon pencarian. $k$ $O(n \log k)$

Sunting 2: Saeed ingin melihat beberapa alasan mengapa saya pikir penyortiran lebih cepat daripada operasi pencarian pohon. Berikut ini adalah tolok ukur yang sangat cepat, untuk , : $k = 10^7$ $n = 10^8$

≈ 8s: masing-masing menyortir vektor dengan elemen $n/k$ $k$
≈ 10d: menyortir vektor dengan elemen $n$
≈ 80an: penyisipan & penghapusan dalam tabel hash dengan ukuran $n$ $k$
≈ 390an: penyisipan & penghapusan di pohon pencarian seimbang ukuran $n$ $k$

Tabel hash ada hanya untuk perbandingan; itu tidak ada gunanya langsung dalam aplikasi ini.

Singkatnya, kami memiliki hampir faktor 50 perbedaan dalam kinerja operasi pohon pencarian penyortiran vs seimbang. Dan segalanya menjadi lebih buruk jika kita meningkatkan . $k$

(Detail teknis: Data = bilangan bulat 32-bit acak. Komputer = laptop modern tipikal. Kode tes ditulis dalam C ++, menggunakan rutin perpustakaan standar (std :: sort) dan struktur data (std :: multiset, std :: unsorted_multiset) Saya menggunakan dua kompiler C ++ yang berbeda (GCC dan Dentang), dan dua implementasi berbeda dari library standar (libstdc ++ dan libc ++) .Secara tradisional, std :: multiset telah diimplementasikan sebagai pohon merah-hitam yang sangat dioptimalkan.)

ds.algorithms ds.data-structures lower-bounds Jukka Suomela
sumber

Saya tidak berpikir Anda akan dapat meningkatkan

. Pasalnya, jika Anda melihat jendela

, Anda tidak pernah mengesampingkan salah satu nomor

n l o g k

$nlogk$

x_{t}, . . ., x_{t + k - 1}

$x_t,...,x_{t+k-1}$

dari median jendela masa depan. Ini berarti bahwa setiap saat Anda harus menyimpan setidaknya

x_{t + \frac{k}{2}}, . . ., x_{t + k - 1}

$x_{t+\frac{k}{2}},...,x_{t+k-1}$

bilangan bulat dalam struktur data, dan sepertinya tidak diperbarui dalam waktu kurang dari waktu log.

\frac{k}{2}

$\frac{k}{2}$

Algoritma sepele Anda bagi saya tampaknya

bukan

, apakah saya salah mengerti sesuatu? Dan saya pikir karena ini Anda memiliki masalah dengan

besar , jika faktor logaritmik tidak ada dalam aplikasi praktis, juga tidak ada konstanta tersembunyi yang besar dalam algoritma ini.

O ((n - k) \cdot k \cdot \log k)

$O((n-k)\cdot k \cdot \log k)$

O (n \log k)

$O(n \log k)$

k

$k$

Saeed

@ Saeed: Dalam algoritma sepele, Anda memproses elemen satu per satu; pada langkah

Anda menambahkan

ke pohon pencarian dan (jika

) Anda juga menghapus

dari pohon pencarian. Ini adalah

langkah, yang masing-masing membutuhkan waktu

i

$i$

x_{i}

$x_i$

i > k

$i > k$

x_{i - k}

$x_{i-k}$

n

$n$

O (\log k)

$O(\log k)$

Jukka Suomela

Jadi maksud Anda Anda memiliki pohon pencarian seimbang bukan pohon pencarian kasual?

Saeed

@ Saeed: Harap dicatat bahwa dalam tolok ukur saya, saya bahkan tidak mencoba mencari median. Aku hanya melakukan

sisipan dan

penghapusan dalam pohon pencarian dari ukuran

, dan operasi ini dijamin untuk mengambil

waktu. Anda hanya perlu menerima bahwa operasi pohon pencarian sangat lambat dalam praktiknya, dibandingkan dengan penyortiran. Anda akan melihat ini dengan mudah jika Anda mencoba untuk menulis algoritma penyortiran yang berfungsi dengan menambahkan elemen ke pohon pencarian seimbang - itu pasti bekerja dalam waktu

, tetapi akan sangat lambat dalam prakteknya, dan juga membuang banyak memori.

n

$n$

n

$n$

k

$k$

O (\log k)

$O(\log k)$

O (n \log n)

$O(n \log n)$

Jukka Suomela

Jawaban:

Inilah batas bawah dari penyortiran. Diberikan set input dengan panjang akan diurutkan, buat input untuk masalah median Anda yang sedang berjalan yang terdiri dari salinan angka lebih kecil dari minimum , kemudian sendiri, lalu salinan angka lebih besar dari maksimum , dan atur . Median berjalan dari masukan ini adalah sama dengan urutan diurutkan . $S$ $n$ $n-1$ $S$ $S$ $n-1$ $S$ $k=2n-1$ $S$

Jadi dalam model perbandingan perhitungan, diperlukan waktu . Mungkin jika input Anda adalah bilangan bulat dan Anda menggunakan algoritma pengurutan bilangan bulat yang dapat Anda lakukan dengan lebih baik. $\Omega(n\log n)$

David Eppstein
sumber

Jawaban ini benar-benar membuat saya bertanya-tanya apakah kebalikannya juga berlaku: diberikan algoritma penyortiran yang efisien, apakah kita mendapatkan algoritma median berjalan yang efisien? (Misalnya, apakah pada algoritma penyortiran integer efisien menyiratkan algoritma median berjalan efisien untuk integer? Atau apakah algoritma penyortiran efisien-IO menyediakan algoritma median berjalan efisien-IO?)

Jukka Suomela

Sekali lagi, terima kasih banyak atas jawaban Anda, itu benar-benar membuat saya berada di jalur yang benar dan memberikan inspirasi untuk algoritma filter median berdasarkan penyortiran! Pada akhirnya saya dapat menemukan makalah dari tahun 1991 yang pada dasarnya menyajikan argumen yang sama dengan apa yang Anda berikan di sini, dan Pat Morin memberikan petunjuk ke makalah lain yang relevan dari tahun 2005; lihat referensi. [6] dan [9] di sini .

Jukka Suomela

Sunting: Algoritma ini sekarang disajikan di sini: http://arxiv.org/abs/1406.1717

Ya, untuk mengatasi masalah ini, cukup melakukan operasi berikut:

Urutkan vektor , masing-masing dengan elemen . $n/k$ $k$
Lakukan pasca-pemrosesan linear-waktu.

Sangat kasar, idenya adalah ini:

Pertimbangkan dua blok input yang berdekatan, dan , keduanya dengan elemen ; biarkan elemen menjadi dan di urutan penampilan di vektor input . $a$ $b$ $k$ $a_1, a_2, ..., a_k$ $b_1, b_2, ..., b_k$ $x$
Urutkan blok ini dan pelajari peringkat setiap elemen di dalam blok.
Menambah vektor dan dengan pointer pendahulu / penerus sehingga dengan mengikuti rantai penunjuk kita dapat melintasi elemen dalam urutan yang meningkat. Dengan cara ini kita telah membangun ganda terkait daftar dan . $a$ $b$ $a'$ $b'$
Satu per satu, menghapus semua elemen dari daftar terkait , dalam urutan terbalik dari penampilan . Setiap kali kami menghapus suatu elemen, ingat apa penggantinya & pendahulunya pada saat penghapusan . $b'$ $b_k, b_{k-1}, ..., b_1$
Sekarang mempertahankan "pointer median" dan yang mengarah ke daftar dan , masing-masing. Menginisialisasinya ke titik tengah , dan Menginisialisasinya ke ekor kosong daftar . $p$ $q$ $a'$ $b'$ $p$ $a'$ $q$ $b'$
Untuk setiap : $i$
- Menghapus dari daftar (ini adalah waktu, hapus saja dari linked list). Bandingkan dengan elemen ditunjuk oleh untuk melihat apakah kita dihapus sebelum atau setelah . $a_i$ $a'$ $O(1)$ $a_i$ $p$ $p$
- Masukkan kembali ke daftar di posisi semula (ini kali, kami menghafal pendahulu dan penerus ). Bandingkan dengan elemen yang ditunjuk oleh untuk melihat apakah kita menambahkan elemen sebelum atau setelah . $b_i$ $b'$ $O(1)$ $b_i$ $b_i$ $q$ $q$
- $p$ $q$ $a' \cup b'$ $p$ $q$ $O(1)$ $p$ $q$ $p$ $q$

$k$

Berikut adalah contoh penerapan dan tolok ukur:

https://github.com/suomela/median-filter

$n \approx 2\cdot 10^6$

$O(n \log k)$
$O(n \log k)$
$O(n \log k)$
$O(n k)$
$\approx k/2$
Sumbu Y = waktu berjalan dalam detik.
Data = bilangan bulat 32-bit dan bilangan bulat 64-bit acak, dari berbagai distribusi.

waktu berjalan

Jukka Suomela
sumber

$m$ $O(n \log m + m \log n)$

$O(\log m)$ $O(\log n)$ $O(\log n)$ biaya hanya terjadi satu kali per median.

$O(n \log m + m \log k)$

Geoffrey Irving
sumber

Ups, ini tidak berfungsi seperti yang tertulis, karena jika Anda tidak menghapus elemen, penghitungan tidak akan mencerminkan jendela baru. Saya tidak yakin apakah itu bisa diperbaiki, tetapi saya akan meninggalkan jawabannya kalau-kalau ada cara.

Geoffrey Irving

O (n \log m)

$O(n \log m)$

catatan: Pertanyaan tidak jelas, struktur data bawahan tidak didefinisikan, kita hanya tahu sesuatu yang sangat kabur. bagaimana Anda ingin meningkatkan sesuatu yang Anda tidak tahu apa itu? bagaimana Anda ingin membandingkan pendekatan Anda?

Saeed

Saya minta maaf atas pekerjaan yang tidak lengkap. Saya telah mengajukan pertanyaan konkret yang diperlukan untuk memperbaiki jawaban ini di sini: cstheory.stackexchange.com/questions/21778/… . Jika menurut Anda itu sesuai, saya dapat menghapus jawaban ini sampai pertanyaan kedua diselesaikan.

Geoffrey Irving