Оптимизированное скалярное произведение в Python
Мой лучший совет состоял бы в том, что нет никакой стандартной древовидной структуры данных, потому что существует столько способов, которыми Вы могли реализовать его, что будет невозможно покрыть все основания одним решением. Чем более конкретный решение, тем менее вероятно это применимо к любой данной проблеме. Я даже раздражаюсь из-за LinkedList - что, если я хочу круговой связанный список?
базовая структура, которую необходимо будет реализовать, будет набором узлов, и здесь является некоторыми опциями запустить Вас. Давайте предположим, что класс Узел является базовым классом всего решения.
, Если необходимо только переместиться вниз по дереву, затем классу Узла нужен Список детей.
, Если необходимо переместиться по дереву, тогда классу Узла нужна ссылка на ее родительский узел.
Сборка метод AddChild, который заботится обо всем minutia этих двух точек и Разное логики, которая должна быть реализована (дочерние пределы, сортируя детей, и т.д.)
4 ответа
Ради интереса я написал "d4", который использует numpy:
from numpy import dot
def d4(v1, v2):
check(v1, v2)
return dot(v1, v2)
Мои результаты (Python 2.5.1, XP Pro sp3, 2 ГГц Core2 Duo T7200):
d0 elapsed: 12.1977242918
d1 elapsed: 13.885232341
d2 elapsed: 13.7929552499
d3 elapsed: 11.0952246724
d4 истекло: 56.3278584289 # go numpy!
И, чтобы еще больше повеселиться, я включил psyco:
d0 elapsed: 0.965477735299
d1 elapsed: 12.5354792299
d2 elapsed: 12.9748163524
d3 elapsed: 9.78255448667
d4 elapsed: 54.4599059378
На основании этого я объявляю d0 победителем :)
Update
@kaiser .se: Мне, наверное, следовало упомянуть, что я сначала преобразовал все в массивы numpy:
from numpy import array
v3 = [array(vec) for vec in v1]
v4 = [array(vec) for vec in v2]
# then
t4 = timeit.Timer("d4(v3,v4)","from dot_product import d4,v3,v4")
И я включил check (v1, v2) , так как он включен в другие тесты. Отключение этого параметра даст numpy несправедливое преимущество (хотя похоже, что он мог бы его использовать). Преобразование массива сократилось примерно на секунду (намного меньше, чем я думал).
Все мои тесты проводились с N = 50.
@nikow: Я использую numpy 1.0.4, который, несомненно, старый, вполне возможно, что они ' Он улучшил производительность за последние полтора года с тех пор, как я его установил.
Обновление №2
@ kaiser.se Вау, вы совершенно правы. Я, должно быть, думал, что это списки списков или что-то в этом роде (я действительно понятия не имею, о чем я думал ... +1 для парного программирования).
Как это выглядит:
v3 = array(v1)
v4 = array(v2)
Новые результаты:
d4 elapsed: 3.22535741274
С Psyco:
d4 elapsed: 2.09182619579
d0 все еще побеждает с Psyco, но numpy, вероятно, в целом лучше, особенно с большими наборами данных.
Вчера меня немного смутил мой медленный результат numpy, поскольку предположительно numpy используется для большого количества вычислений и подвергся значительной оптимизации. Однако, очевидно, не удосужился проверить свой результат :)
Я, должно быть, думал, что это списки списков или что-то в этом роде (я действительно понятия не имею, о чем я думал ... +1 для парного программирования).Как это выглядит:
v3 = array(v1)
v4 = array(v2)
Новые результаты:
d4 elapsed: 3.22535741274
С Psyco:
d4 elapsed: 2.09182619579
d0 все еще побеждает с Psyco, но numpy, вероятно, в целом лучше, особенно с большими наборами данных.
Вчера меня немного смутил мой медленный результат numpy, поскольку предположительно numpy используется для большого количества вычислений и подвергся значительной оптимизации. Однако, очевидно, не удосужился проверить свой результат :)
Я, должно быть, думал, что это списки списков или что-то в этом роде (я действительно понятия не имею, о чем я думал ... +1 для парного программирования).Как это выглядит:
v3 = array(v1)
v4 = array(v2)
Новые результаты:
d4 elapsed: 3.22535741274
С Psyco:
d4 elapsed: 2.09182619579
d0 все еще побеждает с Psyco, но numpy, вероятно, в целом лучше, особенно с большими наборами данных.
Вчера меня немного смутил мой медленный результат numpy, поскольку предположительно numpy используется для большого количества вычислений и подвергся значительной оптимизации. Однако, очевидно, не удосужился проверить свой результат :)
Вчера меня немного смутил мой медленный результат numpy, поскольку предположительно numpy используется для большого количества вычислений и подвергся значительной оптимизации. Однако, очевидно, не удосужился проверить свой результат :)
Вчера меня немного смутил мой медленный результат numpy, поскольку предположительно numpy используется для большого количества вычислений и подвергся значительной оптимизации. Однако, очевидно, не удосужился проверить свой результат :)
Я не знаю, как быстрее, но я бы посоветовал:
sum(i*j for i, j in zip(v1, v2))
его намного легче читать, и он не требует даже модулей стандартной библиотеки.
Вот сравнение с numpy. Мы сравниваем подход быстрой карты звездочки с numpy.dot
Во-первых, итерация по обычным спискам Python:
$ python -mtimeit "import numpy as np; r = range(100)" "np.dot(r,r)"
10 loops, best of 3: 316 usec per loop
$ python -mtimeit "import operator; r = range(100); from itertools import izip, starmap" "sum(starmap(operator.mul, izip(r,r)))"
10000 loops, best of 3: 81.5 usec per loop
Затем numpy ndarray:
$ python -mtimeit "import numpy as np; r = np.arange(100)" "np.dot(r,r)"
10 loops, best of 3: 20.2 usec per loop
$ python -mtimeit "import operator; import numpy as np; r = np.arange(100); from itertools import izip, starmap;" "sum(starmap(operator.mul, izip(r,r)))"
10 loops, best of 3: 405 usec per loop
Видя это, кажется, что numpy для массивов numpy является самым быстрым, а затем функциональным Python конструкции, работающие со списками.
Пожалуйста, сравните эту "d2a" функцию с вашей "d3".
from itertools import imap, starmap
from operator import mul
def d2a(v1,v2):
"""
d2a uses itertools.imap
"""
check(v1,v2)
return sum(imap(mul, v1, v2))
map (на Python 2.x, который, как я полагаю, вы используете) неоправданно создает фиктивный список перед вычислением.