Эффективный способ добавить несколько раз 2D вектор в другой 2D вектор

Question

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

Это мое Фактический код:

import numpy as np


# dummy function just for testing
def get_max_subtree_length(groups):
    return 20

def pad_groups(dataset, groups):
    dataset = np.array(dataset)
    max_subtree_length = get_max_subtree_length(groups)
    padded_dataset = np.array([[]])
    start_range = 0
    dataset_row_length = len(dataset[0]) - 1
    zeros_pad = np.zeros(dataset_row_length)
    for group in groups:
        pad = np.array([group[0]])
        pad = np.append(pad, zeros_pad)
        end_range = start_range + group[1]
        subtree = dataset[start_range:end_range, :]
        if len(padded_dataset[0]) == 0:
            padded_dataset = subtree
        else:
            padded_dataset = np.vstack([padded_dataset, subtree])
        subtree_length = group[1]
        subtree_to_pad = max_subtree_length - subtree_length
        # Append subtree_to_pad (number of pad to append) times the same pad array to the dataset
        pads = np.repeat([pad], subtree_to_pad, axis=0)
        padded_dataset = np.vstack([padded_dataset, pads])
        start_range = end_range
    return padded_dataset

Для проверки:

dataset = np.array([
    [1, 2, 3], [1, 2, 3], [1, 2, 3], [2, 2, 3], [2, 2, 3],
    [2, 2, 3], [3, 2, 3], [3, 2, 3], [3, 2, 3], [4, 2, 3],
    [4, 2, 3], [4, 2, 3], [5, 2, 3], [5, 2, 3], [5, 2, 3],
    [6, 2, 3], [6, 2, 3], [6, 2, 3], [7, 2, 3], [7, 2, 3],
    [7, 2, 3], [8, 2, 3], [8, 2, 3], [8, 2, 3]])

groups = [(1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3), (7, 3), (8, 3)]

dataset = pad_groups(dataset, groups)
print(len(dataset))
# 160
print(dataset)
# [[1. 2. 3.]
#  [1. 2. 3.]
#  [1. 2. 3.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [1. 0. 0.]
#  [2. 2. 3.]
#  [2. 2. 3.]
#  [2. 2. 3.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [2. 0. 0.]
#  [3. 2. 3.]
#  [3. 2. 3.]
#  [3. 2. 3.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [3. 0. 0.]
#  [4. 2. 3.]
#  [4. 2. 3.]
#  [4. 2. 3.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [4. 0. 0.]
#  [5. 2. 3.]
#  [5. 2. 3.]
#  [5. 2. 3.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [5. 0. 0.]
#  [6. 2. 3.]
#  [6. 2. 3.]
#  [6. 2. 3.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [6. 0. 0.]
#  [7. 2. 3.]
#  [7. 2. 3.]
#  [7. 2. 3.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [7. 0. 0.]
#  [8. 2. 3.]
#  [8. 2. 3.]
#  [8. 2. 3.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]
#  [8. 0. 0.]]

В этом случае matrix равно padded_dataset и matrix2 равно pads.

groups имеет длину 122 000.

ОБНОВЛЕНИЕ :

IDE для имитации функции: https://repl.it/repls/IdealKeyModes

Как я могу сделать эту операцию более эффективным способом?

Answer 1

Можно подумать о замене np.vstack(), np.append() и подобных на соответствующие операции list и преобразовать окончательный результат в np.array() в конце. Конечный результат может выглядеть примерно так:

def pad_groups_opt(dataset, groups):
    dataset = np.array(dataset)
    max_subtree_length = get_max_subtree_length(groups)
    start = 0
    rows, cols = dataset.shape
    padded_dataset = []
    for group in groups:
        pad = [group[0]] + [0] * (cols - 1)
        stop = start + group[1]
        subtree = dataset[start:stop].tolist()
        padded_dataset.extend(subtree)
        subtree_to_pad = max_subtree_length - group[1]
        pads = [pad] * subtree_to_pad
        padded_dataset.extend(pads)
        start = stop
    return np.array(padded_dataset)

и тестирование его на соответствие вашему исходному коду:

dataset = np.array([
    [1, 2, 3], [1, 2, 3], [1, 2, 3], [2, 2, 3], [2, 2, 3],
    [2, 2, 3], [3, 2, 3], [3, 2, 3], [3, 2, 3], [4, 2, 3],
    [4, 2, 3], [4, 2, 3], [5, 2, 3], [5, 2, 3], [5, 2, 3],
    [6, 2, 3], [6, 2, 3], [6, 2, 3], [7, 2, 3], [7, 2, 3],
    [7, 2, 3], [8, 2, 3], [8, 2, 3], [8, 2, 3]])
groups = [(1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3), (7, 3), (8, 3)]

print(np.all(pad_groups(dataset, groups) == pad_groups_opt(dataset, groups)))
# True

По времени вы получаете ~ 2-кратное ускорение при вводе:

%timeit pad_groups(dataset, groups)
# 10000 loops, best of 3: 169 µs per loop
%timeit pad_groups_opt(dataset, groups)
# 10000 loops, best of 3: 89.3 µs per loop

и, кажется, становится еще лучше (~ 10x) для больших входов:

%timeit pad_groups(dataset.tolist() * 100, groups * 100)
# 10 loops, best of 3: 107 ms per loop
%timeit pad_groups_opt(dataset.tolist() * 100, groups * 100)
# 100 loops, best of 3: 9.21 ms per loop