0

Имеется массив:

[0, 1, -2, -3, 4, 5, -6]

С помощью следующего кода добиваемся необходимого результата:

for i in range(matrix.shape[0] - 1):
    matrix[i + 1] += matrix[i]
    if matrix[i + 1] > 0:
        matrix[i + 1] = 0

Собственно необходимы результат:

[0, 0, -2, -5, -1, 0, -6]

Как несложно догадаться код крайне медленный (решение задачи "в лоб"). Как получить необходимый результат с использование numpy и без использования циклов?

9
  • Если размеры массива не в миллиардах, то можно не париться. Я замерил время работы: для массива в 7000 элементов алгоритм отработал за 0.00225 секунд. А для 7000000 за 2.641 сек. Да и если вас волнует скорость, напишите на си функцию и подключите к питону, тогда будет быстрее
    – gil9red
    27 окт 2016 в 9:51
  • 1
    Что значит "крайне медленный" сколько времени код на вашей машине занимает. Сколько вы хотите, чтобы он занимал. Какой тип данных (int, float)? Какой размер массива? Сколько памяти доступно? Какой контекст задачи?
    – jfs
    27 окт 2016 в 13:58
  • Массив float32 из 25 миллионов значений. Расчёт цикла занимает порядка 10 сек. Выполнение остальной части кода занимает 12 сек. Итого время выполнения увеличивается почти в два раза. С учётом что данный цикл за время выполнения одного шага программы надо выполнить 300 раз, получается ну ооооочень медленно. Для примера расчёт кумулятивной суммы того же массива циклом занимает 8 сек. А вот после применения функции кум суммы из нумпай. Около 6мс. Следовательно думал что возможно получить нечто подобное и для цикла выше.
    – mihail
    31 окт 2016 в 5:35
  • В таком случае, cython решение из моего ответа хорошо работает (int[:] на float[:] замените)—на моей машине ~0.1 секунды для 25 миллионов float32 (для сравнения np.cumsum(a) в полтора раза медленнее). Если бы было больше возможности для параллелизации, то можно было бы theano попробовать, чтобы на GPU numpy выражения считать). Даже без GPU, так как я использую nogil, то вы можете разные массивы одновременно в разных потоках считать.
    – jfs
    31 окт 2016 в 12:35
  • Насчёт numpy. Следует уточнять какой именно. Т.к. например intel python. В котором numpy собран с MKL показывает результаты очень близкие к си. А в некоторых решениях и обгоняет его (т.к. используется множество возможных оптимизаций под процессоры intel). Мой не самый шустрый процессор и тот показал результат минимум в два раза быстрее. Плюс заметил что при выполнении той же кумсуммы и других функций numpy загрузка идёт всех 8ми ядер процессора вплоть до общего уровня 80-90%. Отсюда я и ищу возможность заменить большее число кода функциями numpy по максимуму. Theano тоже вариант(но не простой)
    – mihail
    31 окт 2016 в 12:57

2 ответа 2

2

Чтобы получить скорости сравнимые с numpy.cumsum() для больших массивов, можно Cython использовать:

cpdef void clipped_cumsum(int[:] a) nogil:
    cdef Py_ssize_t i, n = a.shape[0]
    for i in range(n-1):
        a[i+1] += a[i]
        if a[i+1] > 0:
            a[i+1] = 0

Для примера, можно сохранить этот код в clipped_cumsum.pyx файл и выполнить pip install cython, чтобы попробовать:

#!/usr/bin/env python
import numpy as np
import pyximport # $ pip install cython
pyximport.install() # compile on-the-fly
from clipped_cumsum import clipped_cumsum

a = np.array([0, 1, -2, -3, 4, 5, -6], dtype=np.intc)
clipped_cumsum(a)
print(a) # -> [ 0  0 -2 -5 -1  0 -6]

pyximport модуль из cython пакета позволяет налету скомпилировать clipped_cumsum.pyx файл, что делает доступным модуль расширения clipped_cumsum.

Для крошечных массивов как в вашем примере, подобные изменения кода навряд ли будут полезны.

Для a.repeat(1000_000) массива, Cython версия с явным типом (int[:]) ~100 раз быстрее версии, которая работает с Питон int на моей машине. Можно ещё ускорить, если выключить проверки при индексировании (boundscheck=False, wraparound=False), но вероятно уже существующего прироста достаточно и проверки можно оставить для будущих модификаций кода.

0

С numpy не знаком, но если нужно без циклов, то можно так:

from itertools import accumulate

func = lambda a, b: min(a+b, 0)

matrix = list(accumulate(matrix, func))

На последовательности из миллиона элементов так получается стабильно на 5-10% быстрее, чем с циклами.

(Тестировал на обычном списке, т.к. numpy не установлен, но думаю, результат будет аналогичен).

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.