Trilogi Perkasa: Proyek Euler, Paradoks Simpson, dan DataFrames.jl – Beragampengetahuan

Oleh: Blog Bogumił Kamiński

Repost dari:

Baru-baru ini, mengikuti umpan balik pengguna, saya mulai memecahkan lebih banyak teka-teki di blog saya.
Untuk memilih masalah hari ini, saya pergi ke halaman Project Euler, halaman ini
menyediakan ratusan teka-teki yang sangat keren. Saya ingin menghindari berurusan dengan beberapa
masalahnya mudah, jadi saya memutuskan untuk memilih teka-teki pertama dari daftar kemungkinan
kurang dari 1000 orang telah memecahkannya. Ini membawa saya ke masalah 236.

Saya heran masalah ini adalah contoh paradoks Simpson,
jadi semoga jika Anda seorang ilmuwan data, Anda akan menganggapnya menarik.

Secara umum, Project Euler tidak merekomendasikan memposting solusi untuk masalah
diberikan pada halaman tersebut. Untuk alasan ini, dengan sengaja, saya tidak mengoptimalkan kode saya
dan solusinya adalah kekerasan (untuk mendorong Anda menemukan solusi yang elegan;
solusi yang disajikan membutuhkan beberapa menit untuk menghasilkan hasil).
Juga, saya memutuskan untuk menunjukkan kodenya, tetapi bukan nilai dari solusi akhir
(untuk mendorong Anda mencoba menyelesaikannya).

Jadi mengapa menurut saya menarik untuk membaca artikel ini? Saya memecahkan teka-teki itu
terutama menggunakan DataFrames.jl, jadi saya harap Anda dapat menemukan beberapa data yang berguna
pola berantakan saat membacanya.

Kode yang disajikan dijalankan di Julia 1.8.2, DataFrames.jl 1.4.3 dan
DataFramesMeta.jl 0.12.0. Solusinya membutuhkan 32GB RAM (sekali lagi, di atas
tujuan; jika Anda memiliki lebih sedikit RAM, saya sarankan untuk mengoptimalkan kode saya sebagai bagian dari
tantangan Proyek Euler).

Paradoks Simpson adalah fenomena di mana data dianalisis secara berkelompok
mewakili arah hubungan yang berbeda dari saat Anda menganalisis data
setelah mensintesisnya.

Untuk menunjukkan kepada Anda paradoks dalam praktiknya, izinkan saya memperkenalkan
Masalah Project Euler 236. Deskripsi disalin dari Project Euler
Halaman:

Pemasok ‘A’ dan ‘B’ telah memasok barang mewah dalam jumlah berikut
Hambatan pasar:

Product             'A'     'B'
Beluga Caviar       5248     640
Christmas Cake      1312    1888
Gammon Joint        2624    3776
Vintage Port        5760    3776
Champagne Truffles  3936    5664

Meskipun pemasok telah berusaha sangat keras untuk mengirimkan barang mereka dalam kondisi sempurna,
pasti ada beberapa kerusakan – yaitu produk rusak.

Vendor membandingkan kinerjanya menggunakan dua jenis statistik:

• Lima tingkat kegagalan per produk per pemasok sama dengan
  produk rusak dibagi dengan jumlah produk yang dipasok, untuk masing-masing
  masing-masing lima produk.
• Tingkat kegagalan keseluruhan untuk setiap pemasok sama dengan total
  produk yang rusak dibagi dengan jumlah total produk yang dipasok oleh orang tersebut
  pemasok.

Yang mengejutkan mereka, para pemasok menemukan bahwa masing-masing dari kelima produk tersebut
tingkat kegagalan yang lebih buruk (lebih tinggi) untuk ‘B’ daripada ‘A’ dengan faktor yang sama
(tingkat kerusakan), Saya>1; Namun, secara paradoks, rampasan total
rasio untuk ‘A’ lebih buruk daripada ‘B’, juga dengan satu faktor Saya.

Berapa kemungkinan nilai terbesar dari Saya?

Situasi ini adalah contoh paradoks Simpson. Pemasok dalam grup
‘B’ memiliki lebih banyak kerusakan daripada pemasok ‘A’, namun situasi keseluruhannya demikian
balik. Sebelum kita mencoba memecahkan teka-teki, mari kita periksa
situasinya mungkin.

Asumsikan bahwa jumlah kerusakan per produk dan pemasok adalah sebagai berikut:

Product             'A'     'B'
Beluga Caviar       2478    630
Christmas Cake        16     48
Gammon Joint          33     99
Vintage Port         180    246
Champagne Truffles    23     69

Kami dapat memeriksa bahwa persentase kerusakan kira-kira:

Product             'A'     'B'
Beluga Caviar       47.22%  98.44%
Christmas Cake       1.22%   2.54%
Gammon Joint         1.26%   2.62%
Vintage Port         3.13%   6.51%
Champagne Truffles   0.58%   1.22%

Seperti yang Anda lihat pemasok ‘B’ memiliki tingkat kegagalan 2 kali lebih tinggi di atas
setiap produk (Anda dapat memeriksa apakah persentase kegagalannya sama untuk
semua produk dan kira-kira sama dengan 2,085.

Sekarang mari kita periksa sintesisnya. Pemasok ‘A’ mengirimkan 18880 produk di dalamnya
2730 rusak. Pemasok ‘B’ telah mengirimkan 15744 produk termasuk 1092
rusak. Jadi persentase kegagalan agregat untuk pemasok ‘A’ adalah sekitar
14,46% dan untuk vendor ‘B’ 6,94%. Menariknya, pemasok ‘A’ memiliki lebih dari dua
tingkat kegagalan berkali-kali lebih tinggi daripada pemasok ‘B’ (tingkat yang menakjubkan
persentase kerusakan yang sama seperti di atas, tetapi berlawanan arah).

Sekarang mari kita pecahkan teka-teki dan temukan rasio terbesar yang mungkin Saya rusak
persentase antara pemasok ‘A’ dan ‘B’ yang memenuhi persyaratan
Teka-teki.

Mulailah dengan mengunduh paket dan data DataFramesMeta.jl yang diperlukan:

julia> using DataFramesMeta

julia> const pv = [(a=5248, b=640),
                   (a=1312, b=1888),
                   (a=2624, b=3776),
                   (a=5760, b=3776),
                   (a=3936, b=5664)]
5-element Vector{NamedTuple{(:a, :b), Tuple{Int64, Int64}}}:
 (a = 5248, b = 640)
 (a = 1312, b = 1888)
 (a = 2624, b = 3776)
 (a = 5760, b = 3776)
 (a = 3936, b = 5664)

julia> const pt = (a=sum(x -> x.a, pv), b=sum(x -> x.b, pv))
(a = 18880, b = 15744)

Itu pv vektor yang berisi jumlah produk yang dikirim oleh pemasok ‘A’ dan
‘Pita pt tupel memiliki nama yang menyimpan totalnya.

Kita tahu bahwa untuk setiap kombinasi pemasok produk, tingkat kegagalan setidaknya 1.
Menggunakan allcombinations fungsi yang kita buat kerangka data berisi semua
komponen yang mungkin dari jumlah pembusukan untuk setiap produk dan untuk total, dan
menyimpannya di dfs vektor:

julia> dfs = [allcombinations(DataFrame, a=1:p.a, b=1:p.b) for p in pv];

julia> push!(dfs, allcombinations(DataFrame, a=1:pt.a, b=1:pt.b));

julia> nrow.(dfs)
6-element Vector{Int64}:
   3358720
   2477056
   9908224
  21749760
  22293504
 297246720

Kita dapat melihat bahwa jumlah opsinya besar, tetapi tampaknya sesuai
komputer saat ini dapat menangani.

Sebelum kita melanjutkan, mari kita lihat isi dari salah satu data frame
pastikan strukturnya seperti yang diharapkan:

julia> dfs[1]
3358720×2 DataFrame
     Row │ a      b
         │ Int64  Int64
─────────┼──────────────
       1 │     1      1
       2 │     2      1
       3 │     3      1
    ⋮    │   ⋮      ⋮
 3358718 │  5246    640
 3358719 │  5247    640
 3358720 │  5248    640
    3358714 rows omitted

Semua terlihat bagus.

Sekarang untuk setiap kombinasi kita perlu menghitung Saya tingkat, ingat bahwa untuk
total itu harus dibalik. Juga, kami ingin mengumpulkan kolom :a dan
:b ke dalam kolom yang berisi tupel nilai yang disimpan di dalamnya, sebagaimana mestinya
lebih mudah untuk bekerja dengan data itu nanti dan hanya menyimpan opsi itu Saya Menjadi
lebih besar dari 1. Kita dapat dengan mudah melakukan kedua tugas menggunakan do .macro
DataFramesMeta.jl:

julia> ms = Function[(x, y) -> (y * p.a) // (x * p.b) for p in pv];

julia> push!(ms, (x, y) -> (x * pt.b) // (y * pt.a));

julia> foreach(dfs, ms) do df, m
           @rselect!(df, :m = m(:a, :b), :ab = (:a, :b))
           @rsubset!(df, :m > 1)
       end

Perhatikan bahwa untuk setiap kerangka data, saya telah menetapkan fungsi kalkulasinya sendiri Saya
menskalakan dan menyimpannya ms vektor.

Sekali lagi, mari kita periksa bagaimana bingkai data terlihat setelah transformasi:

julia> nrow.(dfs)
6-element Vector{Int64}:
   1681600
   1238224
   4953504
  10875840
  11145840
 148621760

julia> dfs[1]
1681600×2 DataFrame
     Row │ m           ab
         │ Rational…   Tuple…
─────────┼─────────────────────────
       1 │      41//5  (1, 1)
       2 │     41//10  (2, 1)
       3 │     41//15  (3, 1)
    ⋮    │     ⋮            ⋮
 1681598 │ 5248//5245  (5245, 640)
 1681599 │ 2624//2623  (5246, 640)
 1681600 │ 5248//5247  (5247, 640)
               1681594 rows omitted

Kami menyadari bahwa kami telah mengurangi jumlah baris sekitar 50% (seperti yang diharapkan). amati itu
menggunakan // operator dalam fungsi komputasi Saya kita mendapatkan bilangan rasional
Alhasil perhitungan kita benar, tidak ada pembulatan.

Sekarang mari kita kelompokkan bingkai datanya Saya nilai skala (ingat kita mau
solusi di mana rasionya sama untuk semua produk dan untuk total):

julia> gdfs = groupby.(dfs, :m);

julia> length.(gdfs)
6-element Vector{Int64}:
  1021210
   753076
  3012264
  6612288
  6777256
 90353608

Kami menemukan bahwa kami memiliki beberapa kelompok. Namun, kami hanya tertarik pada kasus
di mana Saya cocok di semua tabel, jadi sekarang mari kita cari kandidat tersebut Saya
nilai:

julia> key_tuples = [@combine(gdf, :mt = (first(:m),)).mt for gdf in gdfs];

julia> match_keys = intersect(key_tuples...);

julia> sort!(match_keys, rev=true)
7040-element Vector{Tuple{Rational{Int64}}}:
 (1230//1,)
 (738//1,)
 (615//1,)
 ⋮
 (1230//1229,)
 (1476//1475,)
 (3895//3894,)

Untungnya, kami melihat bahwa hanya ada 7040 nilai yang mungkin dari Saya tersedia.
Saya mengurutkan kunci yang cocok dalam urutan menurun untuk mendapatkan yang tertinggi Saya
nilai pertama.

Anda mungkin bertanya-tanya mengapa saya menggunakan @combine untuk mengubah rasio menjadi tupel
pertahankan faktor dengan rasio ini. alasannya adalah GroupedDataFrame
mendukung pencarian grup cepat berdasarkan nilai variabel grup dan salah satu
opsi pencarian semacam itu adalah dengan melewatkan cache itu. Jadi kita bisa
membuat groups vektor menyimpan vektor 6 elemen dari kerangka data
mewakili lima produk dan pencocokan total Saya:

julia> groups = [[gdfs[i][key] for i in 1:6] for key in match_keys];

Perhatikan bahwa operasi di DataFrames.jl ini hemat memori. indeks pada
satu GroupedDataFrame untuk mendapatkan pengembalian grup yang unik a SubDataFrameyang
adalah tampilan dari kerangka data sumber.

Seperti sebelumnya, mari kita lihat hasilnya:

julia> groups[1]
6-element Vector{SubDataFrame{DataFrame, DataFrames.Index, Vector{Int64}}}:
 4×2 SubDataFrame
 Row │ m          ab
     │ Rational…  Tuple…
─────┼─────────────────────
   1 │   1230//1  (1, 150)
   2 │   1230//1  (2, 300)
   3 │   1230//1  (3, 450)
   4 │   1230//1  (4, 600)
 1×2 SubDataFrame
 Row │ m          ab
     │ Rational…  Tuple…
─────┼──────────────────────
   1 │   1230//1  (1, 1770)
 2×2 SubDataFrame
 Row │ m          ab
     │ Rational…  Tuple…
─────┼──────────────────────
   1 │   1230//1  (1, 1770)
   2 │   1230//1  (2, 3540)
 1×2 SubDataFrame
 Row │ m          ab
     │ Rational…  Tuple…
─────┼──────────────────────
   1 │   1230//1  (3, 2419)
 3×2 SubDataFrame
 Row │ m          ab
     │ Rational…  Tuple…
─────┼──────────────────────
   1 │   1230//1  (1, 1770)
   2 │   1230//1  (2, 3540)
   3 │   1230//1  (3, 5310)
 12×2 SubDataFrame
 Row │ m          ab
     │ Rational…  Tuple…
─────┼────────────────────────
   1 │   1230//1  (1475, 1)
   2 │   1230//1  (2950, 2)
   3 │   1230//1  (4425, 3)
   4 │   1230//1  (5900, 4)
   5 │   1230//1  (7375, 5)
   6 │   1230//1  (8850, 6)
   7 │   1230//1  (10325, 7)
   8 │   1230//1  (11800, 8)
   9 │   1230//1  (13275, 9)
  10 │   1230//1  (14750, 10)
  11 │   1230//1  (16225, 11)
  12 │   1230//1  (17700, 12)

Jadi kemungkinan tertinggi Saya rasionya 1230. Tapi apakah itu valid? Catatan
bahwa kami belum memeriksa suatu kondisi. Kerusakan total (salah satunya
opsi dalam kerangka data terakhir yang ditunjukkan di atas) harus menjadi jumlah tahun ini
kerusakan pada setiap produk.

Jadi kita perlu membuang ini Saya tingkat di mana hal ini tidak mungkin. Untuk mencapai
ini kita definisikan test_options Fungsi bantuan:

julia> function test_options(inv, outs)
           v = copy(inv[1])
           for i in 2:4
               s = Set{Tuple{Int32, Int32}}()
               for a in v, b in inv[i]
                   push!(s, a .+ b)
               end
               v = collect(s)
           end
           for a in v, b in inv[5]
               a .+ b in outs && return true
           end
           return false
       end
test_options (generic function with 1 method)

Fungsi ini membutuhkan dua argumen inv yang merupakan vektor dari :ab rusak
dari lima produk dan outs yang mana Set dalam kerusakan total.

Fungsinya bekerja sebagai berikut. Kami memeriksa jumlah total yang mungkin dalam setahun
produk rusak yang mungkin kami terima (kami lakukan berulang-ulang, mulai dari produk satu,
lalu tambahkan opsi untuk produk berurutan). Kemudian kita periksa apakah totalnya
Kerusakan untuk kedua pemasok dapat ditemukan di outs koleksi (dan itu
alasan ini adalah Set, karena suite mendukung pencarian cepat). Jika ini masalahnya
kami kembali true. Jika tidak, kami akan kembali false.

Perhatikan bahwa trik dalam fungsi ini, untuk membuatnya memungkinkan secara komputasi
(cukup bagus lagi – solusinya kurang maksimal, ini challenge buat kamu),
adalah perhitungan inkremental dari kemungkinan (a, b) jumlah produk dan
kurangi opsi yang memungkinkan setelah setiap pengulangan menjadi satu Set. Dari Julia
Perspektif pemrograman melibatkan dua baris kode. Pertama adalah
v = copy(inv[1]) dan yang kedua adalah v = collect(s). Mereka membuat fungsional
tipe stabil, karena mereka memastikan itu v variabel yang kita ulangi banyak
dalam fungsi yang selalu dikaitkan dengan objek yang memiliki
Vector{Tuple{Int, Int}} ketik yang dapat disimpulkan oleh kompiler.

Silakan gunakan gunakan test_options memiliki fungsi penyaring Saya nilai-nilai itu
memenuhi persyaratan kuis kami:

julia> answer = [g[1].m[1] for g in groups
                 if test_options([g[i].ab for i in 1:5], Set(g[6].ab))];

julia> first(answer);

Karena sudah kami atur Saya dalam urutan menurun di atas first(answer) adalah solusi
untuk kuis kami. Saya baru saja memesan ; di akhir semua ekspresi untuk menyembunyikannya.

Meski begitu, izinkan saya menunjukkan data yang diungkapkan oleh penulis teka-teki di atas
Masalah Project Euler halaman 236:

julia> length(answer)
35

julia> last(answer)
1476//1475

Memang, kami menemukan bahwa ada 35 nilai unik dari Saya itu mungkin
dan yang terkecil adalah 1476/1575, jadi kemungkinan besar
kode bekerja dengan benar.

Saya harap Anda menikmati teka-teki, contoh dan solusi paradoks Simpson
gunakan DataFrames.jl. Jika Anda ingin menguji keterampilan pemrograman Anda, saya
mendorong Anda untuk meningkatkan solusi saya (kode efisien yang memecahkan teka-teki
berjalan kurang dari 1 detik).

Terkait