Подтвердить что ты не робот

Как векторизовать этот код python?

Я пытаюсь использовать операции NumPy и векторизации, чтобы сделать код кода быстрее. Я, кажется, неправильно понимаю, как векторизовать этот код (возможно, из-за неполного понимания векторизации).

Здесь рабочий код с циклами (A и B - это 2D-массивы заданного размера, уже инициализированные):

for k in range(num_v):
    B[:] = A[:]
    for i in range(num_v):
        for j in range(num_v):
            A[i][j] = min(B[i][j], B[i][k] + B[k][j])
return A

И вот моя попытка векторизации вышеуказанного кода:

for k in range(num_v):
    B = numpy.copy(A)
    A = numpy.minimum(B, B[:,k] + B[k,:])
return A

Для тестирования этих данных я использовал следующее, с приведенным выше кодом в функции "algorithm":

def setup_array(edges, num_v):
    r = range(1, num_v + 1)
    A = [[None for x in r] for y in r]  # or (numpy.ones((num_v, num_v)) * 1e10) for numpy
    for i in r:
        for j in r:
            val = 1e10
            if i == j:
                val = 0 
            elif (i,j) in edges:
                val = edges[(i,j)]
            A[i-1][j-1] = val 
    return A

A = setup_array({(1, 2): 2, (6, 4): 1, (3, 2): -3, (1, 3): 5, (3, 6): 5, (4, 5): 2, (3, 1): 4, (4, 3): 8, (3, 4): 6, (2, 4): -4, (6, 5): -5}, 6) 
B = []
algorithm(A, B, 6)

Ожидаемый результат и то, что я получаю с первым кодом:

[[0, 2, 5, -2, 0, 10] 
 [8, 0, 4, -4, -2, 9]
 [4, -3, 0, -7, -5, 5]
 [12, 5, 8, 0, 2, 13]
 [10000000000.0, 9999999997.0, 10000000000.0, 9999999993.0, 0, 10000000000.0]
 [13, 6, 9, 1, -5, 0]]

Вторая (векторизованная) функция возвращает:

[[ 0. -4.  0.  0.  0.  0.]
 [ 0. -4.  0. -4.  0.  0.]
 [ 0. -4.  0.  0.  0.  0.]
 [ 0. -4.  0.  0.  0.  0.]
 [ 0. -4.  0.  0.  0.  0.]
 [ 0. -4.  0.  0. -5.  0.]]

Что мне не хватает?

4b9b3361

ОТВЕТЫ

Ответ 1

Проблема вызвана широковещательной передачей в строке:

A = numpy.minimum(B, B[:,k] + B[k,:])

B - размер 6 на 6, B [:, k] - массив с 6 элементами, B [k,:] - массив с 6 элементами.

(Поскольку вы используете тип массива numpy, оба B [:, k] и B [k,:] возвращают массив ранга 1 формы N)

Numpy автоматически изменяет размеры для соответствия:

  • Первый B [:, k] добавляется к B [k,:], чтобы получить результат промежуточной матрицы с 6 элементами. (Это не то, что вы намеревались).
  • Во-вторых, этот 6-элементный массив передается на матрицу 6 на 6, повторяя строки
  • В-третьих, вычисляется минимум исходной матрицы и эта широковещательная матрица.

Это означает, что ваш numpy-код эквивалентен:

for k in range(num_v):
   B[:] = A[:]
   C=[B[i][k]+B[k][i] for i in range(num_v)]
   for i in range(num_v):
      for j in range(num_v):
         A[i][j] = min(B[i][j], C[j])

Самый простой способ исправить ваш код - использовать тип матрицы вместо типа массива:

A = numpy.matrix(A)
for k in range(num_v):
    A = numpy.minimum(A, A[:,k] + A[k,:])

Тип матрицы использует более строгие правила вещания, поэтому в этом случае:

  • A [:, k] распространяется на матрицу 6 на 6, повторяя столбцы
  • A [k,:] продолжается до матрицы 6 на 6, повторяя строки
  • Распространенные матрицы объединяются для создания матрицы 6 на 6.
  • Применяется минимум

Ответ 2

Обычно вы хотите векторизовать код, потому что считаете, что он работает слишком медленно.
Если ваш код слишком медленный, то я могу сказать вам, что правильное индексирование сделает его быстрее.
Вместо A[i][j] вы должны написать A[i, j] - это позволяет избежать временной копии массива (sub).
Поскольку вы делаете это во внутренней петле вашего кода, это может быть очень дорогостоящим.

Посмотрите здесь:

In [37]: timeit test[2][2]
1000000 loops, best of 3: 1.5 us per loop

In [38]: timeit test[2,2]
1000000 loops, best of 3: 639 ns per loop

Сделайте это последовательно в своем коде - я твердо верю, что решает уже вашу проблему с производительностью!

Сказав, что...

... здесь я беру на себя, как векторизовать

for k in range(num_v):
    numpy.minimum(A, np.add.outer(A[:,k], A[k,:]), A)
return A

numpy.minimum будет сравнивать два массива и возвращать элемент поменьше из двух элементов. Если вы передадите третий аргумент, он выведет результат. Если это входной массив, вся операция находится на месте.

Как объясняет Питер де Ривай, в вашем решении есть проблема с трансляцией, но математически то, что вы хотите сделать, это какой-то внешний продукт по сравнению с добавлением двух векторов. Поэтому вы можете использовать внешнюю операцию над функцией добавления.

У NumPys двоичные ufuncs есть специальные методы для выполнения определенных видов специальные векторизованные операции, такие как уменьшение, накопление, сумма и внешний.