Ketika saya pertama kali mulai bekerja, programmer assembler mainframe menunjukkan kepada saya bagaimana mereka bertukar nilai tanpa menggunakan algoritma tradisional:
a = 0xBABE
b = 0xFADE
temp = a
a = b
b = temp
Apa yang mereka gunakan untuk menukar dua nilai - dari sedikit ke buffer besar - adalah:
a = 0xBABE
b = 0xFADE
a = a XOR b
b = b XOR a
a = a XOR b
sekarang
b == 0xBABE
a == 0xFADE
yang menukar isi 2 objek tanpa perlu ruang temp temp ketiga.
Pertanyaan saya adalah: Apakah algoritma pertukaran XOR ini masih digunakan dan di mana itu masih berlaku.
algorithms
Quinton Bernhardt
sumber
sumber
Jawaban:
Ketika menggunakan
xorswapada bahaya memasok variabel yang sama karena kedua argumen untuk fungsi yang nol variabel tersebut karena ituxordengan dirinya sendiri yang mengubah semua bit menjadi nol. Tentu saja ini sendiri akan menghasilkan perilaku yang tidak diinginkan terlepas dari algoritma yang digunakan, tetapi perilaku itu mungkin mengejutkan dan tidak jelas pada pandangan pertama.Secara tradisional
xorswaptelah digunakan untuk implementasi tingkat rendah untuk bertukar data antara register. Dalam praktiknya ada alternatif yang lebih baik untuk bertukar variabel dalam register. Sebagai contoh, Intel x86 memilikiXCHGinstruksi yang menukar isi dua register. Berkali-kali seorang kompiler akan mengetahui semantik dari fungsi seperti itu (ia menukar konten dari nilai yang diteruskan ke sana) dan dapat membuat optimasi sendiri jika diperlukan, jadi mencoba untuk mengoptimalkan sesuatu yang sepele seperti fungsi swap tidak benar-benar membelikan Anda apa pun dalam praktek. Hal terbaik untuk menggunakan metode yang jelas kecuali ada alasan terbukti mengapa itu akan kalah dengan mengatakan xorswap dalam domain masalah.sumber
a: 0101 ^ 0101 = 0000; b: 0101 ^ 0000 = 0101; a: 0101 ^ 0000 = 0101;-1->+1.a=10, b=10, dan jika Anda melakukannyaxorswap(a,b)akan berhasil dan tidak nol variabel yang salah dan sekarang dihapus. Tetapi jika Anda melakukannyaxorswap(a, a)makaaakan memusatkan perhatian yang awalnya saya maksudkan tetapi menjadi bodoh. :)Kunci untuk jawabannya ada di pertanyaan - "mengerjakan programmer assembler mainframe" - di hari-hari sebelum kompiler. Ketika manusia berjongkok dengan instruksi perakitan dan membuat solusi tepat untuk perangkat keras tertentu (yang mungkin atau mungkin tidak bekerja pada model lain dari komputer yang sama - masalah seperti waktu hard drive dan memori drum berdampak pada bagaimana kode ditulis - baca Kisah Mel jika salah satu merasa perlu untuk bernostalgia).
Kembali lampau hari-hari, register dan memori berdua langka dan trik untuk tidak perlu mengemis untuk byte lain atau kata memori dari arsitek utama adalah waktu yang disimpan - baik dalam menulis kode dan waktu eksekusi.
Hari-hari itu hilang. Trik bertukar dua hal tanpa menggunakan ketiga adalah trik. Memori dan register keduanya banyak dalam komputasi modern dan manusia tidak lagi menulis perakitan. Kami telah mengajarkan semua trik kami kepada kompiler kami, dan mereka melakukan pekerjaan dengan lebih baik daripada kami. Kemungkinan kompiler melakukan sesuatu yang lebih baik daripada apa yang akan kita lakukan. Dalam kebanyakan kasus, kadang-kadang kita perlu menulis rakitan dalam beberapa loop ketat untuk beberapa alasan ... tapi itu bukan untuk menyimpan register atau kata memori.
Hal ini mungkin berguna lagi jika salah satu bekerja di sebuah mikrokontroler terutama terbatas, tetapi mengoptimalkan swap tidak mungkin sumber masalah seseorang kemudian - mencoba untuk menjadi terlalu pintar lebih mungkin masalah.
sumber
Apakah ini akan berhasil? Iya nih.
Jika Anda menggunakannya? Tidak.
Ini semacam mikro-optimasi akan masuk akal jika:
Anda telah melihat kode yang dihasilkan kompiler untuk cara langsung melakukan ini (penugasan dan sementara) dan memutuskan bahwa pendekatan XOR menghasilkan kode lebih cepat
Anda telah membuat profil aplikasi Anda, dan menemukan bahwa biaya pendekatan langsung lebih penting daripada kejelasan kode (dan menghasilkan penghematan dalam pemeliharaan)
Untuk poin pertama, kecuali jika Anda sudah melakukan pengukuran ini, Anda harus mempercayai compiler. Ketika semantik dari apa yang Anda coba lakukan sudah jelas, ada banyak trik yang dapat dilakukan oleh kompiler, termasuk mengatur ulang akses variabel sehingga swap tidak diperlukan sama sekali, atau sejalan dengan instruksi level mesin apa pun yang memberikan tercepat swap untuk tipe data yang diberikan. "Trik" seperti XOR swap mempersulit kompiler untuk melihat apa yang Anda coba lakukan, dan karenanya membuatnya kurang bisa menerapkan optimasi seperti itu.
Untuk poin kedua, apa yang Anda mendapatkan untuk kompleksitas menambahkan? Bahkan jika Anda telah mengukur dan menemukan pendekatan XOR lebih cepat, apakah ini memiliki dampak yang cukup untuk membenarkan pendekatan yang kurang jelas? Bagaimana Anda tahu?
Akhirnya, Anda harus melihat apakah ada fungsi swap standar untuk platform / bahasa Anda - C ++ STL, misalnya, menyediakan fungsi swap template yang akan cenderung sangat dioptimalkan untuk kompiler / platform Anda.
sumber
Kolega saya melaporkan bahwa ini adalah trik dasar yang ia ajarkan di universitas untuk mempelajari seorang programmer sistem otomatis. Banyak sistem seperti itu yang tertanam dengan sumber daya terbatas dan mereka bisa kekurangan daftar gratis untuk menjaga nilai sementara; dalam hal itu, pertukaran rumit seperti itu (atau analognya dengan menambah dan mengurangi) menjadi sangat penting sehingga masih digunakan.
Tetapi orang harus peduli menggunakannya bahwa dua lokasi ini tidak dapat identik karena dalam kasus terakhir ini akan secara efektif nol nilai kedua. Jadi biasanya terbatas pada kasus yang jelas seperti bertukar register dan lokasi memori.
Dengan x86, instruksi xchg dan cmpxchg memenuhi kebutuhan dalam kebanyakan kasus, tetapi RISC umumnya tidak tercakup bersama mereka (kecuali Sparc).
sumber