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

В 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.

Под редакцией ...

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

15.12.2008 13:29:21
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
0
15.12.2008 14:00:07

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

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

3
15.12.2008 15:11:21
Спасибо Марк, я не знал о постоянстве. Я предпочитаю иметь более локальный охват и просто не знаю, как этого достичь.
Jon Norton 17.12.2008 03:05:52

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

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

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

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

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

  • Использование встроенных функций , таких как sum, cumsum, diff, bsxfunи accumarrayработать непосредственно над матрицей изображения.
  • Сложные вычисления с двойной итерацией на изображениях иногда могут быть выражены в виде умножения матриц.
2
16.12.2008 17:01:30
Вы правы, это была ошибка, потому что реальный код находится на другой машине без подключения к Интернету, поэтому я переписывал из памяти. Я проверил частоту обращений к кешу, и казалось, что это должно помочь. Теперь, когда вы можете увидеть мои настоящие намерения, есть ли более MATLAB способ сделать это?
Jon Norton 17.12.2008 03:08:57

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

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

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

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

0
18.12.2008 04:09:05