LINUX.ORG.RU
решено Форум — Development  

Производительность - двумерный массив из сдвинутых копий?

 , ,


0

2

Имеется массив a из N элементов:

a = np.arange(4)
a

array([0, 1, 2, 3])

Необходимо получить массив N на N из последовательно сдвинутых копий исходного массива, т.е.

array([[0, 1, 2, 3],
       [3, 0, 1, 2],
       [2, 3, 0, 1],
       [1, 2, 3, 0]])

Пока ничего кроме очевидного:

np.array([np.roll(a, i) for i in range(len(a))])

придумать не удалось. На моей машине производительность такого решения для массива из 1024 элементов - 10 мс.

python -m timeit -s 'import numpy as np; a = np.arange(1024)' 'np.array([np.roll(a, i) for i in range(len(a))])'

100 loops, best of 3: 10.5 msec per loop

Вопрос - можно ли быстрее?

★★★

Последнее исправление: omegatype (всего исправлений: 2)
← Бэкап с помощью git — игнорирование субмодулей
Поставить conky на паузу →
Ответ на: комментарий от anonymous

Пардон, ошибся при копировании - для 10 мс. в коде было именно 1024. Исправил.

omegatype ★★★
() автор топика
Ответ на: комментарий от Solace

Не совсем окно. Если я правильно понимаю, as_strided позволяет получать массив из элементов с заданным шагом. Мне необходимо сдвинуть весь массив.

omegatype ★★★
() автор топика

Заменил np.roll на совсем простенькую функцию, полагающую массив одномерным. С 10.5 мс. сократил до 6.5 мс. Хотелось бы ещё быстрее...

from timeit import timeit

setup = """
import numpy as np

a = np.arange(1024)

def my_roll(a, shift):
    if shift == 0:
        return a
    else:
        return np.concatenate((a[-shift:], a[:len(a) - shift]))
"""

expression = """
np.array([my_roll(a, i) for i in range(len(a))])
"""

N = 1000
print timeit(expression, setup=setup, number=N) / N * 1000, 'ms'
omegatype ★★★
() автор топика
Последнее исправление: omegatype (всего исправлений: 1)
Ответ на: комментарий от Solace

Благодарю за наводку!

Очевидное np.concatenate((a, a)) позволило свести исходную задачу к rolling window, а далее по http://stackoverflow.com/questions/4936620/using-strides-for-an-efficient-mov...

Итоговая реализация 0.02 мс. Пожалуй, достаточно быстро.

from timeit import timeit

setup = """
import numpy as np

a = np.arange(1024)

def full_roll(a, inverse):    
    def rolling_window(a, window):
        shape = a.shape[:-1] + (a.shape[-1] - window + 1, window)
        strides = a.strides + (a.strides[-1],)
        return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)
    
    if inverse:
        return rolling_window(np.concatenate((a, a)), len(a))[:-1]
    else:
        return np.fliplr(rolling_window(np.flipud(np.concatenate((a, a))), len(a))[:-1])
"""

expression = """
full_roll(a, False)
"""

N = 1000
print timeit(expression, setup=setup, number=N) / N * 1000, 'ms'
omegatype ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Бэкап с помощью git — игнорирование субмодулей
Development
Поставить conky на паузу →