Dengan bashing Python baru-baru ini , inilah upaya untuk menunjukkan kekuatan Python. Tantangan Anda adalah menulis sebuah program yang menghitung faktorial angka setinggi mungkin dalam 10 detik.n
Skor Anda akan (highest n for your program on your machine)/(highest n for my program on your machine)
Aturan
- Anda harus menghitung solusi integer yang tepat. Karena faktorial akan jauh lebih tinggi daripada apa yang dapat ditampung dalam integer 64 bit yang tidak ditandatangani, Anda dapat menggunakan string jika bahasa Anda tidak mendukung bilangan bulat besar
- Celah standar dilarang. Khususnya, Anda tidak dapat menggunakan sumber daya eksternal apa pun.
- Hanya bagian perhitungan (ini termasuk waktu untuk setiap penyelesaian masalah menggunakan string) menambah total waktu yang seharusnya di bawah 10 detik rata-rata.
- Hanya program berulir tunggal.
- Anda harus menyimpan output dalam bentuk yang mudah dicetak (karena pencetakan membutuhkan waktu) (lihat program saya di bawah), string, variabel, array karakter, dll.
EDIT:
- Program Anda harus memberikan hasil yang benar untuk semua
n
:1 <= n <= (your highest n)
EDIT2:
- Saya benci mengatakan ini secara eksplisit tetapi menggunakan fungsi faktorial bawaan bahasa Anda berada di bawah celah standar http://meta.codegolf.stackexchange.com/a/1078/8766 Maaf, Mathematica and Sage Maaf
Program saya
from __future__ import print_function
import time
def factorial( n ):
return reduce( ( lambda x , y : x * y ) , xrange( 1 , n + 1 ) , 1 )
start = time.clock()
answer = factorial( 90000 )
end = time.clock()
print ( answer )
print ( "Time:" , end - start , "sec" )
Kemenangan skor tertinggi. Sebagai catatan, kode saya dapat mengatur n = 90000
dalam beberapa 9.89
detik pada Pentium 4 3,0 GHz
EDIT: Can semua orang silahkan menambahkan skor bukan hanya tertinggi n . Hanya yang tertinggi n
tidak memiliki arti karena tergantung pada perangkat keras Anda. Tidak mungkin memiliki kriteria kemenangan yang obyektif sebaliknya. Jawaban ali0sha melakukan ini dengan benar.
Kami punya pemenang. Saya tidak menerima jawaban java /codegolf//a/26974/8766 karena semacam rok dekat dengan http://meta.codegolf.stackexchange.com/a/1080/8766
sumber
operator.mul
fungsi lambdafactorial(Inf)
:, kembaliInf
dalam sepersekian detik.Jawaban:
C ++ dengan GMP, skor = 55,55 (10.000.000 / 180.000)
sumber
Python 2.7
42.575 = (6.812.000 / 160.000) kira-kira
Kode:
Uji:
Keluaran:
Bagaimana itu bekerja:
Penggandaan yang lebih besar membutuhkan lebih banyak waktu, jadi kami ingin melakukan penggandaan sekecil mungkin. Ini terutama berlaku di Python di mana untuk angka yang lebih sedikit
2^64
kita menggunakan perangkat keras aritmatika, dan di atas itu kita menggunakan perangkat lunak. Jadi, dim(L)
, kita mulai dengan daftarL
; jika panjangnya aneh, kami menghapus satu nomor dari pertimbangan untuk membuatnya lebih lagi. Lalu kita kalikan elemen1
dengan elemen-2
, elemen3
dengan-4
, dll, sehinggaPendekatan ini memastikan kami menggunakan aritmatika perangkat keras selama mungkin, berikut ini kami beralih ke pustaka aritmatika gmc yang efisien.
Dalam
fac2
, kami mengambil pendekatan pembagian dan menaklukkan yang lebih klasik juga, di mana kami membagi setiap kelipatan dari 2 dan menggeser mereka pada akhirnya untuk meningkatkan kinerja sepele. Saya sudah memasukkannya di sini karena biasanya sekitar 0,5% lebih cepat daripadafac1
.Versi Golf
fac1
(karena saya bisa), 220Bsumber
gmpy2
? $ python Python 2.7.3 (default, 27 Feb 2014, 19:58:35) [GCC 4.6.3] di linux2 Ketik "help", "hak cipta", "kredit" atau "lisensi" untuk informasi lebih lanjut. >>> dari gmpy2 import mpz Traceback (panggilan terakhir terakhir): File "<stdin>", baris 1, di <module> ImportError: Tidak ada modul bernama gmpy2 >>>while len(L): ...
bukanwhile len(L)>1: ...
?Jawa - 125,15 (21,400,000 / 171,000)
Juga tanpa malu-malu disalin dari repo Peter Luschny's Github (terima kasih @ semi-ekstrinsik) dan dilisensikan di bawah lisensi MIT, ini menggunakan algoritma "prima faktorisasi bersarang kuadrat" seperti yang diusulkan oleh Albert Schönhage et al. (Menurut halaman deskripsi algoritma faktorial Luschny ).
Saya sedikit mengadaptasi algoritma untuk menggunakan BigInteger Java dan tidak menggunakan tabel pencarian untuk n <20.
Dikompilasi dengan gcj, yang menggunakan GMP untuk implementasi BigInteger, dan dijalankan di Linux 3.12.4 (Gentoo), pada Core i7 4700MQ di 2.40GHz
sumber
gcj -O3 --main=PrimeSieveFactorialSchoenhage PrimeSieveFactorialSchoenhage.java -o pf_nest_square_fact
Python 3, n = 100000
Perubahan algoritma sederhana adalah semua yang diperlukan untuk meningkatkan kode sampel hingga 10.000.
Jelas bukan jawaban yang paling kreatif, tetapi sebenarnya hanya ada satu cara untuk melakukan faktorial ....
sumber
Perl + C, n = sekitar 3 juta
Di sini saya menggunakan perpustakaan Math :: BigInt :: GMP yang tersedia di CPAN, yang memberikan peningkatan kecepatan besar untuk objek inti Math :: BigInt Perl.
Ingatlah bahwa komputer saya mungkin sedikit lebih lambat dari milik Anda. Menggunakan skrip Python asli Anda, saya hanya dapat menghitung
factorial(40000)
dalam 10 detik;factorial(90000)
membutuhkan waktu lebih lama. (Saya menekan Ctrl + C setelah satu menit.) Pada perangkat keras Anda, menggunakan Math :: BigInt :: GMP, Anda mungkin dapat menghitung faktorial 5 juta atau lebih dalam waktu kurang dari 10 detik.Satu hal yang mungkin Anda perhatikan adalah bahwa meskipun faktorial dihitung sangat cepat, mencetak hasilnya sangat lambat, memakan waktu sekitar tiga kali lebih lama dari perhitungan aslinya. Ini karena GMP secara internal menggunakan representasi biner daripada desimal, dan mencetaknya memerlukan konversi biner ke desimal.
sumber
Math::BigInt
Python 2.7
5.94 = 1'200'000 / 202'000
Buatlah penggunaan relatif mudah penggandaan banyak kelompok dengan jumlah kecil dan kemudian mengalikannya dibandingkan dengan jumlah besar penggandaan yang melibatkan jumlah besar.
sumber
C #: 0,48 (77.000 / 160.000)
Saya tidak senang dengan ini.
Apakah C # itu lambat?
Tapi ini adalah entri saya.
Ketika n = 77000 dibutuhkan
00:00:09:8708952
untuk menghitung.Saya sedang menjalankan dalam mode Rilis, di luar Visual Studio, menggunakan Core i3-2330M @ 2.2GHz.
Sunting: Karena saya tidak melakukan sesuatu yang cerdas, saya menerima hasil itu. Mungkin .NET Framework 4.5 adalah addind overhead (atau BigInteger tidak secepat itu).
sumber
n
zero approached by
operator untuk membuatnya lebih cantik (seperti mulai dengann = ... + 1
kemudian lakukanwhile (0 <-- n) result *= n;
)bc, skor = 0,19
Apa-apaan ini, inilah penantang saya untuk "Berapa banyak yang bisa Anda gandakan secara perlahan?"
bc adalah "Bahasa kalkulator presisi arbitrer", tapi sayangnya agak lambat:
Dalam sekitar 10 detik pada pertengahan 2012 MacBook Pro saya (2,3 GHz Intel Core i7) jawaban python referensi dapat menghitung 122000 !, tetapi skrip bc ini hanya dapat menghitung 23600 !.
Sebaliknya 10.000! membutuhkan 1,5 detik dengan skrip referensi python, tetapi skrip bc membutuhkan 50 detik.
Oh sayang.
sumber
read()
, jadi saya berlaritime sed 's/read()/28000/' factorial.bc | bc
.Bash: skor = 0,001206 (181/150000)
Saya mencuri fungsi matematika dari Rosettacode - Perkalian panjang yang tidak saya analisis atau coba optimalkan.
Anda bebas mengubah algoritme atau mencoba metode pemisahan string yang berbeda.
sumber
Python 3, lanjutan algo oleh Peter Luschny: 8.25x (1 280 000/155 000)
Tanpa malu-malu disalin dari Peter Luschny,
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm ,
yang menyediakan kode ini di bawah lisensi "Creative Commons Attribution-ShareAlike 3.0" lisensi.
Ini sebenarnya adalah algoritma yang cukup canggih, menggunakan sesuatu yang disebut "faktor ayunan" dan daftar bilangan prima. Saya menduga itu bisa lebih cepat jika memang seperti banyak jawaban lain dan melakukan sebagian besar perkalian dengan bilangan bulat 32 bit.
sumber
Jawa - 10.9
n = 885000
Mergesort-y.
BigInteger
Itu lambat.Rekomendasi untuk perpustakaan Java integer berkecepatan tinggi yang sewenang-wenang? : P
sumber
C ++ (spesifik x86_64) - 3.0 (390000/130000)
(mudah dibawa ke x86-32, porting ke arsitektur lain menyiratkan kehilangan kecepatan yang signifikan)
Inilah implementasi mikro dari aritmatika panjang saya sendiri.
Perhitungannya sendiri membutuhkan waktu 10 detik, dan sementara hasilnya dalam bentuk yang mudah dicetak (lihat
operator<<
kelebihannya), dibutuhkan waktu lebih lama untuk mencetaknya.sumber
g++ -O2 factorial.cc -o factorial
dan skor 3,90 = 382000 / 98000.r
peningkatan. Jika demikian, dan Anda dapat melakukan lebih tinggir
dalam 10 detik, maka skor Anda turun.Python 3: 280000/168000
Waktu menjalankan program Anda: antara
9.87585953253
dan10.3046453994
. Waktu menjalankan program saya: tentang10.35296977897559
.Saya membaca jawaban ini di cs.SE dan memutuskan untuk mencoba mengimplementasikannya dengan Python. Namun, saya tidak sengaja menemukan itu
n! = (⌊n / 2⌋)! * 2**(⌊n / 2⌋) * n!!
(catatan:!!
adalah faktorial ganda ). Jadi saya mengubahnya menjadi bentuk non-rekursif.Komentar menunjukkan upaya saya untuk menghindari penghitungan ulang faktorial ganda, tetapi saya menemukan bahwa menyimpan setiap nilai terlalu mahal karena memori membuat komputer saya berjalan lebih lambat. Saya dapat meningkatkan ini dengan hanya menyimpan apa yang dibutuhkan.
Anehnya, saya menerapkan perkalian naif langsung di Python 3, dan itu lebih baik daripada program Anda:
n = 169000
dalam 10 detik .:sumber
Ruby 2.1
skor = 1,80 = 176_000 / 98_000
EDIT: ditingkatkan dari
1,35 = 132_000 / 98_000Saya mengambil ide dari algoritma faktorial GMP . Program ini menggunakan perpustakaan standar untuk menghasilkan bilangan prima. Ruby adalah pilihan yang buruk karena multiplikasi tampaknya lebih lambat di Ruby daripada di Python.
Ya, biner
ruby 2.1.0p0 (2013-12-25 revision 44422) [x86_64-openbsd]
tautan saya terhadap GMP. Ruby 2.1 menambahkan fitur untuk menggunakan GMP untuk multiplikasi besar, tetapi tampaknya masih lebih lambat dari Python 2.7.sumber
Julia - Skor = 15.194
Memanfaatkan pendekatan yang sama persis dengan program referensi ... yaitu,
Jadi ia menggunakan mengurangi, operasi perkalian biner dasar, dan rentang (dalam hal ini, menggunakan besar (n) untuk memaksa perhitungan dilakukan di BigInt daripada Int64). Dari ini, saya mengerti
Di komputer saya, dengan program referensi berjalan dengan input 154000, saya mendapatkan
Time: 10.041181 sec
output (jalankan menggunakanpython ./test.py
, di mana test.py adalah nama file yang berisi kode referensi)sumber
tcl, 13757
Jawaban saya adalah memeriksa batas tcl.
Baris pertama hanya untuk mengatur parameter input:
Yang lain adalah algoritma itu sendiri:
Saya menguji kode saya di http://rextester.com/live/WEL36956 ; Jika saya membuat n lebih besar, saya mendapatkan SIGKILL; mungkin n bisa menjadi lebih besar pada penerjemah tcl lokal, yang tidak saya miliki.
sumber