Объясните разницу в скорости между приложением numpy vectorized function VS python for loop

Я реализовал систему взвешивания TF-IDF на наборе из 42000 изображений, каждая из которых состояла из 784 пикселей. Это в основном матрица 42000 на 784.

В первом методе я попытался использовать явные циклы и занял более 2 часов.

def tfidf(color,img_pix,img_total):
    if img_pix==0:
        return 0
    else:
        return color * np.log(img_total/img_pix)

...

result = np.array([])
for img_vec in data_matrix:
    double_vec = zip(img_vec,img_pix_vec)
    result_row = np.array([tfidf(x[0],x[1],img_total) for x in double_vec])
    try:
        result = np.vstack((result,result_row))
    # first row will throw a ValueError since vstack accepts rows of same len
    except ValueError:
        result = result_row

Второй метод: я попытался использовать матрицы numpy и занял менее 5 минут. Обратите внимание, что data_matrix, img_pix_mat - это матрицы 42000 на 784, а img_total - скаляр.

result = data_matrix * np.log(np.divide(img_total,img_pix_mat))

Я надеялся, что кто-то сможет объяснить огромную разницу в скорости.

Авторы следующей статьи, озаглавленной "Массив NumPy: структура для численного численного вычисления" (http://arxiv.org/pdf/1102.1523.pdf), указываем в верхней части страницы 4, что они наблюдают 500-кратное увеличение скорости за счет векторизованного вычисления. Я предполагаю, что увеличение скорости, которое я вижу, связано с этим. Тем не менее, я хотел бы сделать еще один шаг и спросить, почему числовые векторизованные вычисления намного быстрее, чем стандартные петли python?

Кроме того, возможно, вы, ребята, знаете другие причины, почему первый метод медленный. Нужно ли пытаться/кроме структур иметь большие накладные расходы? Или, возможно, формирование нового np.array для каждого цикла занимает много времени?

Спасибо.

Ответ 1

Из-за внутренней работы numpy (насколько я знаю, numpy работает с C внутри, поэтому все, что вы нажимаете на numpy, на самом деле намного быстрее, потому что оно находится на другом языке)

изменить: вынимая zip и заменяя его vstack, должен идти быстрее (zip имеет тенденцию идти медленно, если аргументы очень большие, а vstack быстрее) (но это также то, что помещает его в numpy (таким образом, в C), а zip - python)

и да, если я правильно понимаю - не уверен в этом, вы делаете 42k раз блок try/except, который определенно должен быть плохим для скорости,

Тест:

T=numpy.ndarray((5,10))
for t in T:
print t.shape

приводит к (10,)

Это означает, что да, если ваши матрицы - это матрицы 42kx784, вы пытаетесь в 42k раз использовать блок try-except, я предполагаю, что это должно влиять на время вычислений, а также каждый раз, когда вы делаете zip каждый раз, но не уверен, что это будет основной причиной,

(так что каждый из ваших 42k раз, когда вы запускаете свой материал, занимает 0.17 сек., я вполне уверен, что блок try/except не занимает 0.17 секунды, но, возможно, накладные расходы, которые он вызывает или так, вносит свой вклад в это?

попробуйте изменить следующее:

double_vec = zip(img_vec,img_pix_vec)
result_row = np.array([tfidf(x[0],x[1],img_total) for x in double_vec])

result_row=np.array([tfidf(img_vec[i],img_pix_vec[i],img_total) for i in xrange(len(img_vec))])

что, по крайней мере, избавляется от оператора zip, но не уверен, что выражение zip занимает ваше время на один мин или почти на два часа (я знаю, что zip медленный, по сравнению с numpy vstack, но не подскажут, даст вам двухчасовое увеличение времени)

Ответ 2

numpy написано на C. Разница, которую вы видите, не связана с чем-то вроде как SSE-векторизация; это просто, что реализация C не должна проходить тонны обработки диспетчеризации времени и проверки исключений и т.д., что реализация Python проходит.