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

Ответ 1

Пожалуйста, подумайте об уменьшении вашей функции 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

Изменить в ответ на комментарий OP "" Это значительно ухудшилось! Урезанная версия занимает в 4 раза больше времени, чем версия, которую я опубликовал выше. "" "

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

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 code
    popn.noncus = noncus # omitted from OP 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
>>>

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

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

Ответ 2

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

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

Изменить. Прежде всего, я должен согласиться со всеми остальными: вы уверены, что правильно измеряете время? Пример кода работает 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 вы должны преобразовать в С++, скомпилировать и запустить:

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 -ized код:

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, print cymakefaster. файл; 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

Изменить: Aaaand более значимые тайминги, для 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.

Ответ 3

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

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)

Ответ 4

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

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

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

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

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

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

Ответ 5

В этом комментарии звучат звонки:

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

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

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

Мне нравится применять SRP к методам, а также к классам: это упрощает тестирование.

Ответ 6

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

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

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

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

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

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

Ответ 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 в каждом объекте человека, так и каждый из них помещать в отдельный список в зависимости от этого атрибута. Разумеется, создание этих двух списков не ускорит цикл.

Ответ 8

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

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