Saya melihat sumber dari Sort_containers dan terkejut melihat baris ini :
self._load, self._twice, self._half = load, load * 2, load >> 1
Berikut load
ini adalah bilangan bulat. Mengapa menggunakan bit shift di satu tempat, dan multiplikasi di tempat lain? Tampaknya masuk akal bahwa pergeseran bit mungkin lebih cepat daripada pembagian integral dengan 2, tetapi mengapa tidak mengganti perkalian dengan pergeseran juga? Saya membandingkan beberapa kasus berikut:
- (kali, bagi)
- (bergeser, bergeser)
- (kali, bergeser)
- (bergeser, bagilah)
dan menemukan bahwa # 3 secara konsisten lebih cepat daripada alternatif lain:
# self._load, self._twice, self._half = load, load * 2, load >> 1
import random
import timeit
import pandas as pd
x = random.randint(10 ** 3, 10 ** 6)
def test_naive():
a, b, c = x, 2 * x, x // 2
def test_shift():
a, b, c = x, x << 1, x >> 1
def test_mixed():
a, b, c = x, x * 2, x >> 1
def test_mixed_swapped():
a, b, c = x, x << 1, x // 2
def observe(k):
print(k)
return {
'naive': timeit.timeit(test_naive),
'shift': timeit.timeit(test_shift),
'mixed': timeit.timeit(test_mixed),
'mixed_swapped': timeit.timeit(test_mixed_swapped),
}
def get_observations():
return pd.DataFrame([observe(k) for k in range(100)])
Pertanyaan:
Apakah tes saya valid? Jika demikian, mengapa (multiply, shift) lebih cepat dari (shift, shift)?
Saya menjalankan Python 3.5 di Ubuntu 14.04.
Edit
Di atas adalah pernyataan asli dari pertanyaan itu. Dan Getz memberikan penjelasan yang sangat baik dalam jawabannya.
Demi kelengkapan, berikut adalah contoh ilustrasi untuk ukuran yang lebih besar x
ketika optimisasi multiplikasi tidak berlaku.
sumber
x
?x
sangat besar, karena itu hanya pertanyaan tentang bagaimana itu disimpan dalam memori, kan?Jawaban:
Ini tampaknya karena penggandaan angka kecil dioptimalkan dalam CPython 3.5, dengan cara yang tidak bergeser oleh angka kecil tidak. Pergeseran kiri positif selalu membuat objek bilangan bulat yang lebih besar untuk menyimpan hasilnya, sebagai bagian dari perhitungan, sedangkan untuk perkalian dari jenis yang Anda gunakan dalam pengujian Anda, optimasi khusus menghindari hal ini dan membuat objek bilangan bulat dengan ukuran yang benar. Ini dapat dilihat pada kode sumber implementasi integer Python .
Karena integer dengan Python presisi-arbitrary, mereka disimpan sebagai array dari integer "digit", dengan batas jumlah bit per digit integer. Jadi dalam kasus umum, operasi yang melibatkan bilangan bulat bukan operasi tunggal, melainkan harus menangani kasus beberapa "digit". Di pyport.h , batas bit ini ini didefinisikan sebagai 30 bit pada platform 64-bit, atau 15 bit sebaliknya. (Saya hanya akan memanggil 30 ini dari sini untuk menjaga penjelasannya sederhana. Tetapi perhatikan bahwa jika Anda menggunakan Python yang dikompilasi untuk 32-bit, hasil patokan Anda akan tergantung pada apakah
x
kurang dari 32.768 atau tidak.)Ketika input dan output operasi tetap dalam batas 30-bit ini, operasi dapat ditangani dengan cara yang dioptimalkan daripada cara umum. Awal implementasi multiplikasi integer adalah sebagai berikut:
Jadi ketika mengalikan dua bilangan bulat di mana masing-masing cocok dalam digit 30-bit, ini dilakukan sebagai perkalian langsung oleh juru bahasa CPython, alih-alih bekerja dengan bilangan bulat sebagai array. (
MEDIUM_VALUE()
dipanggil pada objek integer positif hanya mendapatkan digit 30-bit pertamanya.) Jika hasilnya cocok dengan digit 30-bit tunggal,PyLong_FromLongLong()
akan melihat ini dalam jumlah operasi yang relatif kecil, dan membuat objek integer digit tunggal untuk menyimpan Itu.Sebaliknya, shift kiri tidak dioptimalkan dengan cara ini, dan setiap shift kiri berkaitan dengan integer yang digeser sebagai array. Secara khusus, jika Anda melihat kode sumber untuk
long_lshift()
, dalam kasus shift kiri kecil tapi positif, objek integer 2 digit selalu dibuat, jika hanya untuk panjangnya dipotong menjadi 1 nanti: (komentar saya di/*** ***/
)Divisi integer
Anda tidak bertanya tentang kinerja divisi bilangan bulat yang lebih buruk dibandingkan dengan shift yang tepat, karena itu sesuai dengan harapan Anda (dan saya). Tetapi membagi angka positif kecil dengan angka positif kecil lainnya juga tidak dioptimalkan seperti perkalian kecil. Setiap
//
menghitung hasil bagi dan sisanya menggunakan fungsilong_divrem()
. Sisa ini dihitung untuk pembagi kecil dengan perkalian , dan disimpan dalam objek integer yang baru dialokasikan , yang dalam situasi ini segera dibuang.sumber
x
luar rentang yang dioptimalkan.