javascript：快速查找数组中的连接组件（寻找加速/替代方式） [英] javascript: Fast way to find connected components in array (looking for speed up / alternative way)
本文介绍了javascript：快速查找数组中的连接组件（寻找加速/替代方式）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个矩阵（ 1d数组，x& y-ax ），如下所示：
VAR矩阵= [
'00000000000000000000000000000000000000000000000000000000000000000000111111111'，
'11111100000000000000000000001000000000000000000000000000000000000000000001111'，
'00000000000000000000000000000000001000000000000000000000000000000000000000011'，
'11111000000000000000000000000000000000000001111110000000000000000000000000001'，
'11111000000000000111000000000000000000111111000000000000000000000000000000000'，
' 000000000001111111111111000000000000000000000000000000000'，
'000000000000000001100000000000000000000000000000000''，
'000000000000000000000000000000000000000'，
'0000010000000000000000000000000000000000'，
'000000100100000000000000000000000000001111111100000000000000000000000000 0000000'，
'00000000000000000000000000000000000000000'，
'00000000000000000000000000000000000000000000000000000000000000100000000000000'，
'000000000000000000000000000000000000000000000000000100000000000000000000000'
]
我想找到所有连接的'1'字符组并提取所有位置以得到这样的结果：
[{0：[[68,0]，[69,0]，[70,0]，[71,0]，[72,0] [73.0]，[73,1]，[74,1]，[75.1]，[75.2]，[76,2]，[76.3]，[76,1]，[ 76,0]，[75,0]，[74,0]]，1：[[0,1]，[1,1]，[2,1]，[3,1]，[4， 1]，[5,1]]，2：[[28,1]]，3：[[34,2]]，4：[[0,3]，[0,4] ，[1,4]，[2,4]，[3,4]，[4,4]，[4,3]，[3,3]，[2,3]，[1,3]] 5：[[43,4]，[43,4]，[43,4]，[43,4]，[42,6]，[42,5]，[42,4]，[41， 4]，[41,5]，[41.6]，[40,6]，[40,5]，[40,4]，[39,4]，[39,5]，[39,6] ，[38,6]，[38,5]，[38,4]，[44.3]，[45,3]，[46,3]，[47,3]，[48.3]] 6：[[17,4]，[17,5]，[17,6]，[18,6]，[18,5]，[19,5]，[20,5]，[21， 5]，[22,5]，[23,5]，[1 9,4]，[18,4]，[16,5]，[15,5]，[14,5]，[13,5]，[12,5]，[11,5]，7 ：[[63,6]]，8：[[31,7]，[32,7]，[33,7]，[34,7]，[35,7]，[36,7] ，[37,7]]，9：[[5,8]]，10：[[66,8]]，11：[[6,9]]，12：[[ [9,9]]，13：[[38,9]，[39,9]，[40,9]，[41,9]，[42,9]，[44]，[44， 9]，[45,9]]，14：[[62,11]]，15：[[53,12]]}]
我已经开发了某种 洪水填充算法 上面的矩阵。
但必须有一种更高效的方式快速查找更大矩阵中的连通组件（例如，大10甚至100倍）。
- >我的想法也许这个结果也可以通过某种正则表达式结合javascript代码来实现，但我绝对不知道如何编写这个，所以我希望有人有一个好主意加快我的小算法以便我可以避免溢出错误：
<预类= 片段码-JS郎-JS prettyprint-越权>
变种矩阵= [ '00000000000000000000000000000000000000000000000000000000000000000000111111111'， '11111100000000000000000000001000000000000000000000000000000000000000000001111'， '00000000000000000000000000000000001000000000000000000000000000000000000000011'， '11111000000000000000000000000000000000000001111110000000000000000000000000001'， '11111000000000000111000000000000000000111111000000000000000000000000000000000' ，'00000 000000111111111111100000000000000111111000000000000000000000000000000000' ， '00000000000000000110000000000000000000111111000000000000000000010000000000000'， '00000000000000000000000000000001111111000000000000000000000000000000000000000'， '00000100000000000000000000000000000000000000000000000000000000000010000000000'， '00000010010000000000000000000000000000111111110000000000000000000000000000000'， '00000000000000000000000000000000000000000000000000000000000000000000000000000'， '00000000000000000000000000000000000000000000000000000000000000100000000000000'， '00000000000000000000000000000000000000000000000000000100000000000000000000000'] Array.prototype.extract_components_positions =函数（偏移）{风险阵列= this.map（项目=> item.split（''））。map（str => Array.from（str，Number）），default_value = 0，result_object = {} function test_connection（array，i，j）{if（array [i]& ;& array [i] [j] === -1）{if（！result_object [default_value]）result_object [default_value] = []; result_object [default_value] .push（[j，i]）; array [i] [j] = 1; for（var k = offset; k> 0; k--）{test_connection（array，i + k，j）; // left - right test_connection（array，i，j + k）; // top - bottom test_connection（array，i - k，j）; // right - left test_connection（array，i，j - k）; // bottom - top} return true}} array.forEach（function（a）{a.forEach（function（b，i，bb）{bb [i] = -b}）}）; array.forEach（function（a，i，aa）{a.forEach（function（b，j，bb）{test_connection（aa，i，j）&& default_value ++}）}）return [result_object];} var result = matrix.extract_components_positions（1）; console.log（（result））
.as-console-wrapper {max-height：100％！important;顶部：0; }
编辑1.0 BTW它会如果算法只能连接更大的组件（例如，最少5个连接字符组）
解决方案
代码
这是我想出的方法。我确信它可以进行优化，但我觉得这至少是朝着正确方向迈出的一大步。
我也从以下答案中获取信息并应用它。
var matrix = [ '00000000000000000000000000000000000000000000000000000000000000000000111111111'， '11111100000000000000000000001000000000000000000000000000000000000000000001111'， '00000000000000000000000000000000001000000000000000000000000000000000000000011'，'1111100000000000000000000000000000000000000111111000000000000 0000000000000001' ， '11111000000000000111000000000000000000111111000000000000000000000000000000000'， '00000000000111111111111100000000000000111111000000000000000000000000000000000'， '00000000000000000110000000000000000000111111000000000000000000010000000000000'， '00000000000000000000000000000001111111000000000000000000000000000000000000000'， '00000100000000000000000000000000000000000000000000000000000000000010000000000'， '00000010010000000000000000000000000000111111110000000000000000000000000000000'， '00000000000000000000000000000000000000000000000000000000000000000000000000000'， '00000000000000000000000000000000000000000000000000000000000000100000000000000'， '00000000000000000000000000000000000000000000000000000100000000000000000000000']变种结果= [];功能charPos（STR， char）{return str .split（）。map（function（c，i）{if（c == char）return i; } .filter（function（v）{return v> = 0;}）;} matrix.forEach（function（s，i）{var p = charPos（s，'1'）; results [i] = [ ]; matrix.forEach（function（s2，i2）{var p2; if（（p2 = charPos（s2，'1'）。filter（（n）=> p.includes（n）））。length）{ p2.forEach（function（v）{if（JSON.stringify（results）.indexOf（JSON.stringify（[v，i2]））=== -1）results [i] .push（[v，i2]） ;}）;}}）;}）; console.log（results.filter（v => v.length> 0））;
I have an matrix (1d array, x&y-axe) like this:
var matrix=[
'00000000000000000000000000000000000000000000000000000000000000000000111111111',
'11111100000000000000000000001000000000000000000000000000000000000000000001111',
'00000000000000000000000000000000001000000000000000000000000000000000000000011',
'11111000000000000000000000000000000000000001111110000000000000000000000000001',
'11111000000000000111000000000000000000111111000000000000000000000000000000000',
'00000000000111111111111100000000000000111111000000000000000000000000000000000',
'00000000000000000110000000000000000000111111000000000000000000010000000000000',
'00000000000000000000000000000001111111000000000000000000000000000000000000000',
'00000100000000000000000000000000000000000000000000000000000000000010000000000',
'00000010010000000000000000000000000000111111110000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000100000000000000',
'00000000000000000000000000000000000000000000000000000100000000000000000000000'
]
and I'D like to find all connected groups of '1'-characters and extract all of their positions to get something like this as result:
[{"0": [[68,0],[69,0],[70,0],[71,0],[72,0],[73,0],[73,1],[74,1],[75,1],[75,2],[76,2],[76,3],[76,1],[76,0],[75,0],[74,0]],"1": [[0,1],[1,1],[2,1],[3,1],[4,1],[5,1]],"2": [[28,1]],"3": [[34,2]],"4": [[0,3],[0,4],[1,4],[2,4],[3,4],[4,4],[4,3],[3,3],[2,3],[1,3]],"5": [[43,3],[43,4],[43,5],[43,6],[42,6],[42,5],[42,4],[41,4],[41,5],[41,6],[40,6],[40,5],[40,4],[39,4],[39,5],[39,6],[38,6],[38,5],[38,4],[44,3],[45,3],[46,3],[47,3],[48,3]],"6": [[17,4],[17,5],[17,6],[18,6],[18,5],[19,5],[20,5],[21,5],[22,5],[23,5],[19,4],[18,4],[16,5],[15,5],[14,5],[13,5],[12,5],[11,5]],"7": [[63,6]],"8": [[31,7],[32,7],[33,7],[34,7],[35,7],[36,7],[37,7]],"9": [[5,8]],"10": [[66,8]],"11": [[6,9]],"12": [[9,9]],"13": [[38,9],[39,9],[40,9],[41,9],[42,9],[43,9],[44,9],[45,9]],"14": [[62,11]],"15": [[53,12]]}]
I have already developed some kind of a flood fill algorithm that is working quiet well with the matrix above.
But there must be a way more efficient & fast way to find connected components in a bigger matrix (e.g 10 or even 100 times bigger). --> My idea was maybe this result could be also achieved with some kind of regex expression combined with javascript code, but I'm absolutely not sure how to code this, so I hope somebody has an good idea to fast up my little algorithm below so that I can avoid Overflow Errors :
var matrix=[
'00000000000000000000000000000000000000000000000000000000000000000000111111111',
'11111100000000000000000000001000000000000000000000000000000000000000000001111',
'00000000000000000000000000000000001000000000000000000000000000000000000000011',
'11111000000000000000000000000000000000000001111110000000000000000000000000001',
'11111000000000000111000000000000000000111111000000000000000000000000000000000',
'00000000000111111111111100000000000000111111000000000000000000000000000000000',
'00000000000000000110000000000000000000111111000000000000000000010000000000000',
'00000000000000000000000000000001111111000000000000000000000000000000000000000',
'00000100000000000000000000000000000000000000000000000000000000000010000000000',
'00000010010000000000000000000000000000111111110000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000100000000000000',
'00000000000000000000000000000000000000000000000000000100000000000000000000000'
]
Array.prototype.extract_components_positions = function(offset) {
var array = this.map(item => item.split('')).map(str => Array.from(str, Number)),
default_value = 0,
result_object = {}
function test_connection(array, i, j) {
if (array[i] && array[i][j] === -1) {
if (!result_object[default_value]) result_object[default_value] = [];
result_object[default_value].push([j, i]);
array[i][j] = 1;
for (var k = offset; k > 0; k--) {
test_connection(array, i + k, j); // left - right
test_connection(array, i, j + k); // top - bottom
test_connection(array, i - k, j); // right - left
test_connection(array, i, j - k); // bottom - top
}
return true
}
}
array.forEach(function(a) {
a.forEach(function(b, i, bb) {
bb[i] = -b
})
});
array.forEach(function(a, i, aa) {
a.forEach(function(b, j, bb) {
test_connection(aa, i, j) && default_value++
})
})
return [result_object];
}
var result = matrix.extract_components_positions(1);
console.log((result))
.as-console-wrapper { max-height: 100% !important; top: 0; }
Edit 1.0 BTW It would be also not that bad if the algorithm is just able to connect bigger components (e.g minimum group of 5 connected characters)
解决方案
Code
This is the method I figured out. I'm sure it can be optimized, but I feel it's at least a big step in the right direction.
I've also taken information from the following answers and applied it.
- Finding all indexes of a specified character within a string
- Check whether an array exists in an array of arrays
var matrix=[
'00000000000000000000000000000000000000000000000000000000000000000000111111111',
'11111100000000000000000000001000000000000000000000000000000000000000000001111',
'00000000000000000000000000000000001000000000000000000000000000000000000000011',
'11111000000000000000000000000000000000000001111110000000000000000000000000001',
'11111000000000000111000000000000000000111111000000000000000000000000000000000',
'00000000000111111111111100000000000000111111000000000000000000000000000000000',
'00000000000000000110000000000000000000111111000000000000000000010000000000000',
'00000000000000000000000000000001111111000000000000000000000000000000000000000',
'00000100000000000000000000000000000000000000000000000000000000000010000000000',
'00000010010000000000000000000000000000111111110000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000000000000000000',
'00000000000000000000000000000000000000000000000000000000000000100000000000000',
'00000000000000000000000000000000000000000000000000000100000000000000000000000'
]
var results = [];
function charPos(str, char) {
return str
.split("")
.map(function (c, i) { if (c == char) return i; })
.filter(function (v) { return v >= 0; });
}
matrix.forEach(function(s, i) {
var p = charPos(s, '1');
results[i] = [];
matrix.forEach(function(s2, i2) {
var p2;
if((p2 = charPos(s2, '1').filter((n) => p.includes(n))).length) {
p2.forEach(function(v) {
if(JSON.stringify(results).indexOf(JSON.stringify([v, i2])) === -1)
results[i].push([v, i2]);
});
}
});
});
console.log(results.filter(v => v.length > 0));
这篇关于javascript：快速查找数组中的连接组件（寻找加速/替代方式）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
