Cara menerapkan shuffle tertimbang

Baru-baru ini saya menulis beberapa kode yang saya pikir sangat tidak efisien, tetapi karena hanya menyertakan beberapa nilai, saya menerimanya. Namun, saya masih tertarik pada algoritma yang lebih baik untuk hal berikut:

1. Daftar objek X, masing-masing diberi "bobot"
2. Ringkas bobotnya
3. Hasilkan angka acak dari 0 hingga jumlah
4. Iterasi melalui objek, kurangi beratnya dari jumlah hingga jumlahnya tidak positif
5. Hapus objek dari daftar, dan kemudian tambahkan ke akhir daftar baru

Item 2,4, dan 5 semuanya membutuhkan nwaktu, dan karena itu merupakan O(n^2)algoritma.

Bisakah ini diperbaiki?

Sebagai contoh pengocokan tertimbang, elemen memiliki peluang lebih besar untuk berada di depan dengan bobot lebih tinggi.

Contoh (Saya akan membuat angka acak untuk membuatnya nyata):

6 benda dengan bobot 6,5,4,3,2,1; Jumlahnya adalah 21

Saya memilih 19 19-6-5-4-3-2 = -1:, dengan demikian 2 berada di posisi pertama, bobot sekarang 6,5,4,3,1; Jumlahnya adalah 19

Saya memilih 16 16-6-5-4-3 = -2:, dengan demikian 3 berada di posisi kedua, bobot sekarang 6,5,4,1; Jumlahnya adalah 16

Saya memilih 3 3-6 = -3:, dengan demikian 6 berada di posisi ketiga, bobot sekarang 5,4,1; Jumlahnya adalah 10

Saya memilih 8:, 8-5-4 = -1dengan demikian 4 berada di posisi keempat, bobot sekarang 5,1; Jumlahnya adalah 6

Saya memilih 5:, 5-5=0dengan demikian 5 berada di posisi kelima, bobot sekarang 1; Jumlahnya adalah 1

Saya memilih 1:, 1-1=0dengan demikian 1 berada di posisi terakhir, saya tidak punya beban lagi, saya selesai

Ini dapat diimplementasikan dalam O(n log(n))menggunakan pohon.

Pertama, buat pohon, menjaga setiap simpul jumlah kumulatif semua node keturunan di sebelah kanan dan di sebelah kiri setiap node.

Untuk mengambil sampel suatu barang, sampel secara rekursif dari simpul akar, menggunakan jumlah kumulatif untuk memutuskan apakah Anda mengembalikan simpul saat ini, simpul dari kiri atau simpul dari kanan. Setiap kali Anda mengambil sampel node, atur bobotnya ke nol dan perbarui node induknya.

Ini adalah implementasi saya di Python:

import random

def weigthed_shuffle(items, weights):
    if len(items) != len(weights):
        raise ValueError("Unequal lengths")

    n = len(items)
    nodes = [None for _ in range(n)]

    def left_index(i):
        return 2 * i + 1

    def right_index(i):
        return 2 * i + 2

    def total_weight(i=0):
        if i >= n:
            return 0
        this_weigth = weights[i]
        if this_weigth <= 0:
            raise ValueError("Weigth can't be zero or negative")
        left_weigth = total_weight(left_index(i))
        right_weigth = total_weight(right_index(i))
        nodes[i] = [this_weigth, left_weigth, right_weigth]
        return this_weigth + left_weigth + right_weigth

    def sample(i=0):
        this_w, left_w, right_w = nodes[i]
        total = this_w + left_w + right_w
        r = total * random.random()
        if r < this_w:
            nodes[i][0] = 0
            return i
        elif r < this_w + left_w:
            chosen = sample(left_index(i))
            nodes[i][1] -= weights[chosen]
            return chosen
        else:
            chosen = sample(right_index(i))
            nodes[i][2] -= weights[chosen]
            return chosen

    total_weight() # build nodes tree

    return (items[sample()] for _ in range(n - 1))

Pemakaian:

In [2]: items = list(range(10))
   ...: weights = list(range(10, 0, -1))
   ...:

In [3]: for _ in range(10):
   ...:     print(list(weigthed_shuffle(items, weights)))
   ...:
[5, 0, 8, 6, 7, 2, 3, 1, 4]
[1, 2, 5, 7, 3, 6, 9, 0, 4]
[1, 0, 2, 6, 8, 3, 7, 5, 4]
[4, 6, 8, 1, 2, 0, 3, 9, 7]
[3, 5, 1, 0, 4, 7, 2, 6, 8]
[3, 7, 1, 2, 0, 5, 6, 4, 8]
[1, 4, 8, 2, 6, 3, 0, 9, 5]
[3, 5, 0, 4, 2, 6, 1, 8, 9]
[6, 3, 5, 0, 1, 2, 4, 8, 7]
[4, 1, 2, 0, 3, 8, 6, 5, 7]

weigthed_shuffleadalah generator, sehingga Anda dapat mencicipi kitem teratas secara efisien. Jika Anda ingin mengocok seluruh array, cukup putar di atas generator sampai habis (menggunakan listfungsi).

MEMPERBARUI:

Weighted Random Sampling (2005; Efraimidis, Spirakis) menyediakan algoritma yang sangat elegan untuk ini. Implementasinya super sederhana, dan juga berjalan di O(n log(n)):

def weigthed_shuffle(items, weights):
    order = sorted(range(len(items)), key=lambda i: -random.random() ** (1.0 / weights[i]))
    return [items[i] for i in order]

EDIT: Jawaban ini tidak menginterpretasikan bobot dengan cara yang diharapkan. Ie item dengan berat 2 tidak dua kali lebih mungkin menjadi yang pertama dengan berat 1.

Salah satu cara untuk mengacak daftar adalah dengan menetapkan angka acak untuk setiap elemen dalam daftar dan mengurutkan berdasarkan angka-angka itu. Kita dapat memperluas gagasan itu, kita hanya harus memilih angka acak berbobot. Misalnya, Anda bisa menggunakan random() * weight. Pilihan yang berbeda akan menghasilkan distribusi yang berbeda.

Dalam sesuatu seperti Python, ini harus sesederhana:

items.sort(key = lambda item: random.random() * item.weight)

Berhati-hatilah agar Anda tidak mengevaluasi kunci lebih dari sekali, karena akan berakhir dengan nilai yang berbeda.

Pertama, mari kita mulai dari itu bahwa berat elemen yang diberikan dalam daftar yang akan disortir adalah konstan. Itu tidak akan berubah di antara iterasi. Jika ya, maka ... yah, itu masalah yang lebih besar.

Sebagai ilustrasi mari kita gunakan setumpuk kartu di mana kita ingin menimbang kartu wajah ke depan. weight(card) = card.rank. Ringkasnya, jika kita tidak tahu distribusi bobot memang O (n) satu kali.

Elemen-elemen ini disimpan dalam struktur yang diurutkan seperti modifikasi pada daftar lewati yang dapat diindeks sehingga semua indeks level dapat diakses dari node yang diberikan:

   1 10
 o ---> o -------------------------------------------- -------------> o Tingkat atas
   1 3 2 5
 o ---> o ---------------> o ---------> o ---------------- -----------> o Level 3
   1 2 1 2 5
 o ---> o ---------> o ---> o ---------> o ----------------- ----------> o Level 2
   1 1 1 1 1 1 1 1 1 1 1 1 
 o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o Tingkat bawah

Kepala 1 2 3 4 5 6 6 7 8 9 9 NIL
      Node Node Node Node Node Node Node Node Node

Namun dalam hal ini, setiap node juga 'memakan' ruang sebanyak beratnya.

Sekarang, ketika mencari kartu dalam daftar ini, seseorang dapat mengakses posisinya dalam daftar dalam waktu O (log n) dan mengeluarkannya dari daftar terkait dalam waktu O (1). Ok, mungkin bukan O (1), mungkin O (log log n) waktu (saya harus memikirkan ini lebih banyak lagi). Menghapus simpul ke-6 dalam contoh di atas akan melibatkan memperbarui keempat level - dan keempat level tersebut tidak tergantung pada berapa banyak elemen yang ada dalam daftar (tergantung pada bagaimana Anda mengimplementasikan level).

Karena bobot suatu elemen adalah konstan, seseorang dapat melakukannya sum -= weight(removed)tanpa harus melintasi struktur itu lagi.

Dan dengan demikian, Anda mendapat biaya satu kali O (n) dan nilai pencarian O (log n) dan penghapusan dari daftar biaya O (1). Ini menjadi O (n) + n * O (log n) + n * O (1) yang memberi Anda kinerja keseluruhan O (n log n).

Mari kita lihat ini dengan kartu, karena itulah yang saya gunakan di atas.

      10
3 teratas -----------------------> 4d
                                .
       3 7.
    2 ---------> 2d ---------> 4d
                  . .
       1 2. 3 4.
bot 1 -> Iklan -> 2d -> 3d -> 4d

Ini adalah dek yang sangat kecil dengan hanya 4 kartu di dalamnya. Seharusnya mudah untuk melihat bagaimana ini dapat diperluas. Dengan 52 kartu, struktur ideal akan memiliki 6 level (log ₂ (52) ~ = 6), meskipun jika Anda menggali daftar lompatan, itu pun dapat dikurangi menjadi angka yang lebih kecil.

Jumlah semua bobot adalah 10. Jadi Anda mendapatkan nomor acak dari [1 .. 10] dan 4 Anda berjalan dalam daftar lompatan untuk menemukan item yang ada di langit-langit (4). Karena 4 kurang dari 10, Anda berpindah dari level atas ke level kedua. Empat lebih besar dari 3, jadi sekarang kita berada di 2 berlian. 4 kurang dari 3 + 7, jadi kita pindah ke level bawah dan 4 kurang dari 3 + 3, jadi kita punya 3 berlian.

Setelah mengeluarkan 3 berlian dari struktur, struktur sekarang terlihat seperti:

       7
3 teratas ----------------> 4d
                         .
       3 4.
    2 ---------> 2d -> 4d
                  . .
       1 2. 4.
bot 1 -> Iklan -> 2d -> 4d

Anda akan mencatat bahwa node mengambil sejumlah 'ruang' sebanding dengan beratnya dalam struktur. Ini memungkinkan untuk pemilihan tertimbang.

Karena ini mendekati pohon biner seimbang, pencarian di ini tidak perlu berjalan di lapisan bawah (yang akan menjadi O (n)) dan alih-alih pergi dari atas memungkinkan Anda untuk dengan cepat melewatkan struktur untuk mencari tentang apa yang Anda cari untuk.

Sebagian besar ini malah bisa dilakukan dengan semacam pohon seimbang. Masalahnya ada penyeimbangan ulang struktur ketika sebuah node dihapus menjadi membingungkan karena ini bukan struktur pohon klasik dan rumah tangga untuk mengingat bahwa 4 berlian sekarang dipindahkan dari posisi [6 7 8 9] ke [3 4 5 6] mungkin lebih mahal daripada manfaat dari struktur pohon.

Namun, sementara daftar lompatan mendekati pohon biner dalam kemampuannya untuk melewatkan daftar dalam waktu O (log n), ia memiliki kesederhanaan bekerja dengan daftar tertaut sebagai gantinya.

Ini bukan untuk mengatakan bahwa mudah untuk melakukan semua ini (Anda masih perlu mengawasi semua tautan yang perlu Anda modifikasi ketika Anda menghapus suatu elemen), tetapi itu berarti hanya memperbarui seberapa banyak level yang Anda miliki dan tautannya. dari segalanya ke kanan pada struktur pohon yang tepat.