Оптимизация алгоритма определения формы

Question

У меня есть матрица 0s и 1s, и мне нужно извлечь «фигуры» из этой матрицы. Формы состоят из 1s, соединенных в 8 направлениях. В конечном результате я получаю 2d массив фигур. Каждый массив форм содержит индексы клеток в исходной матрице. Я написал скрипт, и он работает, за исключением того, что он падает с большими матрицами. И я получаю ошибку в консоли Uncaught RangeError: Maximum call stack size exceeded Мне нужно, чтобы она работала с большими матрицами, такими как 1000 x 1000 и более.

Вот мой код:

var matrixCols = 150; 
 
var matrixRows = 150; 
 
var matrix = []; 
 
var shapes = []; 
 
var checkedCels = []; 
 

 

 
function createMatrix() { 
 
\t for(var i = 0; i < matrixRows; i++) { 
 
    \t var row = []; 
 
\t \t for(var j = 0; j < matrixRows; j++) { 
 
    \t var value = Math.round(Math.random()); 
 
     row.push(value); 
 
    \t matrix.push(value); 
 
    } 
 
    console.log(JSON.stringify(row)); 
 
    } \t 
 
} 
 

 
function getShapes() { 
 
\t for(var i = 0; i < matrix.length; i++) { 
 
    \t if(checkedCels.indexOf(i) === -1 && matrix[i] === 1) { 
 
    \t shapes.push(formShape(i)); 
 
    } 
 
    } 
 
    
 
    console.log('Total shapes:', shapes.length); 
 
    console.log(shapes); 
 
} 
 

 
function formShape(startIndex) { 
 
\t return getNeighbours(startIndex); 
 
} 
 

 
function getNeighbours(index) { 
 
\t if(checkedCels.indexOf(index) > -1) { 
 
    \t return []; 
 
    } 
 
    var cels = [index]; 
 
    checkedCels.push(index); 
 
    
 
    var nwIndex = index - matrixCols - 1; 
 
    var nwCel = matrix[nwIndex]; 
 
    if(typeof nwCel !== 'undefined' && nwCel === 1 && index % matrixCols > 0) { 
 
    \t cels = cels.concat(getNeighbours(nwIndex)); 
 
    } 
 
    
 
    var nIndex = index - matrixCols; 
 
    var nCel = matrix[nIndex]; 
 
    if(typeof nCel !== 'undefined' && nCel === 1) { 
 
    \t cels = cels.concat(getNeighbours(nIndex)); 
 
    } 
 
    
 
    var neIndex = index - matrixCols + 1; 
 
    var neCel = matrix[neIndex]; 
 
    if(typeof neCel !== 'undefined' && neCel === 1 && index % matrixCols < (matrixCols - 1)) { 
 
    \t cels = cels.concat(getNeighbours(neIndex)); 
 
    } 
 
    
 
    var wIndex = index - 1; 
 
    var wCel = matrix[wIndex]; 
 
    if(typeof wCel !== 'undefined' && wCel === 1 && index % matrixCols > 0) { 
 
    \t cels = cels.concat(getNeighbours(wIndex)); 
 
    } 
 
    
 
    var eIndex = index + 1; 
 
    var eCel = matrix[eIndex]; 
 
    if(typeof eCel !== 'undefined' && eCel === 1 && index % matrixCols < (matrixCols - 1)) { 
 
    \t cels = cels.concat(getNeighbours(eIndex)); 
 
    } 
 
    
 
    var swIndex = index + matrixCols - 1; 
 
    var swCel = matrix[swIndex]; 
 
    if(typeof swCel !== 'undefined' && swCel === 1 && index % matrixCols > 0) { 
 
    \t cels = cels.concat(getNeighbours(swIndex)); 
 
    } 
 
    
 
    var sIndex = index + matrixCols; 
 
    var sCel = matrix[sIndex]; 
 
    if(typeof sCel !== 'undefined' && sCel === 1) { 
 
    \t cels = cels.concat(getNeighbours(sIndex)); 
 
    } 
 
    
 
    var seIndex = index + matrixCols + 1; 
 
    var seCel = matrix[seIndex]; 
 
    if(typeof seCel !== 'undefined' && seCel === 1 && index % matrixCols < (matrixCols - 1)) { 
 
    \t cels = cels.concat(getNeighbours(seIndex)); 
 
    } 
 
    
 
    return cels; 
 
} 
 

 
createMatrix(); 
 
getShapes();

Как я могу оптимизировать его?

Answer 1

Вы можете избежать рекурсии в функции getNeighbours, сохраняя список ячеек для проверки (которая изначально содержит только startIndex) и на каждой итерации:

• взять элемент из списка
• проверить, если это нормально (не проверено, а значение матрицы при этом индексе 1)
• добавить свои сосед в список, чтобы проверить
• повторить

Этот цикл останавливается, когда больше нет ячеек для проверки.

Не используя рекурсию, программа не выйдет из пространства стека, и алгоритм сможет обрабатывать большие матрицы (если текущий список для проверки не превышает доступную память).

В дополнение к этому существует еще одна возможная оптимизация: checkedCells в настоящее время является массивом и для проверки того, была ли ячейка уже проанализирована, вы используете .indexOf() (что является операцией O (n)). Изменяя checkedCells как объект, который хранит в качестве ключей, индексы анализируемых ячеек уменьшают этот поиск до O (1).

Вот ваш код изменен в соответствии с двумя точками выше:

console.clear(); 
 

 
var matrixCols = 7; 
 
var matrixRows = 7; 
 
var matrix = []; 
 
var shapes = []; 
 
var checkedCels = {}; 
 

 

 
function createMatrix() { 
 
    for (var i = 0; i < matrixRows; i++) { 
 
    var row = []; 
 
    for (var j = 0; j < matrixRows; j++) { 
 
     var value = Math.round(Math.random()); 
 
     // value = Math.random() > 0.75 ? 1 : 0; // to change the probability of a cell being "set" 
 
     row.push(value); 
 
     matrix.push(value); 
 
    } 
 
    console.log(row.map(function(x) { 
 
     return " X" [x] 
 
    }).join('')); 
 
    } 
 
} 
 

 
function getShapes() { 
 
    for (var i = 0; i < matrix.length; i++) { 
 
    if (!checkedCels[i] && matrix[i] === 1) { 
 
     shapes.push(formShape(i)); 
 
    } 
 
    } 
 

 
    console.log('Total shapes:', shapes.length); 
 
    console.log(shapes); 
 
} 
 

 
function formShape(startIndex) { 
 
    var cels = []; 
 
    var toCheck = [startIndex]; 
 

 
    while (toCheck.length) { 
 
    var index = toCheck.pop(); 
 

 
    if (checkedCels[index]) { 
 
     continue; 
 
    } 
 

 
    if (matrix[index] !== 1) { 
 
     continue; 
 
    } 
 

 
    cels.push(index); 
 
    checkedCels[index] = 1; 
 

 
    var neighbours = []; 
 

 
    if (index % matrixCols > 0) { 
 
     neighbours.push(index - matrixCols - 1); // NW 
 
     neighbours.push(index - 1); // W 
 
     neighbours.push(index + matrixCols - 1); // SW 
 
    } 
 
    if (index % matrixCols < (matrixCols - 1)) { 
 
     neighbours.push(index - matrixCols + 1); // NE 
 
     neighbours.push(index + 1); // E 
 
     neighbours.push(index + matrixCols + 1); // SE 
 
    } 
 
    neighbours.push(index - matrixCols); // N 
 
    neighbours.push(index + matrixCols); // S 
 

 
    neighbours.forEach(function(n) { 
 
     if (typeof matrix[n] !== 'undefined') { 
 
     toCheck.push(n); 
 
     } 
 
    }); 
 
    } 
 

 
    return cels; 
 
} 
 

 

 
createMatrix(); 
 
getShapes();

Я ограничивали размер матрицы для 7x7 для удобства чтения, но приведенный выше код должен решить 1000x1000 матрицы в нескольких секунд.