Самый быстрый способ суммировать несколько векторов NumPy, имеющих разную длину

Question

Постановка задачи проста: задано произвольное количество NumPy одномерных векторов с плавающей точкой, как таковое:

v1 = numpy.array([0, 0, 0.5, 0.5, 1, 1, 1, 1, 0, 0])
v2 = numpy.array([4, 4, 4, 5, 5, 0, 0])
v3 = numpy.array([1.1, 1.1, 1.2])
v4 = numpy.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10])

Какой самый быстрый способ их сложить?

many_vectors = [v1, v2, v3, v4]

Использование функции прямой суммы не будет работать, поскольку они могут иметь произвольную неравную длину:

>>> result = sum(many_vectors)
ValueError: operands could not be broadcast together with shapes (10,) (7,)

Вместо этого можно обратиться к библиотеке pandas, которая предложит простой параметр fillna, чтобы избежать этой проблемы.

 >>> pandas.DataFrame(v for v in many_vectors).fillna(0.0).sum().values
 array([ 5.1,  5.1,  5.7,  5.5,  6. ,  1. ,  1. ,  1. ,  0. ,  0. ,  0. ,
    0. ,  0. ,  0. ,  0. , 10. ])

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

In [9]: %timeit pandas.DataFrame(v for v in many_vectors).fillna(0.0).sum().values
1.16 ms ± 97.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Answer 1

Подход № 1

При таких огромных размерах входного массива и огромном количестве массивов мы должны эффективно использовать память и, следовательно, предлагать циклический, который итеративно добавляет один массив за раз -

many_vectors = [v1, v2, v3, v4] # list of all vectors

lens = [len(i) for i in many_vectors]
L = max(lens)
out = np.zeros(L)
for l,v in zip(lens,many_vectors):
    out[:l] += v

Подход № 2

Другой, почти векторизованный, с masking для генерации регулярного 2D массива из списка векторов / массивов неправильной формы и последующего суммирования по столбцам для окончательного вывода -

# Inspired by https://stackoverflow.com/a/38619350/ @Divakar
def stack1Darrs(v):
    lens = np.array([len(item) for item in v])
    mask = lens[:,None] > np.arange(lens.max())
    out_dtype = np.result_type(*[i.dtype for i in v])
    out = np.zeros(mask.shape,dtype=out_dtype)
    out[mask] = np.concatenate(v)
    return out

out = stack1Darrs(many_vectors).sum(0)

Answer 2

Кредит идет @Divakar. Этот ответ только расширяется и улучшается после его ответа. В частности, я переписал функции в соответствии с нашим руководством по стилю и рассчитал их время.

Возможны два подхода:

Подход № 1

###############################################################################
def sum_vectors_with_padding_1(vectors):
    """Given an arbitrary amount of NumPy one-dimensional vectors of floats,
    do an element-wise sum, padding with 0 any that are shorter than the
    longest array (see https://stackoverflow.com/questions/56166217).
    """
    import numpy
    all_lengths = [len(i) for i in vectors]
    max_length  = max(all_lengths)
    out         = numpy.zeros(max_length)
    for l,v in zip(all_lengths, vectors): out[:l] += v
    return out

Подход № 2

###############################################################################
def sum_vectors_with_padding_2(vectors):
    """Given an arbitrary amount of NumPy one-dimensional vectors of floats,
    do an element-wise sum, padding with 0 any that are shorter than the
    longest array (see https://stackoverflow.com/questions/56166217).
    """
    import numpy
    all_lengths = numpy.array([len(item) for item in vectors])
    mask        = all_lengths[:,None] > numpy.arange(all_lengths.max())
    out_dtype   = numpy.result_type(*[i.dtype for i in vectors])
    out         = numpy.zeros(mask.shape, dtype=out_dtype)
    out[mask]   = numpy.concatenate(vectors)
    return out.sum(axis=0)

Сроки

>>> v1 = numpy.array([0, 0, 0.5, 0.5, 1, 1, 1, 1, 0, 0])
>>> v2 = numpy.array([4, 4, 4, 5, 5, 0, 0])
>>> v3 = numpy.array([1.1, 1.1, 1.2])
>>> v4 = numpy.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10])
>>> many_vectors = [v1, v2, v3, v4]
>>> %timeit sum_vectors_with_padding_1(many_vectors)
12 µs ± 645 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit sum_vectors_with_padding_2(many_vectors)
22.6 µs ± 669 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Так что, похоже, способ 1 еще лучше!