Суммарная цифра становится быстрее с большим количеством записей

Question

Я измерил время, необходимое для того, чтобы функция суммы numpy добавила определенное количество значений. Кривые ниже означают количество времени, которое требуется для функции суммы numpy (зеленый) и для стандартного питона для цикла (синий), чтобы скомпоновать все элементы на элемент. Так, например, при использовании функции суммирования numpy на массиве 10 элементов, каждый элемент требует в среднем 2 ^-19 секунд для обработки.

Вот код:

random_vector = np.random.random(10**7) 

def for_sum(vector, n): 
    sum = 0 

    start_time = time.perf_counter() 
    for i in range(n): 
     sum += vector[i] 

    return time.perf_counter() - start_time 

def numpy_sum(vector, n): 
    new_vector = vector[:n] 

    start_time = time.perf_counter() 
    np.sum(new_vector) 

    return time.perf_counter() - start_time 

# determines the number of elements we should sum 
spaced_values = np.logspace(1, 7, num=30, dtype=int) 

# Measure time for for loops, per entry 
for_sum_times_per_entry = np.zeros(0) 
for i in spaced_values: 
    for_sum_times_per_entry = np.append(for_sum_times_per_entry, for_sum(random_vector, i)/i) 

# Measure time for numpy sum function, per entry 
numpy_sum_times_per_entry = np.zeros(0) 
for i in spaced_values: 
    numpy_sum_times_per_entry = np.append(numpy_sum_times_per_entry, numpy_sum(random_vector, i)/i) 

# Plot the amount of time required to sum each entries 
plt.loglog(spaced_values, for_sum_times_per_entry, basex=10, basey=2) 
plt.loglog(spaced_values, numpy_sum_times_per_entry, basex=10, basey=2) 
plt.xlabel("Number of values summed") 
plt.ylabel("Single entry computing time (s)") 
plt.show()  

NumPy кривой сумма показывает, что время обработки, необходимое для 1 элемента становится все ниже и ниже как общее количество элементов, чтобы быть просуммированы увеличивается.

Что это из-за? Мое мнение состоит в том, что функция суммирования numpy имеет определенные накладные расходы, которые увеличивают время обработки. Эти накладные расходы занимают постоянное количество времени, поэтому он становится все менее значительным, когда мы добавляем элементы.

Answer 1

Numpy использует BLAS под капотом, поэтому для numpy.sum вы можете применить логику низкого уровня: если весь массив вписывается в кеш процессора, вы увидите плоский профиль. Кэш L1 на моей машине 64KB, и конечно время вычисления numpy.sum остается плоской до тех пор, пока вы не более чем 64KB записи/64 бит/с плавающей точкой ~ 8000 Поплавок:

Это участок был сгенерирован с

import math 
import numpy 
import perfplot 


def for_sum(a): 
    sum = 0.0 
    for i in range(len(a)): 
     sum += a[i] 
    return sum 


perfplot.show(
     setup=numpy.random.rand, 
     kernels=[for_sum, numpy.sum, sum, math.fsum], 
     labels=['for-sum', 'numpy.sum', 'sum', 'math.fsum'], 
     n_range=[2**k for k in range(15)], 
     xlabel='len(a)', 
     logx=True, 
     logy=True 
     )