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 loadliczba 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:

1. (razy, podziel)
2. (przesunięcie, przesunięcie)
3. (czasy, zmiana)
4. (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 xrozmiary, gdy optymalizacja mnożenia nie ma zastosowania.

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 xmniejszy 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:

static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    /* fast path for single-digit multiplication */
    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
        return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
        /* if we don't have long long then we're almost certainly
           using 15-bit digits, so v will fit in a long.  In the
           unlikely event that we're using 30-bit digits on a platform
           without long long, a large v will just cause us to fall
           through to the general multiplication code below. */
        if (v >= LONG_MIN && v <= LONG_MAX)
            return PyLong_FromLong((long)v);
#endif
    }

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 /*** ***/)

static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
    /*** ... ***/

    wordshift = shiftby / PyLong_SHIFT;   /*** zero for small w ***/
    remshift  = shiftby - wordshift * PyLong_SHIFT;   /*** w for small w ***/

    oldsize = Py_ABS(Py_SIZE(a));   /*** 1 for small v > 0 ***/
    newsize = oldsize + wordshift;
    if (remshift)
        ++newsize;   /*** here newsize becomes at least 2 for w > 0, v > 0 ***/
    z = _PyLong_New(newsize);

    /*** ... ***/
}

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ą funkcji long_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.