Нахождение, где встречается каждый уникальный подмассив

Question

Ситуация:

Я заполняю массив формы (2N, 2N), где N близко к 8000, назовем его A, со значениями, которые я получаю из функциииспользуя вложенные циклы for для вызова функции, которая принимает в качестве аргумента подмассивы shape (2,) из последнего измерения массива shape (N, N, 2), назовите его B.

Это, очевидно, дорогои хотя мне не удалось векторизовать эту часть кода (любая помощь в этом направлении также очень приветствуется), я знаю, что B имеет много повторяющихся подмассивов в последнем измерении.Итак, я хочу выяснить уникальные подмассивы и где каждый встречается.Тогда заполнение A будет ускоряться путем итерации по каждому из этих уникальных подмассивов и заполнения всех позиций, где это происходит, значением, возвращаемым функцией, которая была бы вычислена только один раз.

Что яЯ сделал следующее, но это, кажется, не самый простой способ продолжить, или самый тупой способ сделать это.

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

translat_avg_disloc_matrix = np.zeros([2*n, 2*n])

for i in range(n):
    for alpha in range(2):

        for j in range(n):
            for beta in range(2):

                    translat_avg_disloc_matrix[2*i+alpha,2*j+beta] = average_lat_pos(alpha, beta, b_matrix[i][j])

Хотя я могу найти уникальные подмассивы, выполнив что-то вроде того, что здесь сделано: Эффективно посчитать количество экземпляров уникальных подмассивов в NumPy? ), У меня были проблемы с поиском индексов, где каждый из них встречается.

То, что я пробовал делает что-то вроде:

1) Вычисляет норму подмассивов в последнем измерении B на norm = (B*B).sum(axis=2) и вычисляет нормуподмассивы в последнем измерении B-1

на norm_ = ((B-1)*(B-1)).sum(axis=2)

2) Изменение этих массивов для этих двух норм с помощью norm.reshape((norm.size,1))

3) Создание матриц плиткикак tile_norm = np.tile(norm.T, (len(norm),1))

4) Затем делаем np.unique(np.non_zero(np.abs(tile_norm - norm)+np.abs(tile_norm_-norm_) == 0), axis=0), что дает нам что-то вроде: array([[0, 0, 0, 4], [4, 4, 4, 0]]), где в каждой строке нули указывают, что эти индексы соответствуют одному и тому же (2,) в матрице B.

Словом, я нахожу (2,) массивы, нормы которых совпадают как есть, и которые также согласуются, когда 1 вычтено из них - два уравнения, две переменные.

ЧтоЯ ищу - это способ найти, где каждый из уникальных подмассивов встречается в B, так что использование некоторой необычной индексации позволит мне заполнить матрицу без повторных вызовов функции average_lat_pos (повторение здесь означает вызовдля той же (альфа, бета, (2,) массива) упорядоченной пары).

Answer 1

Одним простым приемом было бы хранить average_lat_pos аргументы в словаре.Поэтому, если ключ находится в словаре, возвращайте его значение без необходимости вычислять average_lat_pos для дублирующихся аргументов.Так как функция average_lat_pos недоступна, я использую фиктивную функцию как:

def average_lat_pos(alpha, betha, td):
    result = 0
    for i in range(1000):
        result += 1
    return result

и окончательный код:

import numpy as np

def average_lat_pos_1(alpha, betha, td):
    get_result = dictionary.get((alpha, betha, td[0], td[1]), 'N')
    if get_result == 'N':
        result = 0
        for i in range(1000):
            result += 1
        dictionary[(alpha, betha, td[0], td[1])] = result
        return result
    else:
        return get_result

def average_lat_pos_2(alpha, betha, td):
    result = 0
    for i in range(1000):
        result += 1
    return result


N = 500
B = np.random.rand(N*N*2) * 100
B = np.floor(B)
B = B.reshape(N,N,2)

dictionary = dict()
A = np.empty([2*N, 2*N])
for i in range(2*N):
    for j in range(2*N):
        A[i, j] = average_lat_pos_1(i%2, j%2, B[i//2, j//2])

Для N = 500, average_lat_pos_1 выполняетпримерно в 10 раз быстрее чем average_lat_pos_2

Answer 2

Векторизация часто лучше.небольшая перестройка вашей функции облегчает работу:

import numpy as np
def average_lat_pos(a,b,x,y):  # all arguments are scalars
    return a*x+2*b*y           # as example

n=1000    
B=np.random.rand(n,n,2)


def loops():
    A=np.empty((2*n,2*n))
    for i in range(n):
        for alpha in range(2):

          for j in range(n):
            for beta in range(2):

              A[2*i+alpha,2*j+beta] = average_lat_pos(alpha, beta, 
              B[i,j,0],B[i,j,1])
    return A

Для векторизации просто преобразуйте уровни цикла в соответствующие измерения:

Z=average_lat_pos(np.arange(2).reshape(1,2,1,1),np.arange(2).reshape(1,1,1,2),
B[:,:,0].reshape(n,1,n,1),B[:,:,1].reshape(n,1,n,1)).reshape(2*n,2*n)

Тесты:

np.allclose(loops(),Z)
Out[105]: True

%timeit loops()
3.73 s ± 9.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit average_lat_pos(np.arange(2).reshape(1,2,1,1),np.arange(2).reshape(1,1,1,2),
   B[:,:,0].reshape(n,1,n,1),B[:,:,1].reshape(n,1,n,1)).reshape(2*n,2*n)
38.7 ms ± 211 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit np.unique(B,axis=2)
1.31 s ± 6.12 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

np.unique подразумевает операцию O(n ln n), которая убьет любое потенциальное усиление.

Но еще лучше здесь, используйте numba, украшая две функции:

@numba.njit
def average_lat_pos(a,b,x,y):
   ....

@numba.njit
def loops(B):
   ....

затем

%timeit loops(B)
3.04 ms ± 34.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)


it's now 1000x faster.