Алгоритм быстрой диффузии интенсивности

Convolution – это распространенный прием обработки изображений (теперь у вас есть ключевое слово для поиска!).

[[ 0.5, 0.5, 0.5 ],
 [ 0.5, 1.0, 0.5 ],
 [ 0.5, 0.5, 0.5 ]]

Похоже, вы реализовали свертки с этим ядром вручную.

Чтобы ускорить процесс: поскольку свертка является ассоциативной, вы можете предварительно вычислить один фильтр вместо многократного применения оригинала. Например, если количество проходов = 2,

once = [[ 0.5, 0.5, 0.5 ], [ 0.5, 1.0, 0.5 ], [ 0.5, 0.5, 0.5 ]]
twice = once ⊗ once =
    [[ 0.25, 0.50, 0.75, 0.50, 0.25 ],
     [ 0.50, 1.50, 2.00, 1.50, 0.50 ],
     [ 0.75, 2.00, 3.00, 2.00, 0.75 ], 
     [ 0.50, 1.50, 2.00, 1.50, 0.50 ], 
     [ 0.25, 0.50, 0.75, 0.50, 0.25 ]]

distribute(hm) = hm ⊗ once ⊗ once
               = hm ⊗ twice

Если вы будете делать это неоднократно, возможно, стоит изучить ФурьеПреобразование; есть теорема о том, что

FT(X ⊗ Y) = FT(X) ⋅ FT(Y)

или после применения обратного преобразования Фурье,

X ⊗ Y = IFT(FT(X) ⋅ FT(Y))

Другими словами, сложные свертки можно заменить простыми умножениями.

Что ж, думаю, в вашем цикле for для функции distributeIntensity вы могли бы внести небольшие изменения:

• Сохраните массив length.
• Инвертируйте оператор if, чтобы избежать оператора continue.

this.distributeIntensity = function(shareRatio) {       
    var tmp = hm.intensity.slice(0); // copy array
    for (var i = 0, n = tmp.length; i < n; i++) {                      
        if (hm.intensity[i] > 0) {
          var current = hm.intensity[i];
          var shareAmount = current * shareRatio;
          this.shareIntensityWithNeighbours(tmp, shareAmount, i);
        }
    }
    hm.intensity = tmp;
};

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

this.distributeIntensity = function(shareRatio) {       
    var tmp = hm.intensity.slice(0); // copy array
    var i = tmp.length;
    while (i--) {
        if (hm.intensity[i] > 0) {
          var current = hm.intensity[i];
          var shareAmount = current * shareRatio;
          this.shareIntensityWithNeighbours(tmp, shareAmount, i);
        }
    }
    hm.intensity = tmp;
};

Вы также можете рассмотреть возможность интеграции функции shareIntensityWithNeighbours в цикл, вызов функции может быть несколько дорогим.

Однако я настоятельно рекомендую вам использовать профилировщик (встроенный в Firebug действительно хорош), чтобы действительно измерить производительность и быстро найти узкие места.

Следует отметить, что в относительно редком случае (таком как первая установка, где имеется только одна запись с интенсивностью > 0) вам нужно заниматься только некоторыми записями.

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

Редактировать

Я пошел нарыть пример такого подхода. Моделирование игры Конвея «Жизнь / Клеточные автоматы» представляет аналогичные трудности в оптимизации. На каждом этапе состояние каждой ячейки должно быть рассчитано на основе окружающих ячеек.

Чрезвычайно мощной реализацией является Hashlife. По сути, он использует умный хэш для отслеживания того, какие ячейки действительно необходимо обновить, и для запоминания (кэширования шаблонов) вычислений. Вы можете найти вдохновение в его стратегии.

Благодаря ответу ephemient выше я смог получить информацию, необходимую для исправления этого алгоритма. В итоге я получил алгоритм, который на 50-55% быстрее. Также спасибо CMS за лайфхаки с производительностью javascript (на самом деле они имеют большое значение).

Для полноты я включаю код:

Примечание. Код оптимизирован, поэтому он не самый аккуратный (развернутые продолжения, обратные итерации массивов и т. д.), много локального кэширования переменных и т. д.

    this.distributeHeatMapIntensities = function(passes, shareRatio) {              
        var tmp = hm.intensity.slice(0);

        var distances = {};
        for (var i = -passes; i <= passes; i++) { distances[i] = Math.abs(i); }
        var shares = [];
        for (var i = 0; i <= passes; i++) { shares.push(i === 0 ? 0 : Math.pow(shareRatio, i)); }
        var len = tmp.length - 1;

        for(var i = len; i >= 0; i--) {     
            var intens = hm.intensity[i];
            if (intens > 0) {                       
                var x = Math.floor(i % hm.columnCount);
                var y = Math.floor(i / hm.columnCount);                     

                for (var tx = -passes; tx <= passes; tx++) { 
                    var nx = x + tx;
                    if (nx >= 0 && nx < hm.columnCount) {               
                        var dx = distances[tx];
                        for (var ty = -passes; ty <= passes; ty++) { 
                            var ny = y + ty;
                            if (ny >= 0 && ny < hm.rowCount) {                      
                                var dy = distances[ty];
                                var distance = dx >= dy ? dx : dy;
                                var share = shares[distance] * intens;
                                var i2 = (ny * hm.columnCount) + nx;
                                tmp[i2] += share;
                            }
                        }
                    }
                }
            }
        }   
        hm.intensity = tmp; 
    }

Спасибо всем

Гвидо