Проблемы с внедрением метода Хорнера в Python

Ответ 1

Ваше профилирование может быть значительно улучшено. Кроме того, мы можем сделать ваш код более 200-500 раз быстрее.

(1) Промыть и повторить

Вы не можете запустить только одну итерацию теста производительности по двум причинам.

• Ваше временное разрешение может быть недостаточно хорошим. Вот почему вы иногда получали одно и то же время для двух реализаций: время для одного прогона было около разрешения вашего механизма синхронизации, поэтому вы записали только один "тик".
• На производительность влияют всевозможные факторы. Лучшим вариантом для значимого сравнения будет много итераций.

Вам не нужны gazillions пробегов (хотя, конечно, это не больно), но вы оцениваете и корректируете количество итераций, пока дисперсия не будет в пределах уровня, приемлемого для вашей цели.

timeit - хороший небольшой модуль для профилирования кода Python.

Я добавил это в нижней части вашего script.

import timeit

n = 1000

print 'Horner', timeit.timeit(
    number = n,
    setup='from __main__ import Horner, c, x',
    stmt='Horner(c,x)'
)
print 'naive', timeit.timeit(
    number = n,
    setup='from __main__ import naive, c, x',
    stmt='naive(c,x)', 
)
print 'itera', timeit.timeit(
    number = n,
    setup='from __main__ import itera, c, x',
    stmt='itera(c,x)', 
)

Что производит

Horner 1.8656351566314697
naive 2.2408010959625244
itera 1.9751169681549072

Хорнер самый быстрый, но он не точно дует в двери с двух других.

(2) Посмотрите, что происходит... очень внимательно

Python имеет перегрузку оператора, поэтому легко пропустить это.

npr.uniform(size=(500,1)) дает вам структуру случайных чисел размером 500 x 1.

Так что?

Ну, c[i] не является числом. Это массив numpy с одним элементом. Numpy перегружает операторы, поэтому вы можете делать такие вещи, как умножение массива на скаляр.

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

Вместо этого попробуйте простой список Python:

import random
c = [random.random() for _ in range(500)]

И теперь

Horner 0.034661054611206055
naive 0.12771987915039062
itera 0.07331395149230957

Whoa! Все время раз быстрее (на 10-60x). Пропорционально, реализация Хорнера стала еще быстрее, чем две другие. Мы удалили накладные расходы на всех трех, и теперь можем видеть разницу в "голых костях".

Хорнер в 4 раза быстрее, чем наивный, и 2x быстрее, чем итера.

(3) Альтернативные времена автономной работы

Вы используете Python 2. Я предполагаю 2.7.

Посмотрите, как тарифы на Python 3.4. (Коррекция синтаксиса: вам нужно поставить круглые скобки вокруг списка аргументов на print.)

Horner 0.03298933599944576
naive 0.13706714100044337
itera 0.06771054599812487

О том же.

Попробуйте PyPy, реализацию JIT Python. ( "Обычная" реализация Python называется CPython.)

Horner 0.006507158279418945
naive 0.07541298866271973
itera 0.005059003829956055

Ницца! Каждая реализация теперь работает на 2-5 раз быстрее. Хорнер теперь в 10 раз быстрее наивности, но немного медленнее, чем итера.

Время работы JIT более сложно, чем интерпретаторы. Позвольте увеличить число итераций до 50000 и попробуйте просто убедиться.

Horner 0.12749004364013672
naive 3.2823100090026855
itera 0.06546688079833984

(Обратите внимание, что мы имеем 50x итераций, но только в 20 раз по времени... JIT не в полной мере повлиял на многие из первых 1000 запусков.) Те же выводы, но различия еще более выражены.

Конечно, идея JIT состоит в том, чтобы анализировать и анализировать и перезаписывать программу во время выполнения, поэтому, если ваша цель - сравнить алгоритмы, это добавит много неочевидной детали реализации.

Тем не менее, сравнение времени выполнения может быть полезно для предоставления более широкой перспективы.

Есть еще несколько вещей. Например, ваша наивная реализация вычисляет переменную, которую она никогда не использует. Вы используете range вместо xrange. Вы могли бы попробовать повторить назад с индексом, а не с реверсивным срезом. Etc.

Ни один из них не изменил результаты для меня, но их стоит рассмотреть.

Ответ 2

Вы не можете получить точный результат, измеряя такие вещи:

start_time=time.time()
print Horner(c,x)
print time.time()-start_time

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

Вы должны окончательно взглянуть на модуль timeit. Что-то вроде этого, может быть:

import timeit
print 'Horner',timeit.timeit(stmt='Horner(c,x)', 
                  setup='from __main__ import Horner, c, x',
                  number = 10000)
#                          ^^^^^
#                probably not enough. Increase that once you will
#                be confident

print 'naive',timeit.timeit(stmt='naive(c,x)', 
                  setup='from __main__ import naive, c, x',
                  number = 10000)
print 'itera',timeit.timeit(stmt='itera(c,x)', 
                  setup='from __main__ import itera, c, x',
                  number = 10000)

Производя это в моей системе:

Horner 23.3317809105
naive 28.305519104
itera 24.385917902

Но все же переменные результаты от запуска к другому:

Horner 21.1151690483
naive 23.4374330044
itera 21.305426836

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

Ответ 3

Если вы проводите много бенчмаркинга, научное вычисление, работу с numpy и многое другое, используя ipython, будет чрезвычайно полезным инструмент.

Для сравнения вы можете использовать код timetime с помощью ipython magic, где вы будете получать более последовательные результаты при каждом запуске, это просто вопрос используя timeit, то функция или код во времени:

In [28]: timeit Horner(c,x)
1000 loops, best of 3: 670 µs per loop

In [29]: timeit naive(c,x)
1000 loops, best of 3: 983 µs per loop

In [30]: timeit itera(c,x)
1000 loops, best of 3: 804 µs per loop

Для временного кода, охватывающего более одной строки, вы просто используете %%timeit:

In [35]: %%timeit
   ....: for i in range(100):
   ....:     i ** i
   ....: 
10000 loops, best of 3: 110 µs per loop

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

встроенные магические команды

Используя cython и некоторые очень простые улучшения, мы можем повысить эффективность Horner примерно на 25 процентов:

In [166]: %%cython
import numpy as np
cimport numpy as np
cimport cython
ctypedef np.float_t DTYPE_t
def C_Horner(c, DTYPE_t x):
    cdef DTYPE_t p
    for i in reversed(c):
        p = p * x + i
    return p   

In [28]: c=npr.uniform(size=(2000,1))

In [29]: timeit Horner(c,-1.34)
100 loops, best of 3: 3.93 ms per loop
In [30]: timeit C_Horner(c,-1.34)
100 loops, best of 3: 2.21 ms per loop

In [31]: timeit itera(c,x)
100 loops, best of 3: 4.10 ms per loop
In [32]: timeit naive(c,x)
100 loops, best of 3: 4.95 ms per loop

Использование списка в @Paul drapers отвечает, что наша cythonised версия работает в два раза быстрее, чем исходная функция и намного быстрее, чем ietra и наивная:

In [214]: import random

In [215]: c = [random.random() for _ in range(500)]

In [44]: timeit C_Horner(c, -1.34)
10000 loops, best of 3: 18.9 µs per loop    
In [45]: timeit Horner(c, -1.34)
10000 loops, best of 3: 44.6 µs per loop
In [46]: timeit naive(c, -1.34)
10000 loops, best of 3: 167 µs per loop
In [47]: timeit itera(c,-1.34)
10000 loops, best of 3: 75.8 µs per loop