Как заполнить 3D-массив в numpy функциональными значениями с той же скоростью, что и Java?

Я попытался смоделировать воксели трехмерного цилиндра с помощью следующего кода:

import math
import numpy as np

R0 = 500
hz = 1

x = np.arange(-1000, 1000, 1)
y = np.arange(-1000, 1000, 1)
z = np.arange(-10, 10, 1)

xx, yy, zz = np.meshgrid(x, y, z)


def density_f(x, y, z):
    r_xy = math.sqrt(x ** 2 + y ** 2)
    if r_xy <= R0 and -hz <= z <= hz:
        return 1
    else:
        return 0


density = np.vectorize(density_f)(xx, yy, zz)

и на вычисление потребовалось много минут.

Эквивалентный неоптимальный код Java работает 10-15 секунд.

Как заставить Python вычислять воксели с одинаковой скоростью? Где оптимизировать?


person Dims    schedule 26.10.2018    source источник
comment
Ваша биография перечисляет MATLAB. Изначально это была оболочка для матричного кода Фортрана. Чтобы получить хорошую скорость, вы должны были мыслить в терминах целых массивов. Новый MATLAB имеет jit-компилятор, который позволяет вам «обманывать» и писать итеративный код. numpy больше похож на более старый MATLAB. Чтобы обойти это, вы использовали добавленные пакеты, такие как cython и numba, которые создают собственный скомпилированный код. Я предполагаю, что вы достаточно знакомы с информатикой, чтобы понимать разницу между C, Java и Python.   -  person hpaulj    schedule 27.10.2018
comment
Часто возникает вопрос, как сделать быструю векторизацию. Вот более простой недавний пример: stackoverflow.com/questions/53016316/   -  person hpaulj    schedule 27.10.2018
comment
Немного не связано с вашим вопросом, но сравните квадрат расстояния xy с предварительно вычисленным квадратом радиуса - вы можете сохранить sqrt на каждой итерации, что должно иметь большое значение.   -  person Artur Biesiadowski    schedule 29.10.2018


Ответы (3)


Пожалуйста, не используйте .vectorize(..), это неэффективно, так как он все равно будет выполнять обработку на уровне Python. .vectorize() следует использовать только в крайнем случае, если, например, функция не может быть вычислена "в большом объеме", потому что ее "структура" слишком сложна.

Но вам не нужно использовать здесь .vectorize, вы можете реализовать свою функцию для работы с массивами с помощью:

r_xy = np.sqrt(xx ** 2 + yy ** 2)
density = (r_xy <= R0) & (-hz <= zz) & (zz <= hz)

или даже немного быстрее:

r_xy = xx * xx + yy * yy
density = (r_xy <= R0 * R0) & (-hz <= zz) & (zz <= hz)

Это создаст массив логических значений 2000200020. Мы можем использовать:

intdens = density.astype(int)

чтобы построить массив из ints.

Распечатать массив здесь довольно сложно, но всего он содержит 2'356'047 единиц:

>>> density.astype(int).sum()
2356047

Контрольные показатели. Если я запускаю это локально 10 раз, я получаю:

>>> timeit(f, number=10)
18.040479518999973
>>> timeit(f2, number=10)  # f2 is the optimized variant
13.287886952000008

Таким образом, в среднем мы вычисляем эту матрицу (включая приведение к ints) за 1,3–1,8 секунды.

person Willem Van Onsem    schedule 26.10.2018
comment
А как насчет более сложных случаев с if-s? Могу ли я эффективно применять функции поэлементно? - person Dims; 27.10.2018
comment
P.S. Почему вы используете одиночные амперсанды? - person Dims; 27.10.2018
comment
@Dims: потому что and в Python оценивает правдивость, а массив не имеет правдивости. & является поэлементным и состоит из двух матриц. Чтобы написать это в таком варианте, может потребоваться определенное творчество. Это то, что со временем можно освоить с опытом. - person Willem Van Onsem; 27.10.2018
comment
Спасибо, но объясните, пожалуйста, что делать с более сложными функциями, где есть if, исключения и т. Д., Которые я не могу записать как одно векторизованное выражение? - person Dims; 27.10.2018
comment
@Dims: нет никаких if и т. Д., Вам нужно закодировать это логическим образом. То же и для исключений. Таким образом, требуется математическая инженерия. - person Willem Van Onsem; 27.10.2018
comment
Извините, в моем случае есть «если». А также вложенные вызовы других функций и т. Д. И во многих случаях просто неоптимально размещать все промежуточные результаты в виде массивов ND. - person Dims; 27.10.2018
comment
@Dims: well numpy предназначен для массовых операций, таких как вычисление поэлементной суммы двух массивов. Python, с другой стороны, очень медленный для отдельных операций, поэтому я думаю, что тогда оба варианта не сработают. Но я видел, что некоторые проблемы, которые сначала выглядят довольно сложными, оказываются элементарными операциями или сверточными операциями и т. Д. Обратите внимание, что операторы if в целом довольно медленные из-за конвейерной обработки, поэтому иногда лучше просто вычислить и то, и другое. операнды вместо использования ifs - person Willem Van Onsem; 27.10.2018
comment
Если не медленный, если он позволит избежать вычисления 90% пространства - person Dims; 27.10.2018

Вы также можете использовать скомпилированную версию функции для расчета плотности. Вы можете использовать для этого cython или numba. Я использую numba для jit-компиляции функции вычисления плотности в ans, поскольку это так же просто, как вставить декоратор .

Плюсы:

  • Вы можете написать if условия, которые упоминаете в своих комментариях.
  • Немного быстрее, чем версия numpy, упомянутая в ответах @Willem Van Onsem, поскольку нам нужно перебирать логический массив для вычисления суммы в density.astype(int).sum().

Минусы:

  • Напишите уродливую трехуровневую петлю. Теряет красоту уникального решения для лайнеров.

Код:

import numba as nb
@nb.jit(nopython=True, cache=True)
def calc_density(xx, yy, zz, R0, hz):
    threshold = R0 * R0
    dimensions = xx.shape

    density = 0
    for i in range(dimensions[0]):
        for j in range(dimensions[1]):
            for k in range(dimensions[2]):
                r_xy = xx[i][j][k] ** 2 + yy[i][j][k] ** 2
    
                if(r_xy <= threshold and -hz <= zz[i][j][k] <= hz):
                    density+=1
    return density

Продолжительность:

Решение Виллема Ван Онсема, вариант f2: 1,28 с без суммы, 2,01 с суммой.

Решение Numba (calc_de density, при втором запуске, чтобы уменьшить время компиляции): 0,48 с.

Как предлагается в комментариях, нам также не нужно рассчитывать сетку. Мы можем напрямую передать x, y, z функции. Таким образом:

@nb.jit(nopython=True, cache=True)
def calc_density2(x, y, z, R0, hz):
    threshold = R0 * R0
    dimensions = len(x), len(y), len(z)

    density = 0
    for i in range(dimensions[0]):
        for j in range(dimensions[1]):
            for k in range(dimensions[2]):
                
                r_xy = x[i] ** 2 + y[j] ** 2
                if(r_xy <= threshold and -hz <= z[k] <= hz):
                    density+=1
    return density

Теперь, для честного сравнения, мы также включаем время np.meshgrid в ответ @Willem Van Onsem. Продолжительность:

Решение Виллема Ван Онсема, вариант f2 (включая время np.meshgrid): 2,24 с

Решение Numba (calc_de density2, при втором запуске, чтобы уменьшить время компиляции): 0,079 с.

person Deepak Saini    schedule 29.10.2018
comment
1) Не используйте глобальные переменные! В Numba каждая глобальная переменная является постоянной времени компиляции. Если вы измените глобальную переменную и снова запустите свою функцию, Numba не распознает эти изменения, что затруднит отладку ошибок. 2) Небольшое изменение (передача x, x, z напрямую) приводит к увеличению производительности в 10 раз. 3) Распараллеливание даст еще один фактор количества ядер. - person max9111; 29.10.2018
comment
@ max9111 не могли бы вы объяснить или примеры (2) и (3)? - person Dims; 29.10.2018
comment
@ max9111, спасибо. 1) да, действительно. Запамятовал. Отредактировал для включения 2). Кажется, не получается 3). Я предполагаю, что бухгалтерский учет, необходимый для распараллеливания, затмевает прибыль для конкретного размера. - person Deepak Saini; 29.10.2018
comment
@Deepak Saini Я опубликовал довольно дублированный ответ, не считая распараллеливания. Я думаю, что было бы лучше добавить параллельный подход к вашему ответу, и я удаляю свой впоследствии ... Кстати: cache = True не работает, если для параметра paralization установлено значение True. - person max9111; 29.10.2018
comment
@ max9111, конечно. Сделаю. - person Deepak Saini; 29.10.2018

Это подразумевается как пространный комментарий к ответу Дипака Шайни.

Главное изменение - не использовать координаты, сгенерированные np.meshgrid, которые содержат ненужные повторения. Это не рекомендуется, если вы можете этого избежать (как с точки зрения использования памяти, так и производительности).

Код

import numba as nb
import numpy as np

@nb.jit(nopython=True,parallel=True)
def calc_density_2(x, y, z,R0,hz):
    threshold = R0 * R0

    density = 0
    for i in nb.prange(y.shape[0]):
        for j in range(x.shape[0]):
            r_xy = x[j] ** 2 + y[i] ** 2
            for k in range(z.shape[0]):
                if(r_xy <= threshold and -hz <= z[k] <= hz):
                    density+=1

    return density

Время

R0 = 500
hz = 1

x = np.arange(-1000, 1000, 1)
y = np.arange(-1000, 1000, 1)
z = np.arange(-10, 10, 1)

xx, yy, zz = np.meshgrid(x, y, z)

#after the first call (compilation overhead)
#calc_density_2          9.7 ms
#calc_density_2 parallel 3.9 ms
#@Deepak Saini           115 ms
person max9111    schedule 29.10.2018