如何将多个属性共享 属性 的数据组合在一起
How to group together data which shares a common property for multiple properties
我有一个问题正在努力解决，但无法想出一个好的解决方案。
我有一些数据是这样的：
[
{ id: 0, dad: 'Carl', mum: 'Amanda', cat: 'Mittens' },
{ id: 1, dad: 'Ron', mum: 'Amanda', cat: 'Scratch' },
{ id: 2, dad: 'Carl', mum: 'Lucy', cat: 'Tiddles' },
{ id: 3, dad: 'Barry', mum: 'Florence', cat: 'Nyanko' },
{ id: 4, dad: 'Barry', mum: 'Florence', cat: 'Fluffy' },
{ id: 5, dad: 'Carl', mum: 'Stefanie', cat: 'Snuggles' },
...
]
我想将具有相同爸爸、妈妈或猫名的条目组合在一起。因此，我最终得到这样的组，即第 1 组的任何成员都不会与任何其他组的任何成员共享爸爸、妈妈或猫的名字。第 1 组的一名成员与该组的每位成员共享 爸爸、妈妈或猫的名字。
我首先按每个类别对它们进行分组，如下所示：
const groupedByDad = groupBy(data, ({dad}) => dad);
const groupedByMum = groupBy(data, ({mum}) => mum);
const groupedByCat = groupBy(data, ({cat}) => cat);
const groups = [groupedByDad, groupedByMum, groupedByCat]; // array of groups
然后我只提取 ID，因为我不再需要额外的数据，只提取哪些 ID 属于哪个组。
// in next block I extract just the IDs from the original data
groups.forEach((group) => {
Object.entries(group).forEach(([key, grouping]) => {
group[key] = grouping.map(({id}) => id);
});
});
然后我想出了一个解决方案，我将所有 ID 数组放在一个对象中并遍历 ID 数组，对于每个数组，我找到与第一个相交的所有 ID 数组并将它们组合在一起在一个新数组中并将它们从数组数组中删除。然后我继续下一个剩余的数组并重复直到原始数组为空。问题是：
- 1：速度慢
- 2：如果我在数组数组中有以下id数组：
0: [0, 1, 2]
1: [0, 1, 9]
2: [9, 8, 4]
然后我的算法发现数组 1 与数组 0 相交并将其添加到匹配组中，但发现数组 2 不相交，因为它不与数组 0 相交。但是数组 2 确实与数组 1 相交（因为它们都有 id 9 in) 因此他们必须共享猫、爸爸或妈妈的名字，因此该组也应该添加到组中，但在我的实现中遗漏了。我可以多次重复这个过程，直到找不到新的匹配项，但这看起来很慢而且效率很低。
必须有更好的 method/algorithm 来将共享至少 1 个共同 属性 的条目组合在一起。有人可以告诉我如何最好地进行吗？
我已将代码放在下面以生成一些测试数据并执行初始分组：
const {groupBy, intersection} = require("lodash");
const dadsNames = ["Barry", "John", "Bill", "Ron", "Carl", "Danny",
"Dodger", "Filbert", "Charlie", "Frank"];
const mumsNames = ["Lucy", "Mary", "Alice", "Sarah", "Yvonne", "Sandra",
"Suzie", "Stefanie", "Pearl", "Amanda", "Florence"];
const catsNames = ["Tiddles", "Nyanko", "Paws", "Fluffy", "Scratch", "Snuggles",
"Impy", "Chris", "Mandrew", "Mittens", "Tuxedo", "Sultan"];
const getRandomEntry = (array) => {
return array[Math.floor((Math.random() * array.length))];
};
const data = [];
for (let i = 0; i < 100; i++) {
data.push({id: i, dad: getRandomEntry(dadsNames), mum: getRandomEntry(mumsNames), cat: getRandomEntry(catsNames)});
}
const groupedByDad = groupBy(data, ({dad}) => dad);
const groupedByMum = groupBy(data, ({mum}) => mum);
const groupedByCat = groupBy(data, ({cat}) => cat);
const groups = [groupedByDad, groupedByMum, groupedByCat]; // array of groups
// in next block I extract just the IDs from the original data
groups.forEach((group) => {
Object.entries(group).forEach(([key, grouping]) => {
group[key] = grouping.map(({id}) => id);
});
});
似乎您需要一个递归解决方案来追查所有应该属于一个组的组合，否则正如上面在您的 3 个 id 的小样本中所述，后续数据行条目未正确包含在该组中。 ..
另一种方法是为dad、mum 和cat 属性值分别分配位值，然后确定该行的位掩码，并使用逻辑AND 来确定属于一组的匹配项。当然，一旦找到匹配项，组位掩码将通过逻辑或展开，并继续搜索，直到找不到该组的更多数据行。
使用问题开头的示例数据，每个属性值的位掩码是...
0: {"Carl" => 1n}
1: {"Amanda" => 2n}
2: {"Mittens" => 4n}
3: {"Ron" => 8n}
4: {"Scratch" => 16n}
5: {"Lucy" => 32n}
6: {"Tiddles" => 64n}
7: {"Barry" => 128n}
8: {"Florence" => 256n}
9: {"Nyanko" => 512n}
10: {"Fluffy" => 1024n}
11: {"Stefanie" => 2048n}
12: {"Snuggles" => 4096n}
...然后这些值用于计算数据行位掩码值...
[
{ id: 0, dad: 'Carl', mum: 'Amanda', cat: 'Mittens' }, ==> 7n
{ id: 1, dad: 'Ron', mum: 'Amanda', cat: 'Scratch' }, ==> 26n
{ id: 2, dad: 'Carl', mum: 'Lucy', cat: 'Tiddles' }, ==> 97n
{ id: 3, dad: 'Barry', mum: 'Florence', cat: 'Nyanko' }, ==> 896n
{ id: 4, dad: 'Barry', mum: 'Florence', cat: 'Fluffy' }, ==> 1408n
{ id: 5, dad: 'Carl', mum: 'Stefanie', cat: 'Snuggles' } ==> 6145n
]
现在，遍历行，搜索匹配项。首先，将组掩码设置为第一个可用行，在本例中为 7n。然后，遍历行，将组掩码与行掩码进行 AND 运算。因此，组掩码 (7n) 与行 ID 1 掩码 (26n) 进行“与”运算，得到 2n ("Amanda")。由于这表示匹配，因此将第 1 行添加到组中，并将组掩码更新为 7n 或 26n，即 31n，这是表示“Carl”、“Amanda”、“Mittens”之和的位掩码， “Ron”和“Scratch”。所以现在，31n 是组掩码，31n 与行 id 2 值 (97n) 的 AND 运算结果为 1n，表示“Carl”为公共元素。因此，行 id 2 被添加到组中，现在 31n OR 97n 结果为 127n 作为组掩码，它表示上面列表中的属性“Carl”到“Tiddles”。这将继续，重新遍历列表中剩余的数据行（以查找由于稍后在搜索中将属性添加到组中而被传递的相关行），直到遍历列表并且没有更多数据行添加到当前组中。然后，如果还有剩余的数据行，则创建一个新组，并使用下一个可用数据行来创建新组，并重复检查循环...
实现（使用问题中的代码随机创建 10 个数据行）是...
const dadsNames = ["Barry", "John", "Bill", "Ron", "Carl", "Danny", "Dodger", "Filbert", "Charlie", "Frank"];
const mumsNames = ["Lucy", "Mary", "Alice", "Sarah", "Yvonne", "Sandra", "Suzie", "Stefanie", "Pearl", "Amanda", "Florence"];
const catsNames = ["Tiddles", "Nyanko", "Paws", "Fluffy", "Scratch", "Snuggles", "Impy", "Chris", "Mandrew", "Mittens", "Tuxedo", "Sultan"];
const getRandomEntry = (array) => {
return array[Math.floor((Math.random() * array.length))];
};
var data = [];
for (let i = 0; i < 10; i++) {
data.push({id: i, dad: getRandomEntry(dadsNames), mum: getRandomEntry(mumsNames), cat: getRandomEntry(catsNames)});
}
function getGroupings( data, attr ) {
function getAttrMap( data, attr ) {
let attrMap = new Map();
let attrMapValue = 1n;
let dataMapValue = new Map();
let dataIndexList = new Set();
data.forEach( ( d, i ) => {
dataIndexList.add( i );
dataMapValue.set( i, 0n );
attr.forEach( a => {
let attrValue = d[ a ];
if ( !attrMap.has( attrValue ) ) {
attrMap.set( attrValue, attrMapValue );
attrMapValue <<= 1n;
}
dataMapValue.set( i, dataMapValue.get( i ) + attrMap.get( attrValue ) );
} );
} );
console.log( `Binary mapping of attributes:` );
attrMap.forEach( (v,k) => console.log( `${k}: ${v.toString()}` ) );
console.log( `\nBinary value of each row of data:` );
dataMapValue.forEach( (v,k) => console.log( `${k}: ${v.toString()}` ) );
return [ dataMapValue, dataIndexList ];
}
let groupings = [];
let [ dataMapValue, dataIndexList ] = getAttrMap( data, ['dad','mum','cat'] );
while ( dataIndexList.size ) {
let group = new Set();
let dataRow = dataIndexList.keys().next().value;
let mask = dataMapValue.get( dataRow );
do {
let entryLength = dataIndexList.size;
dataIndexList.forEach( k => {
if ( mask & dataMapValue.get( k ) ) {
group.add( k );
dataIndexList.delete( k );
mask |= dataMapValue.get( k );
}
} );
if ( entryLength === dataIndexList.size ) break;
} while ( true );
groupings.push( group );
}
return groupings;
}
let result = getGroupings( data, ['dad','mum','cat'] );
console.log( `\nData:` );
console.log( data );
console.log( `\nFinal Groupings` );
console.log( result.map( s => [...s] ) );
请注意，由于爸爸、妈妈和猫属性的数量较少，因此随着数据行数的增加，所有行属于同一组的可能性就越高。因此，上面的代码只选择了 10 个随机条目。
我有一个问题正在努力解决，但无法想出一个好的解决方案。
我有一些数据是这样的：
[
{ id: 0, dad: 'Carl', mum: 'Amanda', cat: 'Mittens' },
{ id: 1, dad: 'Ron', mum: 'Amanda', cat: 'Scratch' },
{ id: 2, dad: 'Carl', mum: 'Lucy', cat: 'Tiddles' },
{ id: 3, dad: 'Barry', mum: 'Florence', cat: 'Nyanko' },
{ id: 4, dad: 'Barry', mum: 'Florence', cat: 'Fluffy' },
{ id: 5, dad: 'Carl', mum: 'Stefanie', cat: 'Snuggles' },
...
]
我想将具有相同爸爸、妈妈或猫名的条目组合在一起。因此，我最终得到这样的组，即第 1 组的任何成员都不会与任何其他组的任何成员共享爸爸、妈妈或猫的名字。第 1 组的一名成员与该组的每位成员共享 爸爸、妈妈或猫的名字。
我首先按每个类别对它们进行分组，如下所示：
const groupedByDad = groupBy(data, ({dad}) => dad);
const groupedByMum = groupBy(data, ({mum}) => mum);
const groupedByCat = groupBy(data, ({cat}) => cat);
const groups = [groupedByDad, groupedByMum, groupedByCat]; // array of groups
然后我只提取 ID，因为我不再需要额外的数据，只提取哪些 ID 属于哪个组。
// in next block I extract just the IDs from the original data
groups.forEach((group) => {
Object.entries(group).forEach(([key, grouping]) => {
group[key] = grouping.map(({id}) => id);
});
});
然后我想出了一个解决方案，我将所有 ID 数组放在一个对象中并遍历 ID 数组，对于每个数组，我找到与第一个相交的所有 ID 数组并将它们组合在一起在一个新数组中并将它们从数组数组中删除。然后我继续下一个剩余的数组并重复直到原始数组为空。问题是：
- 1：速度慢
- 2：如果我在数组数组中有以下id数组： 0: [0, 1, 2] 1: [0, 1, 9] 2: [9, 8, 4] 然后我的算法发现数组 1 与数组 0 相交并将其添加到匹配组中，但发现数组 2 不相交，因为它不与数组 0 相交。但是数组 2 确实与数组 1 相交（因为它们都有 id 9 in) 因此他们必须共享猫、爸爸或妈妈的名字，因此该组也应该添加到组中，但在我的实现中遗漏了。我可以多次重复这个过程，直到找不到新的匹配项，但这看起来很慢而且效率很低。
必须有更好的 method/algorithm 来将共享至少 1 个共同 属性 的条目组合在一起。有人可以告诉我如何最好地进行吗？
我已将代码放在下面以生成一些测试数据并执行初始分组：
const {groupBy, intersection} = require("lodash");
const dadsNames = ["Barry", "John", "Bill", "Ron", "Carl", "Danny",
"Dodger", "Filbert", "Charlie", "Frank"];
const mumsNames = ["Lucy", "Mary", "Alice", "Sarah", "Yvonne", "Sandra",
"Suzie", "Stefanie", "Pearl", "Amanda", "Florence"];
const catsNames = ["Tiddles", "Nyanko", "Paws", "Fluffy", "Scratch", "Snuggles",
"Impy", "Chris", "Mandrew", "Mittens", "Tuxedo", "Sultan"];
const getRandomEntry = (array) => {
return array[Math.floor((Math.random() * array.length))];
};
const data = [];
for (let i = 0; i < 100; i++) {
data.push({id: i, dad: getRandomEntry(dadsNames), mum: getRandomEntry(mumsNames), cat: getRandomEntry(catsNames)});
}
const groupedByDad = groupBy(data, ({dad}) => dad);
const groupedByMum = groupBy(data, ({mum}) => mum);
const groupedByCat = groupBy(data, ({cat}) => cat);
const groups = [groupedByDad, groupedByMum, groupedByCat]; // array of groups
// in next block I extract just the IDs from the original data
groups.forEach((group) => {
Object.entries(group).forEach(([key, grouping]) => {
group[key] = grouping.map(({id}) => id);
});
});
似乎您需要一个递归解决方案来追查所有应该属于一个组的组合，否则正如上面在您的 3 个 id 的小样本中所述，后续数据行条目未正确包含在该组中。 ..
另一种方法是为dad、mum 和cat 属性值分别分配位值，然后确定该行的位掩码，并使用逻辑AND 来确定属于一组的匹配项。当然，一旦找到匹配项，组位掩码将通过逻辑或展开，并继续搜索，直到找不到该组的更多数据行。
使用问题开头的示例数据，每个属性值的位掩码是...
0: {"Carl" => 1n}
1: {"Amanda" => 2n}
2: {"Mittens" => 4n}
3: {"Ron" => 8n}
4: {"Scratch" => 16n}
5: {"Lucy" => 32n}
6: {"Tiddles" => 64n}
7: {"Barry" => 128n}
8: {"Florence" => 256n}
9: {"Nyanko" => 512n}
10: {"Fluffy" => 1024n}
11: {"Stefanie" => 2048n}
12: {"Snuggles" => 4096n}
...然后这些值用于计算数据行位掩码值...
[
{ id: 0, dad: 'Carl', mum: 'Amanda', cat: 'Mittens' }, ==> 7n
{ id: 1, dad: 'Ron', mum: 'Amanda', cat: 'Scratch' }, ==> 26n
{ id: 2, dad: 'Carl', mum: 'Lucy', cat: 'Tiddles' }, ==> 97n
{ id: 3, dad: 'Barry', mum: 'Florence', cat: 'Nyanko' }, ==> 896n
{ id: 4, dad: 'Barry', mum: 'Florence', cat: 'Fluffy' }, ==> 1408n
{ id: 5, dad: 'Carl', mum: 'Stefanie', cat: 'Snuggles' } ==> 6145n
]
现在，遍历行，搜索匹配项。首先，将组掩码设置为第一个可用行，在本例中为 7n。然后，遍历行，将组掩码与行掩码进行 AND 运算。因此，组掩码 (7n) 与行 ID 1 掩码 (26n) 进行“与”运算，得到 2n ("Amanda")。由于这表示匹配，因此将第 1 行添加到组中，并将组掩码更新为 7n 或 26n，即 31n，这是表示“Carl”、“Amanda”、“Mittens”之和的位掩码， “Ron”和“Scratch”。所以现在，31n 是组掩码，31n 与行 id 2 值 (97n) 的 AND 运算结果为 1n，表示“Carl”为公共元素。因此，行 id 2 被添加到组中，现在 31n OR 97n 结果为 127n 作为组掩码，它表示上面列表中的属性“Carl”到“Tiddles”。这将继续，重新遍历列表中剩余的数据行（以查找由于稍后在搜索中将属性添加到组中而被传递的相关行），直到遍历列表并且没有更多数据行添加到当前组中。然后，如果还有剩余的数据行，则创建一个新组，并使用下一个可用数据行来创建新组，并重复检查循环...
实现（使用问题中的代码随机创建 10 个数据行）是...
const dadsNames = ["Barry", "John", "Bill", "Ron", "Carl", "Danny", "Dodger", "Filbert", "Charlie", "Frank"];
const mumsNames = ["Lucy", "Mary", "Alice", "Sarah", "Yvonne", "Sandra", "Suzie", "Stefanie", "Pearl", "Amanda", "Florence"];
const catsNames = ["Tiddles", "Nyanko", "Paws", "Fluffy", "Scratch", "Snuggles", "Impy", "Chris", "Mandrew", "Mittens", "Tuxedo", "Sultan"];
const getRandomEntry = (array) => {
return array[Math.floor((Math.random() * array.length))];
};
var data = [];
for (let i = 0; i < 10; i++) {
data.push({id: i, dad: getRandomEntry(dadsNames), mum: getRandomEntry(mumsNames), cat: getRandomEntry(catsNames)});
}
function getGroupings( data, attr ) {
function getAttrMap( data, attr ) {
let attrMap = new Map();
let attrMapValue = 1n;
let dataMapValue = new Map();
let dataIndexList = new Set();
data.forEach( ( d, i ) => {
dataIndexList.add( i );
dataMapValue.set( i, 0n );
attr.forEach( a => {
let attrValue = d[ a ];
if ( !attrMap.has( attrValue ) ) {
attrMap.set( attrValue, attrMapValue );
attrMapValue <<= 1n;
}
dataMapValue.set( i, dataMapValue.get( i ) + attrMap.get( attrValue ) );
} );
} );
console.log( `Binary mapping of attributes:` );
attrMap.forEach( (v,k) => console.log( `${k}: ${v.toString()}` ) );
console.log( `\nBinary value of each row of data:` );
dataMapValue.forEach( (v,k) => console.log( `${k}: ${v.toString()}` ) );
return [ dataMapValue, dataIndexList ];
}
let groupings = [];
let [ dataMapValue, dataIndexList ] = getAttrMap( data, ['dad','mum','cat'] );
while ( dataIndexList.size ) {
let group = new Set();
let dataRow = dataIndexList.keys().next().value;
let mask = dataMapValue.get( dataRow );
do {
let entryLength = dataIndexList.size;
dataIndexList.forEach( k => {
if ( mask & dataMapValue.get( k ) ) {
group.add( k );
dataIndexList.delete( k );
mask |= dataMapValue.get( k );
}
} );
if ( entryLength === dataIndexList.size ) break;
} while ( true );
groupings.push( group );
}
return groupings;
}
let result = getGroupings( data, ['dad','mum','cat'] );
console.log( `\nData:` );
console.log( data );
console.log( `\nFinal Groupings` );
console.log( result.map( s => [...s] ) );
请注意，由于爸爸、妈妈和猫属性的数量较少，因此随着数据行数的增加，所有行属于同一组的可能性就越高。因此，上面的代码只选择了 10 个随机条目。