Почему кэширование ответов занимает больше времени в MATLAB?

Question

У меня есть долго работающая функция в MATLAB, которую я пытался ускорить, добавив кеширование и в итоге значительно снизив производительность. Мой код в основном ищет непрерывные «горизонтальные» линии на изображении с обнаруженным краем, и оригинальный код выглядит примерно так:

function lineLength = getLineLength(img, startRow, startCol)
    [nRows, nCols] = size(img);
    lineLength = 0;
    if startRow < 1 || startRow > nRows
        return;
    end

    for curCol = startCol:nCols
        if img(curCol)
            lineLength = lineLength + 1;
            continue;
        elseif lineLength > 0
            lengths = zeros(2,1);
            lengths(1) = getLineLength(img, startRow - 1, curCol);
            lengths(2) = getLineLength(img, startRow + 1, curCol);
            increment = max(lengths);
            lineLength = lineLength + increment;
        end
        break; %// At this point the end of the current line has been reached
    end
end function

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

function lineLength = getLineLength(img, startRow, startCol)
persistent pointCache; 
    if startRow == 0 && startCol == 0
        pointCache = zeros(size(img, 1), size(img, 2), 2);
    end
    [nRows, nCols] = size(img);
    lineLength = 0;
    if startRow < 1 || startRow > nRows
        return;
    end

    for curCol = startCol:nCols
        if pointCache(startRow, curCol, 2)
            lineLength = lineLength + pointCache(startRow, curCol, 1);
            break;
        end
        if img(curCol)
            lineLength = lineLength + 1;
            continue;
        elseif lineLength > 0
            lengths = zeros(2,1);
            lengths(1) = getLineLength(img, startRow - 1, curCol);
            lengths(2) = getLineLength(img, startRow + 1, curCol);
            increment = max(lengths);
            lineLength = lineLength + increment;
        end
        break; %// At this point the end of the current line has been reached
    end
    pointCache(startRow, startCol, 1) = lineLength;
    pointCache(startRow, startCol, 2) = 1;
end function

Что меня удивило, так это то, что реализация этого кэширования фактически ухудшила мою производительность, а не улучшила ее. Мое лучшее предположение состоит в том, что либо переменная global доставляет мне неприятности, либо требует дополнительного использования памяти, но у меня недостаточно опыта MATLAB, чтобы это знать.

Edited ...

Как правильно заметил Гаутам, в исходном коде была ошибка, которая игнорировала результаты рекурсии. Это то, что делает настоящий код. Я уверен, что это очевидно, но MATLAB - не мой родной язык, поэтому, если есть более MATLABы способ сделать это, я бы с удовольствием порекомендовал.

Answer 1

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

Каждый раз, когда у вас есть проблемы с производительностью, профиль. Вызовите profile on, затем свою функцию, затем profile report. Это укажет на ваши реальные проблемы с производительностью. Редко интуиция хороша для профилирования проблем, особенно в matlab. Вы можете прочитать справку, но она говорит сама за себя.

Answer 2

Мне не понятно, что делает эта функция. В частности, почему вы рекурсивно вызываете getLineLength, а затем эффективно отбрасываете результаты (вы проверяете только, если приращение больше нуля)?

Я думаю, почему pointCache не помогает: ваша функция, вероятно, не вызывает себя повторно с теми же параметрами (startRow, startCol). Вы пытались регистрировать, сколько раз вызывается getLineLength для определенного startRow и startCol?

Каким бы ни был ваш алгоритм, использование рекурсии для итерации по изображению совершенно не соответствует сильным сторонам MATLAB. Если вы хотите высокую производительность:

1. Настройте свой алгоритм на использование итерации вместо рекурсии и
2. Выясните, как векторизовать повторяющиеся части.

Несколько советов по векторизации:

• Используйте встроенные функции, такие как sum, cumsum, diff, bsxfun и accumarray, чтобы работать непосредственно с матрицей изображения.
• Сложные вычисления с двойной итерацией для изображений иногда могут быть выражены в виде умножения матриц.

Answer 3

Насколько я могу судить, вы пытаетесь найти количество ненулевых элементов для каждого столбца, хотя код, похоже, не вполне этого достигает. Хотелось бы что-то вроде следующей работы:

lineLengths = max(cumsum(img~=0, 1), 1)

Если вы пытаетесь извлечь капли из вашего изображения, рассмотрите возможность использования функции BWLABEL.

Я второе, что говорит Гаутам о том, что обычно хорошо работает в Matlab.

Answer 4

Я предполагаю, что вы кешируете не ту часть своего кода. Рекурсия в другой части, кажется, является настоящим узким местом. Весь алгоритм выглядит немного странно для меня, возможно, вам лучше попробовать что-то вроде этого (хотя я точно не знаю, хотите ли вы этого):

for every pixel p in img
  if (pixel p set)
    linelength = 1
    p2 = p
    while (pixel p2 set) and (p2 in same column as p)
      p++ // don't check lines twice
      p2++
      linelength++
    endwhile
  endif