Увеличение скорости кода Python

Question

У меня есть некоторый код на Python, который имеет много классов. Я использовал cProfile, чтобы найти, что общее время для запуска программы составляет 68 секунд. Я обнаружил, что следующая функция в классе с именем Buyers занимает около 60 секунд из этих 68 секунд. Я должен запустить программу около 100 раз, поэтому любое увеличение скорости поможет. Можете ли вы предложить способы увеличения скорости путем изменения кода? Если вам нужна дополнительная информация, пожалуйста, дайте мне знать.

def qtyDemanded(self, timePd, priceVector):
    '''Returns quantity demanded in period timePd. In addition,
    also updates the list of customers and non-customers.

    Inputs: timePd and priceVector
    Output: count of people for whom priceVector[-1] < utility
    '''

    ## Initialize count of customers to zero
    ## Set self.customers and self.nonCustomers to empty lists
    price = priceVector[-1]
    count = 0
    self.customers = []
    self.nonCustomers = []


    for person in self.people:
        if person.utility >= price:             
            person.customer = 1
            self.customers.append(person)
        else:
            person.customer = 0
            self.nonCustomers.append(person)

    return len(self.customers)

self.people - это список person объектов. Каждый person имеет customer и utility в качестве своих атрибутов.

РЕДАКТИРОВАТЬ - добавленный ответ

-------------------------------------

Большое спасибо за предложения. Здесь Ответы на некоторые вопросы и предложения люди любезно сделал. Я не пробовал их всех, но попробую других и напишу позже.

(1) @amber - к функции обращаются 80000 раз.

(2) @gnibbler и другие - self.people - это список объектов Person в памяти. Не подключен к базе данных.

(3) @ Хью Ботвелл

cumtime по оригинальной функции - 60,8 с (доступ 80000 раз)

cumtime, занятое новой функцией с псевдонимами локальной функции в соответствии с предложением - 56,4 с (доступ 80000 раз)

(4) @rotoglup и @Martin Thomas

Я еще не пробовал ваши решения. Мне нужно проверить оставшуюся часть кода, чтобы увидеть места, где я использую self.customers, прежде чем я смогу внести изменения, не добавляя клиентов в список self.customers. Но я попробую это и напишу обратно.

(5) @TryPyPy - спасибо за ваше любезное предложение проверить код.

Позвольте мне сначала немного прочесть предложения, которые вы внесли, чтобы увидеть, можно ли их использовать.

РЕДАКТИРОВАТЬ 2 Некоторые предположили, что, поскольку я отмечаю клиентов и не-клиентов в self.people, я должен попытаться не создавать отдельные списки self.customers и self.noncustomers, используя append. Вместо этого я должен перебрать self.people, чтобы найти количество клиентов. Я попробовал следующий код и рассчитал обе функции ниже f_w_append и f_wo_append. Я обнаружил, что последнее занимает меньше времени, но это все еще 96% времени, которое занимает первое. То есть это очень небольшое увеличение скорости.

@ TryPyPy - следующий фрагмент кода достаточно полон, чтобы проверить функцию узкого места, на случай, если ваше предложение еще есть, чтобы проверить его с другими компиляторами.

Еще раз спасибо всем, кто ответил.

import numpy

class person(object):
    def __init__(self, util):
        self.utility = util
        self.customer = 0

class population(object):
    def __init__(self, numpeople):
        self.people = []
        self.cus = []
        self.noncus = []
        numpy.random.seed(1)
        utils = numpy.random.uniform(0, 300, numpeople)
        for u in utils:
            per = person(u)
            self.people.append(per)

popn = population(300)

def f_w_append():
    '''Function with append'''
    P = 75
    cus = []
    noncus = []
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
            cus.append(per)
        else:
            per.customer = 0
            noncus.append(per)
    return len(cus)

def f_wo_append():
    '''Function without append'''
    P = 75
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
        else:
            per.customer = 0

    numcustomers = 0
    for per in popn.people:
        if per.customer == 1:
            numcustomers += 1                
    return numcustomers

РЕДАКТИРОВАТЬ 3: Кажется, проблема в numpy

Это в ответ на то, что Джон Махин сказал ниже. Ниже вы видите два способа определения класса Population. Я запускал программу ниже дважды, по одному с каждым способом создания Population класса. Один использует NumPy и один не использует NUMPY. Один без numpy занимает столько же времени, сколько Джон нашел в своих пробежках. Один с NumPy занимает гораздо больше времени. Что мне неясно, так это то, что экземпляр popn создается до начала записи времени (по крайней мере, именно так он выглядит из кода). Тогда, почему NumPy версия занимает больше времени. И я подумал, что numpy должен был быть более эффективным. Во всяком случае, проблема, кажется, с NumPy и не столько с дополнением, хотя это немного замедляет вещи. Может кто-нибудь, пожалуйста, подтвердите с кодом ниже? Спасибо.

import random # instead of numpy
import numpy
import time
timer_func = time.time # using Mac OS X 10.5.8

class Person(object):
    def __init__(self, util):
        self.utility = util
        self.customer = 0

class Population(object):
    def __init__(self, numpeople):
        random.seed(1)
        self.people = [Person(random.uniform(0, 300)) for i in xrange(numpeople)]
        self.cus = []
        self.noncus = []   

# Numpy based    
# class Population(object):
#     def __init__(self, numpeople):
#         numpy.random.seed(1)
#         utils = numpy.random.uniform(0, 300, numpeople)
#         self.people = [Person(u) for u in utils]
#         self.cus = []
#         self.noncus = []    


def f_wo_append(popn):
    '''Function without append'''
    P = 75
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
        else:
            per.customer = 0

    numcustomers = 0
    for per in popn.people:
        if per.customer == 1:
            numcustomers += 1                
    return numcustomers



t0 = timer_func()
for i in xrange(20000):
    x = f_wo_append(popn)
t1 = timer_func()
print t1-t0

Редактировать 4: См. Ответы Джона Мачина и TryPyPy

Поскольку здесь было так много правок и обновлений, те, кто попал сюда впервые, могут быть немного смущены. Смотрите ответы Джона Мачина и TryPyPy. И то, и другое может существенно улучшить скорость кода. Я благодарен им и другим, кто предупредил меня о медлительности append. Поскольку в этом случае я собираюсь использовать решение Джона Мачина и не использовать numpy для генерации утилит, я принимаю его ответ как ответ. Тем не менее, я действительно ценю указания, указанные в TryPyPy.

Answer 1

Есть много вещей, которые вы можете попробовать после оптимизации вашего кода Python для скорости.Если эта программа не нуждается в расширениях C, вы можете запустить ее под PyPy , чтобы воспользоваться ее JIT-компилятором.Вы можете попробовать сделать расширение C для возможно огромных ускорений . Shed Skin даже позволит вам преобразовать вашу программу на Python в автономный двоичный файл C ++.

Я готов использовать вашу программу в соответствии с этими различными сценариями оптимизации, если вы сможете предоставить достаточно кода для сравнительного анализа,

Редактировать : Прежде всего, я должен согласиться со всеми остальными: вы уверены, что правильно измеряете время?Пример кода здесь выполняется 100 раз менее чем за 0,1 секунды, поэтому есть большая вероятность, что либо неправильное время, либо у вас есть узкое место (IO?), Которого нет в примере кода.

Тосказал, я сделал это 300000 человек, поэтому времена были последовательными.Вот адаптированный код, общий для CPython (2.5), PyPy и Shed Skin:

from time import time
import random
import sys


class person(object):
    def __init__(self, util):
        self.utility = util
        self.customer = 0


class population(object):
    def __init__(self, numpeople, util):
        self.people = []
        self.cus = []
        self.noncus = []
        for u in util:
            per = person(u)
            self.people.append(per)


def f_w_append(popn):
    '''Function with append'''
    P = 75
    cus = []
    noncus = []
    # Help CPython a bit
    # cus_append, noncus_append = cus.append, noncus.append
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
            cus.append(per)
        else:
            per.customer = 0
            noncus.append(per)
    return len(cus)


def f_wo_append(popn):
    '''Function without append'''
    P = 75
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
        else:
            per.customer = 0

    numcustomers = 0
    for per in popn.people:
        if per.customer == 1:
            numcustomers += 1
    return numcustomers


def main():
    try:
        numpeople = int(sys.argv[1])
    except:
        numpeople = 300000

    print "Running for %s people, 100 times." % numpeople

    begin = time()
    random.seed(1)
    # Help CPython a bit
    uniform = random.uniform
    util = [uniform(0.0, 300.0) for _ in xrange(numpeople)]
    # util = [random.uniform(0.0, 300.0) for _ in xrange(numpeople)]

    popn1 = population(numpeople, util)
    start = time()
    for _ in xrange(100):
        r = f_wo_append(popn1)
    print r
    print "Without append: %s" % (time() - start)


    popn2 = population(numpeople, util)
    start = time()
    for _ in xrange(100):
        r = f_w_append(popn2)
    print r
    print "With append: %s" % (time() - start)

    print "\n\nTotal time: %s" % (time() - begin)

if __name__ == "__main__":
    main()

Работать с PyPy так же просто, как и работать с CPython, просто введите «pypy» вместо «python».Для Shed Skin вы должны конвертировать в C ++, скомпилировать и запустить:

shedskin -e makefaster.py && make 

# Check that you're using the makefaster.so file and run test
python -c "import makefaster; print makefaster.__file__; makefaster.main()" 

А вот код на языке Cython:

from time import time
import random
import sys


cdef class person:
    cdef readonly int utility
    cdef public int customer

    def __init__(self, util):
        self.utility = util
        self.customer = 0


class population(object):
    def __init__(self, numpeople, util):
        self.people = []
        self.cus = []
        self.noncus = []
        for u in util:
            per = person(u)
            self.people.append(per)


cdef int f_w_append(popn):
    '''Function with append'''
    cdef int P = 75
    cdef person per
    cus = []
    noncus = []
    # Help CPython a bit
    # cus_append, noncus_append = cus.append, noncus.append

    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
            cus.append(per)
        else:
            per.customer = 0
            noncus.append(per)
    cdef int lcus = len(cus)
    return lcus


cdef int f_wo_append(popn):
    '''Function without append'''
    cdef int P = 75
    cdef person per
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
        else:
            per.customer = 0

    cdef int numcustomers = 0
    for per in popn.people:
        if per.customer == 1:
            numcustomers += 1
    return numcustomers


def main():

    cdef int i, r, numpeople
    cdef double _0, _300
    _0 = 0.0
    _300 = 300.0

    try:
        numpeople = int(sys.argv[1])
    except:
        numpeople = 300000

    print "Running for %s people, 100 times." % numpeople

    begin = time()
    random.seed(1)
    # Help CPython a bit
    uniform = random.uniform
    util = [uniform(_0, _300) for i in xrange(numpeople)]
    # util = [random.uniform(0.0, 300.0) for _ in xrange(numpeople)]

    popn1 = population(numpeople, util)
    start = time()
    for i in xrange(100):
        r = f_wo_append(popn1)
    print r
    print "Without append: %s" % (time() - start)


    popn2 = population(numpeople, util)
    start = time()
    for i in xrange(100):
        r = f_w_append(popn2)
    print r
    print "With append: %s" % (time() - start)

    print "\n\nTotal time: %s" % (time() - begin)

if __name__ == "__main__":
    main()

Для его сборки приятно иметьsetup.py вот так:

from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

ext_modules = [Extension("cymakefaster", ["makefaster.pyx"])]

setup(
  name = 'Python code to speed up',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules
)

Вы создаете его с помощью: python setupfaster.py build_ext --inplace

Затем тестируйте: python -c "import cymakefaster; печатайте cymakefaster. file ; cymakefaster.main () "

Синхронизация запускалась пять раз для каждой версии, при этом Cython был самым быстрым и простым из всех используемых генераторов кода (Shed Skin стремится быть более простым, но загадочнымсообщения об ошибках и неявная статическая типизация усложнили здесь).Что касается лучшего значения, PyPy обеспечивает впечатляющее ускорение в версии счетчика без изменений кода.

#Results (time in seconds for 30000 people, 100 calls for each function):
                  Mean      Min  Times    
CPython 2.5.2
Without append: 35.037   34.518  35.124, 36.363, 34.518, 34.620, 34.559
With append:    29.251   29.126  29.339, 29.257, 29.259, 29.126, 29.272
Total time:     69.288   68.739  69.519, 70.614, 68.746, 68.739, 68.823

PyPy 1.4.1
Without append:  2.672    2.655   2.655,  2.670,  2.676,  2.690,  2.668
With append:    13.030   12.672  12.680, 12.725, 14.319, 12.755, 12.672
Total time:     16.551   16.194  16.196, 16.229, 17.840, 16.295, 16.194

Shed Skin 0.7 (gcc -O2)
Without append:  1.601    1.599   1.599,  1.605,  1.600,  1.602,  1.599
With append:     3.811    3.786   3.839,  3.795,  3.798,  3.786,  3.839
Total time:      5.704    5.677   5.715,  5.705,  5.699,  5.677,  5.726

Cython 0.14 (gcc -O2)
Without append:  1.692    1.673   1.673,  1.710,  1.678,  1.688,  1.711
With append:     3.087    3.067   3.079,  3.080,  3.119,  3.090,  3.067
Total time:      5.565    5.561   5.562,  5.561,  5.567,  5.562,  5.572

Редактировать : Ааа и более значимые тайминги, для 80000 звонков по 300 человек в каждом:

Results (time in seconds for 300 people, 80000 calls for each function):
                  Mean      Min  Times
CPython 2.5.2
Without append: 27.790   25.827  25.827, 27.315, 27.985, 28.211, 29.612
With append:    26.449   24.721  24.721, 27.017, 27.653, 25.576, 27.277
Total time:     54.243   50.550  50.550, 54.334, 55.652, 53.789, 56.892


Cython 0.14 (gcc -O2)
Without append:  1.819    1.760   1.760,  1.794,  1.843,  1.827,  1.871
With append:     2.089    2.063   2.100,  2.063,  2.098,  2.104,  2.078
Total time:      3.910    3.859   3.865,  3.859,  3.944,  3.934,  3.951

PyPy 1.4.1
Without append:  0.889    0.887   0.894,  0.888,  0.890,  0.888,  0.887
With append:     1.671    1.665   1.665,  1.666,  1.671,  1.673,  1.681
Total time:      2.561    2.555   2.560,  2.555,  2.561,  2.561,  2.569

Shed Skin 0.7 (g++ -O2)
Without append:  0.310    0.301   0.301,  0.308,  0.317,  0.320,  0.303
With append:     1.712    1.690   1.733,  1.700,  1.735,  1.690,  1.702
Total time:      2.027    2.008   2.035,  2.008,  2.052,  2.011,  2.029

Shed Skin становится быстрее, PyPy превосходит Cython.Все три вещи намного быстрее по сравнению с CPython.

Answer 2

Пожалуйста, подумайте об уменьшении вашей функции f_wo_append:

def f_wo_append():
    '''Function without append'''
    P = 75
    numcustomers = 0
    for person in popn.people:
        person.customer = iscust = person.utility >= P
        numcustomers += iscust
    return numcustomers

Редактировать в ответ на комментарий ОП "" "Это сделало его намного хуже! Урезанная версия занимает в 4 раза больше времени, чем версия, которую я выложил выше." ""

Нет способа, которым это могло бы занять «в 4 раза больше» (5 раз?) ... вот мой код, который демонстрирует значительное сокращение в случае «без добавления», как я предлагал, а также вводит значительное улучшение по делу "с добавлением".

import random # instead of numpy
import time
timer_func = time.clock # better on Windows, use time.time on *x platform

class Person(object):
    def __init__(self, util):
        self.utility = util
        self.customer = 0

class Population(object):
    def __init__(self, numpeople):
        random.seed(1)
        self.people = [Person(random.uniform(0, 300)) for i in xrange(numpeople)]
        self.cus = []
        self.noncus = []        

def f_w_append(popn):
    '''Function with append'''
    P = 75
    cus = []
    noncus = []
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
            cus.append(per)
        else:
            per.customer = 0
            noncus.append(per)
    popn.cus = cus # omitted from OP's code
    popn.noncus = noncus # omitted from OP's code
    return len(cus)

def f_w_append2(popn):
    '''Function with append'''
    P = 75
    popn.cus = []
    popn.noncus = []
    cusapp = popn.cus.append
    noncusapp = popn.noncus.append
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
            cusapp(per)
        else:
            per.customer = 0
            noncusapp(per)
    return len(popn.cus)    

def f_wo_append(popn):
    '''Function without append'''
    P = 75
    for per in popn.people:
        if  per.utility >= P:
            per.customer = 1
        else:
            per.customer = 0

    numcustomers = 0
    for per in popn.people:
        if per.customer == 1:
            numcustomers += 1                
    return numcustomers

def f_wo_append2(popn):
    '''Function without append'''
    P = 75
    numcustomers = 0
    for person in popn.people:
        person.customer = iscust = person.utility >= P
        numcustomers += iscust
    return numcustomers    

if __name__ == "__main__":
    import sys
    popsize, which, niter = map(int, sys.argv[1:4])
    pop = Population(popsize)
    func = (f_w_append, f_w_append2, f_wo_append, f_wo_append2)[which]
    t0 = timer_func()
    for _unused in xrange(niter):
        nc = func(pop)
    t1 = timer_func()
    print "popsize=%d func=%s niter=%d nc=%d seconds=%.2f" % (
        popsize, func.__name__, niter, nc, t1 - t0)

и вот результаты его работы (Python 2.7.1, Windows 7 Pro, «Intel Core i3 CPU 540 @ 3,07 ГГц»):

C:\junk>\python27\python ncust.py 300 0 80000
popsize=300 func=f_w_append niter=80000 nc=218 seconds=5.48

C:\junk>\python27\python ncust.py 300 1 80000
popsize=300 func=f_w_append2 niter=80000 nc=218 seconds=4.62

C:\junk>\python27\python ncust.py 300 2 80000
popsize=300 func=f_wo_append niter=80000 nc=218 seconds=5.55

C:\junk>\python27\python ncust.py 300 3 80000
popsize=300 func=f_wo_append2 niter=80000 nc=218 seconds=4.29

Редактировать 3 Почему numpy занимает больше времени:

>>> import numpy
>>> utils = numpy.random.uniform(0, 300, 10)
>>> print repr(utils[0])
42.777972538362874
>>> type(utils[0])
<type 'numpy.float64'>

и вот почему моя функция f_wo_append2 заняла в 4 раза больше времени:

>>> x = utils[0]
>>> type(x)
<type 'numpy.float64'>
>>> type(x >= 75) 
<type 'numpy.bool_'> # iscust refers to a numpy.bool_
>>> type(0 + (x >= 75)) 
<type 'numpy.int32'> # numcustomers ends up referring to a numpy.int32
>>>

Эмпирическим подтверждением является то, что эти пользовательские типы не так быстры, когда используются в качестве скаляров ... возможно, потому, что им необходимо сбрасывать аппаратное обеспечение с плавающей запятой при каждом их использовании. Хорошо для больших массивов, а не для скаляров.

Используете ли вы какие-либо другие функции? Если нет, просто используйте модуль random. Если у вас есть другие варианты использования numpy, вы можете использовать numpy.float64 - float во время настройки популяции.

Answer 3

Этот комментарий звонит в тревожные звонки:

'''Returns quantity demanded in period timePd. In addition,
also updates the list of customers and non-customers.

Помимо того, что timePd не используется в функции, если вы действительно хотите просто вернуть количество, сделайте это в функции.Делайте «дополнительно» вещи в отдельной функции.

Затем выполните профиль и посмотрите, в какой из этих двух функций вы проводите большую часть своего времени.

Мне нравится применять SRP к методам и классам: itоблегчает их тестирование.

Answer 4

В зависимости от того, как часто вы добавляете новые элементы в self.people или изменяете person.utility, вы можете рассмотреть сортировку self.people по полю utility.

Тогда вы можете использовать функцию bisect, чтобы найти нижний индекс i_pivot, где выполняется условие person[i_pivot].utility >= price. Это будет иметь меньшую сложность (O (log N)), чем ваш исчерпывающий цикл (O (N))

Получив эту информацию, вы можете при необходимости обновить список people:

Вам действительно нужно каждый раз обновлять поле utility? В отсортированном случае вы могли бы легко определить это значение во время итерации: например, учитывая, что ваш список отсортирован в порядке возрастания, utility = (index >= i_pivot)

Тот же вопрос со списками customers и nonCustomers. Зачем они тебе нужны? Их можно заменить на кусочки исходного отсортированного списка: например, customers = self.people[0:i_pivot]

Все это позволит вам уменьшить сложность вашего алгоритма и использовать более встроенные (быстрые) функции Python, что может ускорить вашу реализацию.

Answer 5

Некоторые поиски можно исключить, используя псевдонимы локальных функций:

def qtyDemanded(self, timePd, priceVector):
    '''Returns quantity demanded in period timePd. In addition,
    also updates the list of customers and non-customers.

    Inputs: timePd and priceVector
    Output: count of people for whom priceVector[-1] < utility
    '''
    price = priceVector[-1]
    self.customers = []
    self.nonCustomers = []

    # local function aliases
    addCust = self.customers.append
    addNonCust = self.nonCustomers.append

    for person in self.people:
        if person.utility >= price:             
            person.customer = 1
            addCust(person)
        else:
            person.customer = 0
            addNonCust(person)

    return len(self.customers)

Answer 6

Вы просите догадки, и в основном вы получаете догадки.

Не нужно догадываться. Вот пример.

Answer 7

Удивительно, что показанная функция является таким узким местом, потому что она настолько проста.По этой причине я бы дважды проверил мою процедуру профилирования и результаты.Однако, если они верны, самой трудоемкой частью вашей функции должен быть цикл for, который он содержит, конечно, поэтому имеет смысл сосредоточиться на его ускорении.Один из способов сделать это - заменить if/else на прямой код.Вы также можете немного уменьшить поиск атрибутов для метода списка append.Вот как обе эти вещи могут быть выполнены:

def qtyDemanded(self, timePd, priceVector):
    '''Returns quantity demanded in period timePd. In addition,
    also updates the list of customers and non-customers.

    Inputs: timePd and priceVector
    Output: count of people for whom priceVector[-1] < utility
    '''

    price = priceVector[-1] # last price
    kinds = [[], []] # initialize sublists of noncustomers and customers
    kindsAppend = [kinds[b].append for b in (False, True)] # append methods

    for person in self.people:
        person.customer = person.utility >= price  # customer test
        kindsAppend[person.customer](person)  # add to proper list

    self.nonCustomers = kinds[False]
    self.customers = kinds[True]

    return len(self.customers)

Тем не менее, я должен добавить, что кажется немного избыточным иметь оба флага customer в каждом объекте person и также поместите каждый из них в отдельный список в зависимости от этого атрибута.Несоблюдение этих двух списков, конечно, ускорит дальнейший цикл.

Answer 8

Некоторые любопытные вещи, которые я отметил:

timePd передается как параметр, но никогда не используется

цена - это массив, но вы когда-либо используете только последнюю запись - почему бы не передать туда значение вместо передачи списка?

Счет инициализирован и никогда не используется

self.people содержит несколько объектов person, которые затем копируются в self.customers или self.ncustomers, а также с установленным флагом клиента. Почему бы не пропустить операцию копирования и, по возвращении, просто перебрать список, посмотрев на флаг клиента? Это спасло бы дорогостоящее приложение.

В качестве альтернативы попробуйте использовать psyco, который может ускорить чистый Python, иногда значительно.