#javascript #arrays #group-by #grouping
#javascript #массивы #групповое-по #группировка
Вопрос:
У меня есть проблема, над решением которой я работаю, и мне трудно найти хорошее решение.
У меня есть некоторые данные, которые выглядят так:
[
{ 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
Затем я извлекаю только идентификаторы, поскольку мне больше не нужны дополнительные данные, только какие идентификаторы принадлежат к какой группе.
// 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);
});
});
Затем я придумал решение, в котором я помещаю все массивы идентификаторов в 1 объект и перебираю массивы идентификаторов, для каждого массива я нахожу все массивы идентификаторов, которые пересекают первый, группирую их вместе в новый массив и удаляю их из массива массивов. Затем я перехожу к следующему оставшемуся массиву и повторяю, пока исходный массив массивов не станет пустым. Проблема в этом:
- 1: это медленно
- 2: Если у меня есть следующие массивы идентификаторов в массиве массивов: 0: [0, 1, 2] 1: [0, 1, 9] 2: [9, 8, 4] затем мой алгоритм обнаруживает, что массив 1 пересекает массив 0 и добавляет его в соответствующие группы, но обнаруживает, что массив 2 этого не делает, поскольку он не пересекает массив 0. Однако массив 2 пересекает массив 1 (поскольку оба они имеют идентификатор 9 в), и поэтому они должны иметь общее имя кошки, папы или мамы, поэтому эта группа также должна быть добавлена в группу, но в моей реализации она отсутствует. Я мог бы повторить процедуру несколько раз, пока не будут найдены новые совпадения, но это кажется медленным и действительно неэффективным.
Должен быть лучший метод / алгоритм для группировки записей, которые имеют как минимум 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);
});
});
Ответ №1:
Похоже, вам нужно рекурсивное решение для поиска всех комбинаций, которые должны попасть в одну группу, в противном случае, как отмечалось выше в вашей небольшой выборке из 3 идентификаторов, последующие записи строк данных не будут должным образом включены в группу…
Другой альтернативой является присвоение битовых значений каждому из значений атрибутов dad, mum и cat, затем определение битовой маски строки и использование логического И для определения совпадений, принадлежащих группе. Конечно, как только совпадение найдено, битовая маска группы расширяется с помощью логического ИЛИ, и поиск продолжается до тех пор, пока для группы не будет найдено больше строк данных.
Используя пример данных в начале вопроса, битовые маски для каждого значения атрибута следующие…
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. Затем строки обходятся, заменяя групповую маску маской строки. Итак, маска группы (7n) дополняется маской идентификатора строки 1 (26n), в результате чего получается 2n ( «Аманда»). Поскольку это указывает на совпадение, строка 1 затем добавляется в группу, а маска группы обновляется до 7n ИЛИ 26n, что равно 31n, что является битовой маской, представляющей сумму «Карл», «Аманда», «Варежки», «Рон» и «Скретч». Итак, теперь 31n — это маска группы, а 31n, дополненный значением идентификатора строки 2 (97n), приводит к 1n, представляющему «Carl» как общий элемент. Итак, идентификатор строки 2 добавляется в группу, и теперь 31n ИЛИ 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 amp; 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] ) ); Обратите внимание, что из-за небольшого количества атрибутов dad, mum и cat, чем больше вы увеличиваете количество строк данных, тем выше вероятность того, что все строки попадут в одну группу. Следовательно, приведенный выше код выбирает только 10 случайных записей.