Блог

Как я могу заменить несколько экземпляров шаблона в большом массиве 2D numpy на меньший массив 2D numpy?

Я ищу векторизованное решение с использованием логической маски, чтобы минимизировать влияние на производительность, потому что большой массив, с которым я работаю, будет состоять из миллионов строк.

Например:

 #Large array
largeArr = np.array([
    [0, 1, 1],
    [0, 1, 1],
    [0, 1, 1],
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
    [0, 1, 1],
    [0, 1, 1],
    [0, 1, 1],
    [0, 0, 0],
    [0, 0, 0],
    [3, 2, 0],
    [3, 2, 0],
    [3, 2, 0],
    [3, 2, 0],
    [0, 0, 0],
    [0, 0, 0],
    [3, 2, 0],
    [3, 2, 0],
    [3, 2, 0],
    [3, 2, 0],
    [0, 0, 0]
])
 

Я хотел бы заменить разделы 3 последовательными строками [0, 1, 1] , содержащими

 pattern1 = [
    [0, 2, 1],
    [0, 2, 2],
    [0, 2, 3]
]
 

Затем я хотел бы заменить разделы 4 последовательными строками [3, 2, 0] , содержащими

 pattern2 = [
    [5, 2, 1],
    [5, 3, 2],
    [5, 4, 3],
    [5, 5, 4]
]
 

Ожидаемый результат:

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

Будет несколько шаблонов для поиска и замены, каждый со своим собственным массивом замены. Цель состоит в том, чтобы перебирать предоставленные строки поиска и шаблоны замены по одной за раз.

Строка поиска всегда представляет собой одну строку, повторяемую столько раз, сколько строк в шаблоне замены.

Я предполагаю, что все ваши количества являются массивами, а не списками. Если это не так, заверните их в np.array :

 search = np.array([0, 1, 1])
pattern = np.array(pattern1)
 

Размер блока задается

 n = len(pattern)  # or pattern.shape[0]
 

Я предполагаю, что вы хотите заменить только неперекрывающиеся сегменты. Таким образом, в то время как шесть строк search составляют ровно два экземпляра pattern в выходных данных, семь строк составляют два экземпляра pattern и экземпляр search .

Поиск шаблона прост. Начните с создания маски того, где строки соответствуют шаблону:

 mask = (largeArr == search).all(1)
 

Идиома для поиска непрерывных пробегов маски была избита до смерти на этом сайте. Суть в np.diff том, чтобы найти, где меняется знак маски, затем np.flatnonzero получить индексы и np.diff снова вычислить длину пробега. Сначала наложите маску, чтобы убедиться, что результат правильно включает конечные точки:

 indices = np.flatnonzero(np.diff(np.r_[False, mask, False])).reshape(-1, 2)
runs = np.diff(indices, axis=1).squeeze()
 

Обратите indices внимание, что для удобства это было изменено на две колонки. Проходящее заполнение l гарантирует, что это возможно. Первый столбец-это начало каждого запуска (включительно), а второй-конец (эксклюзивно). Это делает вычисление длины пробега runs тривиальным.

Теперь вы можете настроить indices , чтобы включать только прогоны размером n или больше, и обрезать конечные элементы, чтобы они были кратны n начальным элементам:

 # runs = n * (runs // n), but for huge arrays
np.floor_divide(runs, n, out=runs)
np.multiply(runs, n, out=runs)

indices[:, 1] = indices[:, 0]   runs
 

Вы можете обрезать неиспользуемые участки нулевой длины indices indices = indices[np.flatnonzero(runs)] , но в этом нет необходимости. Следующим шагом является преобразование скорректированного indices изображения обратно в маску:

 mask = np.zeros_like(mask, dtype=np.int8)
 

Тип np.uint8 dtype позволяет хранить 1 и -1 в маске и имеет тот же размер, np.bool_ что и , что означает, что при правильном выполнении конечный результат можно легко просмотреть как логическую маску:

 starts, ends = indices.T
if ends[-1] == mask.size:
    ends = ends[:-1]
mask[starts] = 1
mask[ends] -= 1  # This takes care of zero-length segments automatically
mask = np.cumsum(mask, out=mask).view(bool)
 

Дополнительная обработка для ends , которая распаковывается как второй столбец indices , учитывает случай, когда маска выполняется до конца массива. Поскольку конечные индексы являются исключительными, это будет за пределами массива, но это также означает, что этот запуск вообще не нужно завершать.

Теперь, когда ваша маска была отфильтрована и обрезана, вы можете назначить правильные строки в largeArr . Самый простой способ-повторить pattern столько раз, сколько необходимо:

 largeArr[mask, :] = np.tile(pattern, [runs.sum() // n, 1])
 

Если вы упаковываете это в функцию, вы можете запускать ее для нескольких шаблонов:

 def replace_pattern(arr, search, pattern):
    n = len(pattern)
    mask = (arr == search).all(1)
    indices = np.flatnonzero(np.diff(np.r_[False, mask, False])).reshape(-1, 2)
    runs = np.diff(indices, axis=1).squeeze()
    np.floor_divide(runs, n, out=runs)
    np.multiply(runs, n, out=runs)
    indices[:, 1] = indices[:, 0]   runs
    mask = np.zeros_like(mask, dtype=np.int8)
    starts, ends = indices.T
    if ends[-1] == mask.size:
        ends = ends[:-1]
    mask[starts] = 1
    mask[ends] -= 1
    mask = np.cumsum(mask, out=mask).view(bool)
    arr[mask, :] = np.tile(pattern, [runs.sum() // n, 1])

replacements = [
    ([0, 1, 1], [[0, 2, 1],
                 [0, 2, 2],
                 [0, 2, 3]]),
    ([3, 2, 0], [[5, 2, 1],
                 [5, 3, 2],
                 [5, 4, 3],
                 [5, 5, 4]])
]

largeArr = np.array(...)

for search, pattern in replacements:
    replace_pattern(largeArr, search, pattern)