Temukan median yang berjalan dari aliran bilangan bulat

Kemungkinan Duplikat:
Algoritma median bergulir dalam C

Mengingat bahwa bilangan bulat dibaca dari aliran data. Temukan median elemen yang dibaca sejauh ini dengan cara yang efisien.

Solusi yang saya baca: Kita dapat menggunakan tumpukan maksimum di sisi kiri untuk mewakili elemen yang kurang dari median efektif, dan tumpukan minimum di sisi kanan untuk mewakili elemen yang lebih besar dari median efektif.

Setelah memproses elemen yang masuk, jumlah elemen dalam tumpukan berbeda paling banyak dengan 1 elemen. Ketika kedua tumpukan berisi jumlah elemen yang sama, kami menemukan rata-rata data root tumpukan sebagai median efektif. Ketika tumpukan tidak seimbang, kami memilih median efektif dari akar tumpukan yang mengandung lebih banyak elemen.

Tetapi bagaimana kita membangun tumpukan maksimum dan tumpukan minimum yaitu bagaimana kita tahu median efektif di sini? Saya berpikir bahwa kita akan memasukkan 1 elemen di max-heap dan kemudian 1 elemen berikutnya di min-heap, dan seterusnya untuk semua elemen. Koreksi saya Jika saya salah di sini.

Ada sejumlah solusi berbeda untuk menemukan median berjalan dari data yang dialirkan, saya akan membicarakannya secara singkat di akhir jawaban.

Pertanyaannya adalah tentang perincian dari solusi spesifik (max heap / min heap solution), dan bagaimana solusi berbasis heap bekerja dijelaskan di bawah ini:

Untuk dua elemen pertama tambahkan yang lebih kecil ke maxHeap di sebelah kiri, dan yang lebih besar ke minHeap di sebelah kanan. Kemudian proses aliran data satu per satu,

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

Kemudian pada waktu tertentu Anda dapat menghitung median seperti ini:

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

Sekarang saya akan berbicara tentang masalah secara umum seperti yang dijanjikan di awal jawaban. Menemukan menjalankan median dari aliran data adalah masalah yang sulit, dan menemukan solusi yang tepat dengan kendala memori secara efisien mungkin tidak mungkin untuk kasus umum. Di sisi lain, jika data memiliki beberapa karakteristik yang dapat kita eksploitasi, kita dapat mengembangkan solusi khusus yang efisien. Misalnya, jika kita tahu bahwa data adalah tipe integral, maka kita dapat menggunakan penghitungan, Yang dapat memberi Anda algoritma waktu konstan memori konstan. Solusi berbasis heap adalah solusi yang lebih umum karena dapat digunakan untuk tipe data lain (ganda) juga. Dan akhirnya, jika median yang tepat tidak diperlukan dan perkiraan sudah cukup, Anda bisa mencoba memperkirakan fungsi kepadatan probabilitas untuk data dan memperkirakan median yang menggunakannya.

Jika Anda tidak dapat menyimpan semua item dalam memori sekaligus, masalah ini menjadi jauh lebih sulit. Solusi tumpukan meminta Anda untuk menahan semua elemen dalam memori sekaligus. Ini tidak mungkin di sebagian besar aplikasi dunia nyata dari masalah ini.

Alih-alih, saat Anda melihat angka, catat hitungan berapa kali Anda melihat setiap bilangan bulat. Dengan asumsi bilangan bulat 4 byte, itu 2 ^ 32 ember, atau paling banyak 2 ^ 33 bilangan bulat (kunci dan hitung untuk setiap int), yaitu 2 ^ 35 byte atau 32GB. Kemungkinan akan jauh lebih sedikit daripada ini karena Anda tidak perlu menyimpan kunci atau menghitung entri yang 0 (mis. Seperti defaultdict in python). Ini membutuhkan waktu yang konstan untuk memasukkan setiap integer baru.

Kemudian pada titik mana pun, untuk menemukan median, cukup gunakan hitungan untuk menentukan bilangan bulat mana yang merupakan elemen tengah. Ini membutuhkan waktu yang konstan (meskipun konstan besar, tetapi tetap konstan).

Jika varian input terdistribusi secara statistik (mis. Normal, log-normal, dll.) Maka pengambilan sampel reservoir adalah cara yang masuk akal untuk memperkirakan persentil / median dari aliran angka yang sewenang-wenang.

int n = 0;  // Running count of elements observed so far  
#define SIZE 10000
int reservoir[SIZE];  

while(streamHasData())
{
  int x = readNumberFromStream();

  if (n < SIZE)
  {
       reservoir[n++] = x;
  }         
  else 
  {
      int p = random(++n); // Choose a random number 0 >= p < n
      if (p < SIZE)
      {
           reservoir[p] = x;
      }
  }
}

"reservoir" kemudian merupakan sampel semua input yang berjalan, seragam (wajar) - berapapun ukurannya. Menemukan median (atau persentil apa pun) adalah hal yang mudah untuk menyortir reservoir dan mengumpulkan poin yang menarik.

Karena reservoir berukuran tetap, penyortiran dapat dianggap efektif O (1) - dan metode ini berjalan dengan konsumsi waktu dan memori yang konstan.

Cara paling efisien untuk menghitung persentil aliran yang saya temukan adalah algoritma P²: Raj Jain, Imrich Chlamtac: Algoritma P² untuk Perhitungan Dinamis Kuantiil dan Histogram Tanpa Menyimpan Pengamatan. Komunal. ACM 28 (10): 1076-1085 (1985)

Algoritma ini lurus ke depan untuk mengimplementasikan dan bekerja dengan sangat baik. Namun, ini merupakan perkiraan, jadi ingatlah itu. Dari abstrak:

Algoritma heuristik diusulkan untuk perhitungan dinamis jika median dan kuantil lainnya. Estimasi tersebut dihasilkan secara dinamis saat pengamatan dihasilkan. Pengamatan tidak disimpan; oleh karena itu, algoritma ini memiliki persyaratan penyimpanan yang sangat kecil dan tetap terlepas dari jumlah pengamatan. Ini membuatnya ideal untuk diimplementasikan dalam chip kuantil yang dapat digunakan dalam pengontrol dan perekam industri. Algoritma selanjutnya diperluas ke plot histogram. Keakuratan algoritma dianalisis.

Jika kita ingin menemukan median dari n elemen yang paling baru dilihat, masalah ini memiliki solusi tepat yang hanya membutuhkan n elemen yang paling baru dilihat untuk disimpan dalam memori. Ini cepat dan bersisik dengan baik.

Daftar lompatan yang dapat diindeks mendukung O (ln n) penyisipan, penghapusan, dan pencarian yang diindeks dari elemen-elemen sembarang sambil mempertahankan urutan yang diurutkan. Ketika digabungkan dengan antrian FIFO yang melacak entri tertua ke-n, solusinya sederhana:

class RunningMedian:
    'Fast running median with O(lg n) updates where n is the window size'

    def __init__(self, n, iterable):
        self.it = iter(iterable)
        self.queue = deque(islice(self.it, n))
        self.skiplist = IndexableSkiplist(n)
        for elem in self.queue:
            self.skiplist.insert(elem)

    def __iter__(self):
        queue = self.queue
        skiplist = self.skiplist
        midpoint = len(queue) // 2
        yield skiplist[midpoint]
        for newelem in self.it:
            oldelem = queue.popleft()
            skiplist.remove(oldelem)
            queue.append(newelem)
            skiplist.insert(newelem)
            yield skiplist[midpoint]

Berikut ini tautan untuk menyelesaikan kode kerja (versi kelas yang mudah dipahami dan versi generator yang dioptimalkan dengan kode daftar lewati yang dapat diindekskan):

• http://code.activestate.com/recipes/576930-efisien-running-median-using-an-indexable-skipli/

• http://code.activestate.com/recipes/577073 .

Cara intuitif untuk memikirkan hal ini adalah bahwa jika Anda memiliki pohon pencarian biner seimbang penuh, maka root akan menjadi elemen median, karena akan ada jumlah elemen yang lebih kecil dan lebih besar. Sekarang, jika pohon tidak penuh ini tidak akan menjadi masalah karena akan ada elemen yang hilang dari tingkat terakhir.

Jadi yang bisa kita lakukan adalah memiliki median, dan dua pohon biner seimbang, satu untuk elemen kurang dari median, dan satu untuk elemen lebih besar dari median. Kedua pohon harus disimpan pada ukuran yang sama.

Ketika kami mendapatkan integer baru dari aliran data, kami membandingkannya dengan median. Jika lebih besar dari median, kami menambahkannya ke pohon yang benar. Jika dua ukuran pohon berbeda lebih dari 1, kami menghapus elemen min dari pohon kanan, menjadikannya median baru, dan menempatkan median lama di pohon kiri. Begitu pula untuk yang lebih kecil.

Efisien adalah kata yang tergantung pada konteks. Solusi untuk masalah ini tergantung pada jumlah kueri yang dilakukan relatif terhadap jumlah penyisipan. Misalkan Anda memasukkan angka N dan waktu K menjelang akhir Anda tertarik pada median. Kompleksitas algoritma heap based adalah O (N log N + K).

Pertimbangkan alternatif berikut. Memotong angka-angka dalam array, dan untuk setiap permintaan, jalankan algoritma seleksi linear (menggunakan pivot quicksort, katakanlah). Sekarang Anda memiliki algoritma dengan running time O (KN).

Sekarang jika K cukup kecil (kueri yang jarang), algoritma yang terakhir sebenarnya lebih efisien dan sebaliknya.

Tidak bisakah kau melakukan ini hanya dengan satu tumpukan? Pembaruan: no. Lihat komentarnya.

Invarian: Setelah membaca 2*ninput, tumpukan min memegang yang nterbesar.

Loop: Baca 2 input. Tambahkan keduanya ke heap, dan hapus min heap. Ini membangun kembali invarian.

Jadi, ketika 2ninput telah dibaca, min heap adalah yang terbesar ke-n. Perlu ada sedikit komplikasi tambahan untuk rata-rata dua elemen di sekitar posisi median dan untuk menangani permintaan setelah jumlah input ganjil.