Как я могу улучшить эффективность этой петли

Question

У меня есть пустой массив, содержащий метки.Я хотел бы рассчитать число для каждой метки на основе ее размера и ограничительной рамки.Как я могу написать это более эффективно, чтобы ее можно было использовать на больших массивах (~ 15000 меток)?

A = array([[ 1, 1, 0, 3, 3],
           [ 1, 1, 0, 0, 0],
           [ 1, 0, 0, 2, 2],
           [ 1, 0, 2, 2, 2]] )

B = zeros( 4 )

for label in range(1, 4):
    # get the bounding box of the label
    label_points = argwhere( A == label )
    (y0, x0), (y1, x1) = label_points.min(0), label_points.max(0) + 1

    # assume I've computed the size of each label in a numpy array size_A
    B[ label ] = myfunc(y0, x0, y1, x1, size_A[label])

Answer 1

Я не смог реализовать это эффективно, используя некоторые векторизованные функции NumPy, поэтому, возможно, умная реализация Python будет быстрее.

def first_row(a, labels):
    d = {}
    d_setdefault = d.setdefault
    len_ = len
    num_labels = len_(labels)
    for i, row in enumerate(a):
        for label in row:
            d_setdefault(label, i)
        if len_(d) == num_labels:
            break
    return d

Эта функция возвращает словарь, сопоставляющий каждую метку с индексом первой строки, в которой она появляется. Применение функции к A, A.T, A[::-1] и A.T[::-1] также дает вам первый столбец, а также последняя строка и столбец.

Если вы предпочитаете использовать список вместо словаря, вы можете превратить словарь в список, используя map(d.get, labels). Кроме того, вы можете использовать массив NumPy вместо словаря с самого начала, но вы потеряете возможность выходить из цикла сразу, как только будут найдены все метки.

Мне было бы интересно, действительно ли (и насколько) это ускоряет ваш код, но я уверен, что это быстрее, чем ваше оригинальное решение.

Answer 2

Другой метод:

используйте bincount (), чтобы получить количество меток в каждой строке и столбце, и сохраните информацию в массиве строк и столбцов.

Для каждой метки вам нужен только поискдиапазон в строках и столбцах.Это быстрее, чем сортировка, на моем компьютере, он может сделать расчет за несколько секунд.

def label_range2(A):
    maxlabel = np.max(A)+1
    h, w = A.shape
    rows = np.zeros((h, maxlabel), np.bool)
    for row in xrange(h):
        rows[row,:] = np.bincount(A[row,:], minlength=maxlabel) > 0

    cols = np.zeros((w, maxlabel), np.bool)
    for col in xrange(w):
        cols[col,:] =np.bincount(A[:,col], minlength=maxlabel) > 0

    for label in xrange(1, maxlabel):
        row = rows[:, label]
        col = cols[:, label]
        y = np.where(row)[0]
        x = np.where(col)[0]
        x0 = np.min(x)
        x1 = np.max(x)+1
        y0 = np.min(y)
        y1 = np.max(y)+1        
        yield label, x0,y0,x1,y1

Answer 3

Алгоритм:

1. изменить массив на одно измерение
2. получить индекс сортировки с помощью argsort ()
3. получить отсортированную версию массива измерений как sorted_A
4. используйте where () и diff (), чтобы найти позицию изменения метки в sorted_A
5. , используйте позицию изменения и индекс сортировки, чтобы получить исходную позицию метки в одном измерении.
6. вычисляет двухмерное местоположение из позиции измерения.

для большого массива, такого как (7000, 9000), это может закончить вычисление за 30 секунд.

здеськод:

import numpy as np

A = np.array([[ 1, 1, 0, 3, 3],
           [ 1, 1, 0, 0, 0],
           [ 1, 0, 0, 2, 2],
           [ 1, 0, 2, 2, 2]] )

def label_range(A):
    from itertools import izip_longest
    h, w = A.shape
    tmp = A.reshape(-1)

    index = np.argsort(tmp)
    sorted_A = tmp[index]
    pos = np.where(np.diff(sorted_A))[0]+1
    for p1,p2 in izip_longest(pos,pos[1:]):
        label_index = index[p1:p2]
        y = label_index // w
        x = label_index % w

        x0 = np.min(x)
        x1 = np.max(x)+1
        y0 = np.min(y)
        y1 = np.max(y)+1
        label = tmp[label_index[0]]

        yield label,x0,y0,x1,y1

for label,x0,y0,x1,y1 in label_range(A):
    print "%d:(%d,%d)-(%d,%d)" % (label, x0,y0,x1,y1)

#B = np.random.randint(0, 100, (7000, 9000))
#list(label_range(B))

Answer 4

Используя PyPy, вы можете просто запустить цикл и не беспокоиться о векторизации. Это должно быть быстро.

Answer 5

Кажется, что узкое место в производительности - это призыв к argmax. Этого можно избежать, изменив цикл следующим образом (вычисляя только y0, y1, но легко обобщая до x0, x1):

for label in range(1, 4):
    comp = (A == label)
    yminind = comp.argmax(0)
    ymin = comp.max(0)
    ymaxind = comp.shape[0] - comp[::-1].argmax(0)
    y0 = yminind[ymin].min()
    y1 = ymaxind[ymin].max()

Я не уверен в причине разницы в производительности, но одной из причин может быть то, что все операции, такие как ==, argmax и max, могут предварительно выделить свой выходной массив непосредственно из формы входного массива , что невозможно для argwhere.