Ускорение операций списка в Python с помощью C

Question

Предположим, что p и q - это списки в Python общей длины n. Каждый список содержит содержимое range(n) в некотором порядке (что важно!). Можно предположить, что n мал (т. Е. Не превышает 2^16). Теперь я определяю операцию по этим спискам, используя следующий код

def mult(p,q): 
    return [q[i] for i in p] 

Ясно mult(p,q) снова список, содержащий содержимое range(n) в некотором порядке. Этот код python является примером состава перестановок (см. http://en.wikipedia.org/wiki/Permutation).

Я бы хотел, чтобы этот код работал как можно быстрее в Python. Я попытался заменить p и q на массивы numpy, чтобы узнать, не ускорит ли это процесс, но разница была незначительной при тестах времени (обратите внимание, что numpy не рассчитан на вышеупомянутую функцию). Я также написал расширение C для Python, чтобы попытаться ускорить процесс, но это, похоже, не помогло (я, однако, использовал такие функции, как PySequence_Fast_GET_ITEM, которые, вероятно, те же функции, что и сам Python).

Можно ли написать новый тип для Python в C (как описано здесь http://docs.python.org/2/extending/newtypes.html), который имел бы свойство, что функция mult была бы быстрой (er)? Или, действительно, напишите любую программу в C, которая даст Python такой тип.

Я задаю этот вопрос, чтобы увидеть, не лает ли я за неправильное дерево. В частности, существует ли, по сути, неотъемлемое свойство Python, что означает, что это никогда не ускорится? Меня больше всего интересует Python 2.7, но было бы интересно узнать о любых решениях для Python 3+.

Answer 1

Как отмечает Абид Рахман, использование NumPy правильно - это лучше, чем реализация собственной структуры данных C.

import numpy as np 

p = np.array(range(1000)) 
q = np.array(range(1000)) 

%timeit [q[i] for i in p] 
# 1000 loops, best of 3: 312 us per loop 

%timeit q[p] 
# 100000 loops, best of 3: 4.31 us per loop 

NumPy в основном делает то, что вы надеялись сделать самостоятельно (нажмите массив доступа до уровня C). Однако, если вы просто выполняете понимание списка, весь цикл будет обрабатываться на Python, поэтому он будет не намного быстрее оригинала с регулярными списками Python.