Seorang pewawancara baru-baru ini bertanya kepada saya pertanyaan ini: diberi tiga variabel boolean, a, b, dan c, kembalikan benar jika setidaknya dua dari tiga itu benar.
Solusi saya sebagai berikut:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
Dia mengatakan bahwa ini dapat ditingkatkan lebih lanjut, tetapi bagaimana caranya?
java
boolean
boolean-logic
pengguna282886
sumber
sumber
atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou)
Jawaban:
Daripada menulis:
Menulis:
Adapun ekspresi itu sendiri, kira-kira seperti ini:
atau ini (mana yang menurut Anda lebih mudah dipahami):
Tes
a
danb
tepat sekali, danc
paling banyak sekali.Referensi
sumber
return hasGoodAttendance ? (passedCoursework || passed Exam) : (passedCoursework && passedExam)
, itu terlihat baik bagi saya.atLeastTwo(hasgoodAttendance, passedCoursework, passedExam)
. Gagasan "setidaknya 2 bools benar" cukup generik sehingga layak digunakan.Hanya demi menggunakan XOR untuk menjawab masalah yang relatif lurus ke depan ...
sumber
Mengapa tidak menerapkannya secara harfiah? :)
Dalam C Anda bisa menulis
a+b+c >= 2
(atau!!a+!!b+!!c >= 2
menjadi sangat aman).Menanggapi perbandingan TofuBeer tentang bytecode java, berikut ini adalah tes kinerja sederhana:
Ini mencetak yang berikut ini di mesin saya (menjalankan Ubuntu pada Intel Core 2 + sun java 1.6.0_15-b03 dengan HotSpot Server VM (14.1-b02, mode campuran)):
Iterasi pertama dan kedua:
Iterasi selanjutnya:
Saya bertanya-tanya, apa yang bisa dilakukan java VM yang menurunkan kinerja seiring waktu untuk kasus (a + b + c> = 2).
Dan inilah yang terjadi jika saya menjalankan java dengan
-client
switch VM:Misteri...
Dan jika saya menjalankannya di GNU Java Interpreter , ia menjadi hampir 100 kali lebih lambat, tetapi
a&&b || b&&c || a&&c
versi itu yang menang.Hasil dari Tofubeer dengan kode terbaru menjalankan OS X:
Hasil dari Paul Wagland dengan Mac Java 1.6.0_26-b03-383-11A511
sumber
a+b+c >= 2
: ini tidak bekerja dengan negatif, bukan? Anda mungkin harus melakukan!!a
hal itu, saya tidak yakin.Pertanyaan semacam ini dapat diselesaikan dengan Peta Karnaugh :
dari mana Anda menyimpulkan bahwa Anda memerlukan grup untuk baris pertama dan dua grup untuk kolom pertama, untuk mendapatkan solusi optimal dari poligenelegricants:
sumber
Keterbacaan harus menjadi tujuannya. Seseorang yang membaca kode harus segera memahami maksud Anda. Jadi, inilah solusi saya.
sumber
Seq(true, true, false).map(if (_) 1 else 0).sum >= 2
Penjelasan:
Jika
a==b
, maka keduanya benar atau keduanya salah. Jika keduanya benar, kami telah menemukan dua boolean sejati kami, dan dapat mengembalikan true (dengan kembalia
). Jika keduanya salah tidak mungkin ada dua boolean sejati bahkan jikac
itu benar, jadi kami mengembalikan false (dengan mengembalikana
). Itu(a==b) ? a
bagiannya. Bagaimana dengan: c
? Baik jikaa==b
salah, maka tepat satua
ataub
harus benar, jadi kami telah menemukan boolean pertama yang benar, dan satu-satunya yang tersisa yang penting adalah jikac
juga benar, jadi kami kembalic
sebagai jawabannya.sumber
a
danb
setuju, mereka memiliki suara mayoritas, jadi pergilah dengan apa pun itu, jika tidak, mereka tidak setuju, demikianc
juga suara yang menentukan"Anda tidak perlu menggunakan bentuk hubungan pendek dari operator.
return (a & b) | (b & c) | (c & a);
Ini melakukan jumlah operasi logika yang sama dengan versi Anda, namun benar-benar tanpa cabang.
sumber
Inilah pendekatan umum yang digerakkan oleh tes. Bukan sebagai "efisien" karena sebagian besar solusi sejauh ini ditawarkan, tetapi jelas, diuji, bekerja, dan digeneralisasi.
sumber
Jumlahkan. Ini disebut aljabar boolean karena suatu alasan:
Jika Anda melihat tabel kebenaran di sana, Anda dapat melihat bahwa perkalian adalah boolean dan, dan tambahannya adalah xor.
Untuk menjawab pertanyaan Anda:
sumber
return ((a?1:0) + (b?1:0) + (c?1:0)) >= 2
.sumber
Itu benar-benar tergantung apa yang Anda maksud dengan "ditingkatkan":
Lebih jelas?
Terser?
Lebih umum?
Lebih scalable?
Lebih cepat?
Yang mana yang "diperbaiki" sangat bergantung pada situasinya.
sumber
Berikut implementasi lain menggunakan peta / kurangi. Ini berskala baik hingga miliaran boolean © dalam lingkungan terdistribusi. Menggunakan MongoDB:
Membuat basis data
values
boolean:Membuat peta, mengurangi fungsi:
Sunting : Saya suka jawaban CurtainDog tentang memiliki peta / mengurangi berlaku untuk daftar umum, jadi inilah fungsi peta yang menerima panggilan balik yang menentukan apakah suatu nilai harus dihitung atau tidak.
Menjalankan peta / kurangi:
sumber
Mengambil jawaban (sejauh ini) di sini:
dan menjalankannya melalui decompiler (javap -c X> results.txt):
Anda dapat melihat bahwa?: Yang sedikit lebih baik daripada versi perbaikan dari sumber asli Anda. Salah satu yang terbaik adalah yang menghindari percabangan sama sekali. Itu bagus dari sudut pandang instruksi yang lebih sedikit (dalam banyak kasus) dan lebih baik untuk bagian prediksi cabang CPU, karena tebakan yang salah dalam prediksi cabang dapat menyebabkan kemacetan CPU.
Saya akan mengatakan yang paling efisien adalah yang dari moonshadow secara keseluruhan. Ini menggunakan instruksi paling sedikit rata-rata dan mengurangi kemungkinan warung pipa di CPU.
Untuk menjadi 100% yakin Anda perlu mengetahui biaya (dalam siklus CPU) untuk setiap instruksi, yang, sayangnya tidak tersedia (Anda harus melihat sumber untuk hotspot dan kemudian vendor CPU menentukan spesifikasi untuk waktu itu). diambil untuk setiap instruksi yang dihasilkan).
Lihat jawaban yang diperbarui oleh Rotsor untuk analisis runtime kode.
sumber
Contoh lain dari kode langsung:
Jelas itu bukan kode yang paling ringkas.
Tambahan
Versi lain (sedikit dioptimalkan) ini:
Ini mungkin berjalan sedikit lebih cepat, dengan asumsi bahwa perbandingan terhadap 0 akan menggunakan kode yang lebih cepat (atau mungkin lebih sedikit) daripada perbandingan terhadap 2.
sumber
++n
lebih cepat daripadan++
karena Anda harus membuat salinan lain sebelum melakukan penambahan .n
atas), setiap kompiler yang layak akan mengkompilasi setiap++
operasi menjadi satu instruksi CPU, apakah itu pra atau posting.Namun cara lain untuk melakukan ini tetapi tidak terlalu bagus:
Nilai
Boolean
kode hash ditetapkan pada 1231 untuk true dan 1237 untuk false sehingga bisa digunakan secara setara<= 3699
sumber
Set peningkatan yang paling jelas adalah:
lalu
Tetapi perbaikan itu kecil.
sumber
Saya tidak suka ternary (
return a ? (b || c) : (b && c);
dari jawaban atas), dan saya tidak berpikir saya pernah melihat orang menyebutkannya. Itu ditulis seperti ini:sumber
Di Clojure :
Pemakaian:
sumber
Saya rasa saya belum melihat solusi ini:
Keuntungannya adalah begitu mencapai angka yang Anda cari, itu rusak. Jadi, jika ini "setidaknya 2 dari 1.000.000 nilai ini benar" di mana dua yang pertama sebenarnya benar, maka itu harus lebih cepat daripada beberapa solusi yang lebih "normal".
sumber
boolean ... boolValues
lebih mudah untuk menelepon, tetapi masih membutuhkan arrayKami dapat mengonversi bool menjadi bilangan bulat dan melakukan pemeriksaan mudah ini:
sumber
Karena tidak ditentukan bagaimana kode harus ditingkatkan, saya akan berusaha untuk memperbaiki kode dengan membuatnya lebih lucu. Inilah solusi saya:
Jika ada yang bertanya-tanya apakah kode ini berfungsi, berikut adalah penyederhanaan menggunakan logika yang sama:
}
Ini dapat diringkas lebih lanjut sebagai berikut:
Tapi sekarang tidak lucu lagi.
sumber
Terlalu banyak cara untuk melakukan ini ...
sumber
Solusi AC.
atau Anda mungkin lebih suka:
sumber
sumber
Cara paling sederhana (IMO) yang tidak membingungkan dan mudah dibaca:
sumber
(C && (A || B)) || (A && B)
baru saja mengubah nama * variabel` ...Interpretasi literal akan bekerja dalam semua bahasa utama:
Tapi saya mungkin akan membuat lebih mudah bagi orang untuk membaca, dan diperluas menjadi lebih dari tiga - sesuatu yang tampaknya dilupakan oleh banyak programmer:
sumber
Sebagai tambahan untuk postingan @TofuBeer TofuBeer yang luar biasa, pertimbangkan jawaban @pdox pdox:
Pertimbangkan juga versinya yang dibongkar seperti yang diberikan oleh "javap -c":
jawaban pdox mengkompilasi kode byte lebih sedikit daripada jawaban sebelumnya. Bagaimana waktu pelaksanaannya dibandingkan dengan yang lain?
Setidaknya di komputer saya, jawaban pdox hanya sedikit lebih cepat daripada jawaban @moonshadow moonshadow, menjadikan pdox yang tercepat secara keseluruhan (pada laptop HP / Intel saya).
sumber
Di Ruby:
[a, b, c].count { |x| x } >= 2
Yang bisa dijalankan di JRuby di JavaVM. ;-)
sumber
Dia mungkin tidak mencari sesuatu yang berbelit-belit seperti operator perbandingan bitwise (biasanya berbelit-belit tetapi dengan boolean, sangat aneh untuk menggunakan operator bitwise) atau sesuatu yang sangat bundar seperti mengkonversi ke int dan menjumlahkannya.
Cara paling langsung dan alami untuk menyelesaikan ini adalah dengan ekspresi seperti ini:
Masukkan fungsi jika Anda mau, tetapi tidak terlalu rumit. Solusinya singkat dan efisien secara logis.
sumber
Dalam C:
sumber