Оптимальный алгоритм группировки данных в javascript

Один из способов добиться того, что вам нужно, - разделить контакты на группы. Каждая группа будет содержать список names, phones и emails.

Затем переберите контакты и посмотрите, попадает ли текущий контакт в какую-либо из групп. Если нет, создайте новую группу и установите для нее names/phones/emails, чтобы следующие контакты могли попасть в одну и ту же группу.

var data = [
      {id:1,name:'John',phone:'11111111',email:'[email protected]'},
      {id:2,name:'Marc',phone:'22222222',email:'[email protected]'},
      {id:3,name:'Ron',phone:'99999999',email:'[email protected]'},
      {id:4,name:'Andrew',phone:'55555555',email:'[email protected]'},
      {id:5,name:'Wim',phone:'99999999',email:'[email protected]'},
      {id:6,name:'Marc',phone:'33333333',email:'[email protected]'},
      {id:7,name:'Dan',phone:'44444444',email:'[email protected]'}
];

var groups = [];

data.forEach(function(person){
  var phone = person.phone;
  var email = person.email;
  var name = person.name;
  var id = person.id;
  var found = false;
  groups.forEach(function(g){
    if (    g.names.indexOf(name) > -1 
        || g.phones.indexOf(phone)>-1 
        || g.emails.indexOf(email)>-1) {
      found = true;
      g.names.push(name);
      g.phones.push(phone);
      g.emails.push(email);
      g.people.push(id);
    }
  });
  if (!found) {
      groups.push({names:[name],phones:[phone],emails:[email],people:[id]});
  }
  
  
});
var output=[];
groups.forEach(function(g){
  output.push(g.people);
});
console.info(output);   //[ [1,3,5] , [2,6,7] , [4] ]

Идея:

• Начать с 0 групп
• Итерируйте свой список контактов
• Проверьте, есть ли группа с именем, телефоном или адресом электронной почты контакта. Объедините всех членов этих групп в одну группу. Затем добавьте себя в эту группу. Если нет, создайте новую группу с собой и установите имя, телефон и адрес электронной почты для себя.

Union find - это эффективная структура для обработки слияния непересекающиеся множества. Код взят из здесь. Поскольку он использует сжатие путей и объединение по рангу, вы можете считать, что весь код линейен по количеству контактов.

var data = [
      {id:1,name:'John',phone:'11111111',email:'[email protected]'},
      {id:2,name:'Marc',phone:'99999999',email:'[email protected]'},
      {id:3,name:'Ron',phone:'99999999',email:'[email protected]'},
      {id:4,name:'Andrew',phone:'55555555',email:'[email protected]'},
      {id:5,name:'Wim',phone:'99999999',email:'[email protected]'},
      {id:6,name:'Marc',phone:'33333333',email:'[email protected]'},
      {id:7,name:'Dan',phone:'44444444',email:'[email protected]'}
];

// UNION-FIND structure, with path comression and union by rank

var UNIONFIND = (function () {
    
    function _find(n)
    {
        if (n.parent == n) return n;	
        n.parent = _find(n.parent);	
        return n.parent;
    }
    
    return {
        makeset:function(id){    
            var newnode = {
                parent: null,
                id: id,
                rank: 0
            };
            newnode.parent = newnode;            
            return newnode;
        },
    
        find: _find,
     
        combine: function(n1, n2) {                                    
            var n1 = _find(n1);
            var n2 = _find(n2);
            
            if (n1 == n2) return;
        
            if (n1.rank < n2.rank)
            {
                n2.parent = n2;
                return n2;
            }
            else if (n2.rank < n1.rank)
            {
                n2.parent = n1;
                return n1;
            }
            else
            {
                n2.parent = n1;
                n1.rank += 1;
                return n1;
            }
        }
    };
})();

var groupHash = {name: {}, phone: {}, email: {}}
var groupNodes = []

data.forEach(function(contact){
  var group = UNIONFIND.makeset(contact.id);
  var groups = new Set();
  ["name", "phone", "email"].forEach(function(attr){
    if (groupHash[attr].hasOwnProperty(contact[attr])) groups.add(groupHash[attr][contact[attr]])
  });
  
  groups = Array.from(groups);
  groups.push(group);
  groupNodes.push(group);
  
  for(var i = 1; i < groups.length; i++) {
    UNIONFIND.combine(groups[0], groups[i]);
  }  
  
  ["name", "phone", "email"].forEach(function(attr){
      groupHash[attr][contact[attr]] = groups[0];
  });
  
})

var contactsInGroup = {}


groupNodes.forEach(function(group){
    var groupId = UNIONFIND.find(group).id;
    
    if (contactsInGroup.hasOwnProperty(groupId) == false) {
      contactsInGroup[groupId] = [];
    }
    
    contactsInGroup[groupId].push(group.id);
})

var result = Object.values(contactsInGroup).filter(function(list){
 return list.length > 1
})

console.info(result)

Вот еще один вариант пути, по которому вы могли бы пойти. Идея состоит в том, чтобы использовать один Array.reduce для группировки по id и сохранить все значения (vls) и объединенные результаты (ids) в этом accumulator object.

Таким образом, вы можете легко сравнить name/phone/email, используя Array.some + Array.includes (что и делает функция getGroupId).

После того, как вы сгруппировали и получили почти окончательный результат, просто prettify, удалив группы с length из одного и выбрав только массив ids из остальных:

var data = [ {id:1,name:'John',phone:'11111111',email:'[email protected]'}, {id:2,name:'Marc',phone:'22222222',email:'[email protected]'}, {id:3,name:'Ron',phone:'99999999',email:'[email protected]'}, {id:4,name:'Andrew',phone:'55555555',email:'[email protected]'}, {id:5,name:'Wim',phone:'99999999',email:'[email protected]'}, {id:6,name:'Marc',phone:'33333333',email:'[email protected]'}, {id:7,name:'Dan',phone:'44444444',email:'[email protected]'} ];

const getGroupId = (obj, vals) => Object.entries(obj)
   .find(([k,v]) => v.vls.some(x => vals.includes(x))) || []

const group = d => d.reduce((r, c) => {
   let values = Object.values(c), groupID = getGroupId(r, values)[0]
	
   if (!groupID)	
      r[c.id] = ({ vls: values, ids: [...r[c.id] || [], c.id] })
   else {
      r[groupID] = ({
         vls: [...r[groupID].vls, ...values], ids: [...r[groupID].ids, c.id]
      })
   }
   return r
}, {})

const prettify = grp => Object.values(grp).reduce((r,c) => {
   if (c.ids.length > 1)
     r.push(c.ids)
     return r
}, [])

console.info(prettify(group(data)))

Следует отметить, что нас не волнует количество свойств, поскольку мы делаем Object.values. Таким образом, вы можете легко добавить еще один address или fax в этот список, и он все равно будет работать с zero code changes.

Согласно отзывам, вот еще одна версия, которая работает немного иначе:

var data = [ {id:1,name:'John',phone:'11111111',email:'[email protected]'}, {id:2,name:'Marc',phone:'22222222',email:'[email protected]'}, {id:3,name:'Ron',phone:'99999999',email:'[email protected]'}, {id:4,name:'Andrew',phone:'55555555',email:'[email protected]'}, {id:5,name:'Wim',phone:'99999999',email:'[email protected]'}, {id:6,name:'Marc',phone:'33333333',email:'[email protected]'}, {id:7,name:'Dan',phone:'44444444',email:'[email protected]'} ];
var testData = [{ id: 1, name: 'John', phone: '1', email: 'a' }, { id: 2, name: 'Marc', phone: '2', email: 'b' }, { id: 3, name: 'Ron', phone: '1', email: 'b' }]; 

const getGroupId = (obj, vals) => Object.entries(obj)
  .find(([k,v]) => v.vls.some(x => vals.includes(x))) || []

const group = d => d.reduce((r,c,i,a) => {
  let values = Object.values(c), groupID = !i ? i : getGroupId(r, values)[0]

  if (!groupID) {		
    let hits = a.filter(x => 
       x.id != c.id && values.some(v => Object.values(x).includes(v)))
    hits.forEach(h => 
       r[c.id] = ({ vls: [...values, ...Object.values(h)], ids: [c.id, h.id] }))
  }
  else
    r[groupID] = r[groupID].ids.includes(c.id) ? r[groupID] : 
      ({ vls: [...r[groupID].vls, ...values], ids: [...r[groupID].ids, c.id] })      
  return r
}, {})

const prettify = grp => Object.values(grp).reduce((r, c) => {
  if (c.ids.length > 1)
    r.push(c.ids)
  return r
}, [])

console.info(prettify(group(data)))      // OP data
console.info(prettify(group(testData)))  // Test data

Причина этой версии связана с testData, предоставленным @Mark, у которого 2-й элемент не соответствует первому, но соответствует 3-му элементу, который фактически совпадает с 1-м ... так что все они должны быть хитами.

Чтобы добраться до этого, как только мы находим совпадение, мы ищем совпадения с тем же начальным совпадением и вставляем в ту же группу, чтобы у нас было максимальное количество данных для сопоставления.

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

Любой ответ, который повторяется по каждой записи n, а затем по растущему списку групп m для сопоставления, будет иметь худшую производительность O(n*m) (обнаруживается, когда нет двух записей, совпадающих по любому термину).

Любой ответ, который повторяется по каждой записи, а затем по группам и использует массивы для проверки совпадения значений среди опций q, дополнительно должен будет уплатить штраф в размере O(q) за совпадение. В худшем случае, если, скажем, все электронные письма одинаковы, а все телефоны разные, это будет означать O(n*m).

Я считаю, что это O(n), потому что, если предположить, что количество полей для сопоставления является константой (в данном случае 3: name, phone и email), все операции в основном цикле, который выполняется один раз для каждой записи, являются O(1) .

Существует дополнительная сложность, позволяющая исправить тот факт, что в конце процесса мы можем найти мост между двумя (или даже 3) группами, поскольку записи могут совпадать в разных полях с записями из разных групп. Это может случиться несколько раз. Чтобы не перестраивать группы во время основного цикла, мы оставляем слияние до самого конца, где сначала строим карту what-group-end-up-where, а затем, наконец, перемещаем все идентификаторы записей в их последнюю группу. Все это можно сделать в O(m) с числом групп m; с дополнительным O(n) при фактическом копировании идентификаторов записей в объединенные группы: в целом мы все еще находимся на территории O(n).

Последняя строка создает массивы идентификаторов из объединенных групп и отфильтровывает все, в которых не более 1 элемента.

const data = [
    {id:1,name:'John',phone:'11111111',email:'[email protected]'},
    {id:2,name:'Marc',phone:'99999999',email:'[email protected]'},
    {id:3,name:'Ron',phone:'99999999',email:'[email protected]'},
    {id:4,name:'Andrew',phone:'55555555',email:'[email protected]'},
    {id:5,name:'Wim',phone:'99999999',email:'[email protected]'},
    {id:6,name:'Marc',phone:'33333333',email:'[email protected]'},
    {id:7,name:'Dan',phone:'44444444',email:'[email protected]'}
];

const groups = function(inputs) {

    let valuesToGroups = new Map(
        ['name', 'phone', 'email'].map(key => [key, new Map()]));
    let groups = new Map();
    let pendingMerges = [];
    for (const entry of inputs) {
        let group = undefined;
        let found = [];
        for (const [key, valueMap] of valuesToGroups) {
            // look up value in values-index for current key
            group = valueMap.get(entry[key]);
            if (group !== undefined) {
                found.push(group);
                // not breaking allows groups to be merged
            }
        }
        if (found.length === 0) {
            // not found: create new group
            group = groups.size;
            groups.set(group, [entry.id]);
        } else {
            // found: add entry to chosen group
            group = found[0];
            groups.get(group).push(entry.id);
            if (found.length > 1) {
                pendingMerges.push(found);
            }
        }
        // add entry's values to index, pointing to group
        for (const [key, valueMap] of valuesToGroups) {
            valueMap.set(entry[key], group); 
        }        
    }
    // do pending merges; initially, all groups are stand-alone
    let merges = new Map(Array.from(groups.keys()).map(k => [k, k]));
    for (const merge of pendingMerges) {
        // contents will go to the lowest-numbered group
        const sorted = merge.map(groupId => merges.get(groupId)).sort();
        sorted.forEach(groupId => merges.set(groupId, sorted[0]));
    }
    const cleanGroups = new Map();
    groups.forEach((value, key) => { 
        const k = merges.get(key); 
        if ( ! cleanGroups.has(k)) {
            cleanGroups.set(k, []);
        }
        value.forEach(id => cleanGroups.get(k).push(id))
    })
    // return only non-empty groups
    return [... cleanGroups].filter(g => g[1].length>1).map(g => [... g[1]]);
}(data);

console.info(""+JSON.stringify(groups))
// output is [[1,2,3,5,6,7]]