Patrzyłem na źródło sort_containers i byłem zaskoczony, widząc tę linię :
self._load, self._twice, self._half = load, load * 2, load >> 1
Oto load
liczba całkowita. Po co używać przesunięcia bitowego w jednym miejscu, a mnożenia w innym? Wydaje się rozsądne, że przesunięcie bitu może być szybsze niż dzielenie przez całkę przez 2, ale dlaczego nie zastąpić mnożenia również przesunięciem? Porównałem następujące przypadki:
- (razy, podziel)
- (przesunięcie, przesunięcie)
- (czasy, zmiana)
- (przesuń, podziel)
i odkryłem, że # 3 jest konsekwentnie szybszy niż inne alternatywy:
# 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)])
Pytanie:
Czy mój test jest ważny? Jeśli tak, dlaczego (mnożenie, przesuwanie) jest szybsze niż (przesuwanie, przesuwanie)?
Uruchamiam Python 3.5 na Ubuntu 14.04.
Edytować
Powyżej znajduje się oryginalne sformułowanie pytania. Dan Getz zapewnia doskonałe wyjaśnienie w swojej odpowiedzi.
W trosce o kompletność poniżej przedstawiono przykładowe ilustracje przedstawiające większe x
rozmiary, gdy optymalizacja mnożenia nie ma zastosowania.
źródło
x
?x
jest bardzo duże, ponieważ to tylko kwestia tego, jak jest przechowywany w pamięci, prawda?Odpowiedzi:
Wydaje się, że dzieje się tak, ponieważ mnożenie małych liczb jest zoptymalizowane w CPythonie 3.5 w taki sposób, że przesunięcia w lewo przez małe liczby nie są. Dodatnie przesunięcia w lewo zawsze tworzą większy obiekt będący liczbą całkowitą do przechowywania wyniku, jako część obliczenia, podczas gdy w przypadku mnożenia takiego rodzaju, jakiego użyłeś w teście, specjalna optymalizacja unika tego i tworzy obiekt całkowity o prawidłowym rozmiarze. Można to zobaczyć w kodzie źródłowym implementacji liczb całkowitych w Pythonie .
Ponieważ liczby całkowite w Pythonie mają dowolną precyzję, są one przechowywane jako tablice liczb całkowitych z ograniczeniem liczby bitów przypadających na cyfrę całkowitą. Zatem w ogólnym przypadku operacje na liczbach całkowitych nie są pojedynczymi operacjami, ale zamiast tego muszą obsługiwać przypadek wielu „cyfr”. W pyport.h ten limit bitów jest zdefiniowany jako 30 bitów na platformie 64-bitowej lub 15 bitów w innym przypadku. (Odtąd będę po prostu nazywać to 30, aby wyjaśnienie było proste. Pamiętaj jednak, że jeśli używasz Pythona skompilowanego dla wersji 32-bitowej, wynik twojego testu porównawczego będzie zależał od tego, czy byłby
x
mniejszy niż 32768, czy nie).Gdy wejścia i wyjścia operacji mieszczą się w tym 30-bitowym limicie, operacja może być obsługiwana w sposób zoptymalizowany zamiast w sposób ogólny. Początek implementacji mnożenia liczb całkowitych jest następujący:
Zatem mnożenie dwóch liczb całkowitych, z których każda mieści się w 30-bitowej cyfrze, odbywa się jako bezpośrednie mnożenie przez interpreter CPythona, zamiast pracować z liczbami całkowitymi jako tablicami. (
MEDIUM_VALUE()
wywoływane na dodatnim obiekcie całkowitoliczbowym po prostu pobiera pierwszą 30-bitową cyfrę). Jeśli wynik mieści się w jednej 30-bitowej cyfrze,PyLong_FromLongLong()
zauważy to w stosunkowo niewielkiej liczbie operacji i utworzy jednocyfrową liczbę całkowitą do przechowywania to.W przeciwieństwie do tego, przesunięcia w lewo nie są optymalizowane w ten sposób, a każde przesunięcie w lewo zajmuje się przesunięciem liczby całkowitej jako tablicy. W szczególności, jeśli spojrzysz na kod źródłowy
long_lshift()
, w przypadku małego, ale dodatniego przesunięcia w lewo, zawsze tworzony jest 2-cyfrowy obiekt będący liczbą całkowitą, choćby po to, aby jego długość została później skrócona do 1: (moje komentarze w/*** ***/
)Dzielenie liczb całkowitych
Nie pytałeś o gorszą wydajność całkowitego podziału dolnego w porównaniu z prawidłowymi zmianami, ponieważ pasuje to do twoich (i moich) oczekiwań. Ale dzielenie małej liczby dodatniej przez inną małą liczbę dodatnią również nie jest tak zoptymalizowane, jak małe mnożenia. Every
//
oblicza iloraz i resztę za pomocą funkcjilong_divrem()
. Ta reszta jest obliczana dla małego dzielnika z pomnożeniem i jest przechowywana w nowo przydzielonym obiekcie całkowitoliczbowym , który w tej sytuacji jest natychmiast odrzucany.źródło
x
poza zoptymalizowanym zakresem.