Bagaimana Pencarian Loteri Membawa Saya ke Kuasa PyTorch

pengenalan

Pada suatu ketika, anda mungkin pernah mendengar bahawa peluang anda untuk memenangi loteri a sangat tipis. Seperti semua perkara yang berkaitan dengan kebarangkalian, beberapa percubaan mungkin memihak kepada anda. Sekarang, jika anda mengambil bahagian dalam banyak loteri, peluang anda untuk memenangi satu akan menjadi lebih baik, bergantung pada bilangan lagi loteri yang anda sertai. Ini sama sekali bukan jaminan bahawa anda akhirnya akan menang, tetapi dengan pengedaran seragam , dan mengikut undang-undang bilangan besar (dalam kes ini bermakna bilangan loteri yang banyak), kita boleh mencapai kemungkinan yang lebih berkemungkinan besar.

Adalah penting untuk memahami bahawa setiap loteri baharu adalah bebas daripada yang lain, dan "nombor tiket" loteri yang sama boleh memenangi banyak loteri yang berbeza (mengikut undang-undang nombor besar). Anda juga mungkin tidak bernasib baik dan memilih nombor yang salah dalam setiap loteri, tidak kira berapa kali anda mencuba. Anda mempunyai dua pilihan sekarang:

1. Anda boleh mencuba nombor rawak setiap kali.
2. Anda boleh mencuba nombor sama setiap kali.

Secara teori (dan secara matematik), kedua-dua senario mempunyai kebarangkalian yang sama untuk berlaku. Walau bagaimanapun, senario 2 akan memberi anda sedikit kelebihan. Apabila bilangan kali menghampiri infiniti, setiap nombor akhirnya akan dipilih. Masalahnya ialah dengan senario 1, anda perlu mencuba lebih banyak kali dengan harapan nombor yang anda pilih pada masa itu sepadan dengan nombor yang menang. Dengan senario 2, anda pasti bahawa kerana percubaan cenderung kepada infiniti, nombor anda pada satu ketika akan "menang". Untuk catatan blog ini, kami akan menggunakan senario 2.

Jadi, adakah anda fikir anda boleh menjawab soalan ini sebelum saya memberitahu anda jawapannya?

"Jika semua loteri di sekeliling anda mempunyai slot untuk tepat 1 juta orang dan anda memilih tiket yang sama [x] untuk semua orang yang anda mainkan, berapa banyak loteri yang anda perlu bermain untuk akhirnya menjadi pemenang?" (Jangan ragu untuk mengulas tentang jawapan awal anda)

Jawapannya...

Kira-kira 14.4 juta kali.

Selebihnya catatan blog ini adalah tentang cara saya mencapai nilai itu, cara simulasi dilakukan dan beberapa kaveat. Perkara akan menjadi lebih teknikal dari sini.

Logik

Nombor tiket loteri 1 juta orang akan berjulat antara 1 - 1,000,000 (atau 0 - 999,999). Pemain hanya boleh memilih nombor dalam julat itu untuk setiap loteri, dan tiket yang menang hanya boleh dari julat itu. Pada asasnya, kita boleh katakan kita akan mempunyai set 1 juta nombor.

Mengambil kira hakikat bahawa pengguna boleh memilih mana-mana nombor dalam julat itu, kami perlu memenuhi syarat setiap item dalam set dipukul sekurang-kurangnya sekali. Ini kerana jika setiap nombor telah dipanggil sekurang-kurangnya sekali, ia akan meliputi sebarang kemungkinan nombor tiket yang boleh dipilih oleh pemain. Ini juga bermakna kami tidak mengambil berat tentang berapa kali setiap nombor dijalankan, menjadikan "set" struktur data Python yang ideal untuk digunakan untuk simulasi kami. Kami akan bermula dengan set kosong, dan mengisinya dengan nombor yang dijana secara rawak pada setiap lelaran sehingga set mengandungi setiap nombor dalam julat yang ditentukan. Memandangkan set Python tidak mengulangi nombor, kami tidak perlu risau tentang memastikan keunikan.

def calculate_lottery_chances(lottery_players_count):
  number_set = set()
  count = 0

  while len(number_set) < lottery_players_count:
    gen_number = random.randint(1, lottery_players_count)
    number_set.add(gen_number)
    count += 1

  return count

Untuk loteri 1,000,000 orang, panggilan fungsi akan kelihatan seperti: calculate_lottery_chances(1000000), dan ia akan mengembalikan bilangan percubaan loteri sebelum menang. Menyusun kod dengan cara ini menjadikannya sangat boleh dipanjangkan.

Masalahnya

Ringkasnya, punca masalah adalah "variasi". Kali pertama saya menjalankan fungsi itu, saya mendapat "13.1 juta" kali sebagai nilai saya. Saya menyiarkannya semula, dan mendapat sesuatu sepanjang garis 13.9 juta. Saya melakukan ini lebih banyak kali dan mendapat jawapan yang berbeza-beza - pada satu ketika, saya mendapat 15 juta. Sudah jelas bahawa saya perlu melakukan ini dan mencari purata. Mengikuti corak yang sedia ada setakat ini, saya menganggap bahawa kerana bilangan lelaran untuk meratakannya cenderung ke arah infiniti, saya akan lebih hampir mendapat satu jawapan yang boleh dipercayai. Terdapat keperluan untuk sesuatu yang boleh melakukan ini, dan melakukannya dengan pantas, dan itu membawa saya untuk menulis fungsi ini:

def average_over_n_times(function, function_arg, n):
  """
  This returns the average of the returned value of a function
  when it is called n times, with its (one) arg
  """
  total = 0
  for x in range(0, n):
    total += function(function_arg)

  return round(total/n)

Selepas itu, semuanya akan ditambal sebagai:

num_of_trials = average_over_n_times(calculate_lottery_chances, lottery_players_count, n)

Di mana "n" akan mewakili bilangan kali kepada purata hasil dengan. Ini, bagaimanapun, membawa masalah lain yang akan dibincangkan dalam bahagian seterusnya.

Apa yang sepatutnya "n"?

Semakin besar nilai n, semakin hampir kepada hasil "average-case". Walau bagaimanapun, memandangkan masih tiada perkara mutlak atau kepastian, melaksanakan siri tugasan ini terlalu banyak kali berhenti menjadi produktif. Saya mengatakan ini atas sebab berikut:

• Masa tidak terbatas, dan kita tidak boleh melakukan pengiraan ini selama-lamanya, bermakna akan sentiasa ada variasi (tidak kira betapa sedikit) setiap kali ia dijalankan, mengalahkan idea "mutlak".
• Sumber pengiraan adalah terhad.
• Salah satu andaian percubaan ini ialah "kerawak" yang dihasilkan oleh komputer boleh meniru realiti dengan tepat.
• Sama seperti masa jalan algoritma, magnitud yang lebih kecil berhenti sama pentingnya dengan magnitud yang lebih besar. Variasi kira-kira 100,000 tidak akan begitu ketara apabila berurusan dengan nilai yang lebih besar daripada 13,000,000.

Mengingat perkara ini, saya menguji "n" dengan nilai: 10, 20, 30, 50, 100, 1000 dan 5000 kali.

Di manakah PyTorch masuk?

Pada ketika ini, anda mungkin tertanya-tanya mengapa perkataan "PyTorch" dalam tajuk catatan blog tidak disebut. Nah, walaupun saya menyebut ujian n dengan nilai yang berbeza, ia bukan kod yang sama yang saya gunakan untuk semua ujian.

Ini adalah percubaan yang berat dari segi pengiraan, dan CPU saya bercakap dengan saya. Coretan kod yang saya kongsikan sebelum ini ditulis dalam satu fail yang mempunyai sifar kebergantungan pakej luaran, dan fail itu dijalankan dalam shell bash dengan arahan masa didahulukan untuk menjejaki masa pelaksanaan. Inilah rupa masa pelaksanaan apabila hanya menggunakan CPU:

n	Time (min and sec)
10	1m34.494s
20	3m2.591s
30	5m19.903s
50	10m58.844s
100	14m56.157s

Pada 1000, saya tidak dapat menjalankan program ini lagi. Saya tidak pasti sama ada ia pecah separuh jalan dan gagal menghentikan pelaksanaan, tetapi saya membatalkannya selepas 4 jam dan 57 minit. Terdapat beberapa faktor yang saya rasa mempengaruhi perkara ini, yang akan saya bincangkan dalam bahagian "kaveat". Bagaimanapun, bunyi kipas saya berbunyi, dan saya tahu saya mungkin telah menolak CPU komputer riba saya yang dikuasakan sederhana terlalu banyak. Saya enggan menerima kekalahan dan sambil memikirkan perkara yang boleh saya lakukan untuk sekurang-kurangnya menjalankan lelaran 4 digit, saya teringat sesuatu yang diberitahu oleh rakan saya yang bekerja dengan PyTorch kepada saya:

"GPU secara amnya lebih cekap dalam pengiraan intensif berbanding CPU"

PyTorch menggunakan GPU, menjadikannya alat yang sesuai untuk kerja itu.

Pemfaktoran semula

PyTorch akan digunakan untuk pengiraan untuk tujuan kami, jadi pemfaktoran semula kod calculate_lottery_chances() sedia ada bermakna menukar operasi berangka yang bergantung kepada CPU dan bertukar kepada struktur data PyTorch yang sesuai. Secara ringkasnya:

• Jenis data set() Python tidak lagi mencukupi.
• Fungsi Python randint() akan ditukar dengan PyTorch yang setara.
• Memandangkan jenis data set() tidak mencukupi, akan ada suis untuk menjana tensor sifar yang sepadan dengan saiz bilangan_pemain_loteri, dengan boolean untuk menunjukkan sama ada sesuatu nombor itu pernah menang atau tidak.

Faktor semula bagi mengira_peluang_loteri akan kelihatan seperti:

def calculate_lottery_chances(lottery_players_count):
  number_set = set()
  count = 0

  while len(number_set) < lottery_players_count:
    gen_number = random.randint(1, lottery_players_count)
    number_set.add(gen_number)
    count += 1

  return count

Saya menetapkan peranti saya sebagai "xpu" kerana komputer saya menggunakan GPU Intel Graphics, yang disokong oleh PyTorch.

Keluaran

Untuk memastikan GPU saya digunakan semasa pelaksanaan, saya membuka pengurus tugas Windows saya dan menavigasi ke bahagian "prestasi" sebelum menjalankan. Semasa berlari, saya melihat peningkatan ketara dalam penggunaan sumber GPU.
Untuk konteks, berikut ialah sebelum vs selepas:

Sebelum:

Perhatikan penggunaan GPU adalah pada 1%

Selepas:

Perhatikan penggunaan GPU adalah pada 49%

Untuk masa jalan untuk nilai n yang berbeza-beza, GPU adalah beberapa kali lebih pantas. Ia menjalankan nilai n di bawah 100 secara konsisten dalam masa kurang daripada seminit, dan dapat mengira nilai n pada 5000 (lima ribu!)

Berikut ialah jadual masa jalan menggunakan GPU:

n	Time (min and sec)
10	0m13.920s
20	0m18.797s
30	0m24.749s
50	0m34.076s
100	1m12.726s
1000	16m9.831s

Untuk mengetahui betapa besarnya jurang prestasi antara operasi GPU dan CPU untuk percubaan ini, berikut ialah visualisasi data untuk difikirkan:

Paksi-x dihadkan pada 100 kerana saya tidak lagi boleh mendapatkan output "tepat pada masa" secara realistik daripada CPU, sekali gus tidak meninggalkan ruang untuk dibandingkan dengan GPU. Melaksanakan eksperimen dengan nombor dalam julat 1000 - 5000 memberi saya kira-kira "14.4 juta kali" sebagai hasilnya, lebih kerap daripada tidak. Begitulah saya mendapat jawapan dari tadi.

Kaveat

Percubaan ini membuat andaian dan bergantung pada cara tertentu untuk melakukan sesuatu. Selain itu, pengalaman saya dengan PyTorch berpotensi bermakna terdapat pendekatan yang lebih cekap. Berikut ialah beberapa faktor yang perlu dipertimbangkan bahawa mungkin mempengaruhi sama ada ketepatan penemuan saya atau masa pelaksanaan:

1. Saya membuat andaian halus bahawa rawak yang dijana oleh komputer meniru rawak dalam kehidupan sebenar (dunia fizikal).
2. Semasa saya menukar sedikit logik untuk menggunakan PyTorch, selebihnya kod masih bergantung pada CPU. Sebagai contoh, dalam fungsi average_over_n_times(), ada kemungkinan bahawa kedua-dua penambahan dalam gelung dan purata mungkin mendapat manfaat daripada setara PyTorch. Saya mengesyaki akan ada peningkatan prestasi.
3. Saya tidak pasti tentang kesan saiz_kelompok yang saya gunakan pada ketepatan dan prestasi.
4. Semua ujian CPU dan GPU telah dilakukan dengan PC saya dipalamkan, untuk membolehkan mesin berfungsi pada tahap terbaik. Menjalankannya dengan peranti menggunakan kuasa bateri mungkin melihat masa jalan yang lebih lama.
5. CUDA PyTorch mungkin mempunyai kelebihan berbanding "XPU", ​​tetapi PC saya tidak mempunyai sokongan untuk yang pertama.
6. Saya mengelak daripada membiarkan PC saya "tidur" semasa ujian. Ujian mungkin mengambil masa lebih lama untuk dijalankan jika komputer anda tidur.

Akhir sekali, saya ingin menyatakan bahawa ini adalah kali pertama saya menggunakan PyTorch untuk apa-apa sahaja, dan saya agak kagum dengan persembahannya.

Kesimpulan

Apabila saya pergi ke lubang arnab dengan ini, saya tidak menjangkakan untuk melihat keuntungan seperti itu dalam prestasi. Saya mempelajari idea di sebalik tensor dan beberapa perkara tentang mekanisme sokongan di sebalik tugasan yang lebih kompleks dari segi pengiraan. Anda mempunyai kebebasan untuk menggunakan, meniru atau mengubah suai coretan kod mengikut kehendak anda.

Terima kasih kerana memanjakan saya, dan saya harap anda seronok membaca.

Sehingga lain kali,

Sekian. ?

Atas ialah kandungan terperinci Bagaimana Pencarian Loteri Membawa Saya ke Kuasa PyTorch. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!