javascript中数据分组的优化算法

Question

以下(简化的) json数据类型定义了联系人：

{
  id:   number;
  name: string;
  phone: string;
  email: string
}

以下是一组数据：

+---+----------+-------------+---------------------------+ 
|id | name     | phone       |email                      | 
+---+----------+-------------+---------------------------+
|1  | John     | 11111111    |aaaa@test.com              | 
|2  | Marc     | 22222222    |bbbb@test.com              | 
|3  | Ron      | 99999999    |aaaa@test.com              |
|4  | Andrew   | 55555555    |dddd@test.com              |
|5  | Wim      | 99999999    |gggg@test.com              |
|6  | Marc     | 33333333    |cccc@test.com              |
|7  | Dan      | 44444444    |cccc@test.com              |
+---+----------+-------------+---------------------------+

目标是使用javascript(可以选择提交，但主要思想是根据以下约束使算法清晰)找到属于同一组的组:当下列任何条件相同时，联系人属于一个组:姓名、电话或电子邮件。结果显示id在数组中分组为数组。忽略1组中的联系人。

在上面的例子中，这意味着与In 1,3,5的联系人属于一起，因为1,3共享相同的电子邮件，3和5共享相同的电话号码。同样，2,6,7: 2和6有相同的名字，6和7有相同的电子邮件。5没有任何共同之处。因此，预期结果是：

[[1,3,5], [2,6,7]]

背景:一种可行的解决方案是遍历每一项，并检查列表的其余部分是否名称、电子邮件或电话是否相同。如果是这样的话，将它们分组，并将它们从列表中删除(在示例中，我们将1与列表中的所有项进行比较，只找到3项)。问题是，还需要再次检查这些组的下一项，因为在本例中，尚未作为组的一部分检测到5。这使得算法变得复杂，而我怀疑有一种简单的方法可以在线性时间内解决这个问题。这类问题也可能有个名字吗？

Answer 1

想法：

• 从0组开始
• 迭代联系人列表
• 检查是否有一个具有联系人名称、电话或电子邮件的组。将这些组的所有成员合并为同一个组。那就把你自己加入那组吧。如果不是，开始一个新的小组与自己，并设置名称，电话和电子邮件组作为你自己。

Union查找是处理不相交集合并的有效结构。从这里获取的代码。由于它使用路径压缩和按秩合并，您可以考虑整个代码在接触的数量上是线性的。

​

var data = [
      {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'},
      {id:2,name:'Marc',phone:'99999999',email:'bbbb@test.com'},
      {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'},
      {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'},
      {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'},
      {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'},
      {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'}
];

// 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.log(result)

​

Answer 2

任何迭代每个n条目，然后遍历要匹配的越来越多的m组的答案，都将具有O(n*m)最差的时间性能(当在任何条件下没有两个条目匹配时发现)。

任何迭代每个条目，然后遍历组，并使用数组测试q选项之间匹配值的答案，都必须支付每次匹配的O(q)代价。在最坏的情况下，假设所有的电子邮件相同，所有的电话都不同，这将意味着O(n*m)。

我相信这个答案是O(n)，因为假设要匹配的字段数是一个常量(在本例中为3：name、phone和email)，主循环中的所有操作(每个条目运行一次)都是O(1)。

另一个复杂的问题是，在这个过程的后期，我们可能会在两个(甚至3个)组之间找到一个桥梁，因为条目可以在不同的字段上与来自不同组的条目相匹配。这种情况可能会发生好几次。为了避免在主循环期间重建组，我们将合并放在最末端，首先构建一个什么组结束位置的映射，然后最后将所有入口ID移到它们的最后一个组。所有这些都可以在O(m)中完成，有m个组的数量；当实际将条目in复制到合并的组时，使用一个额外的O(n)：总的来说，我们仍然处于O(n)区域。

最后一行从合并的组中构建ids数组，并筛选出没有超过一个元素的任何ids。

const data = [
    {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'},
    {id:2,name:'Marc',phone:'99999999',email:'bbbb@test.com'},
    {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'},
    {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'},
    {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'},
    {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'},
    {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'}
];

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.log(""+JSON.stringify(groups))
// output is [[1,2,3,5,6,7]]

Answer 3

这是另一条你可以走的路线的建议。其思想是使用一个Array.reduce按id分组，并将所有值(vls)和组合结果(ids)保存在该accumulator object中。

通过这种方式，您可以轻松地使用Array.some + Array.includes (这就是getGroupId函数所做的)来比较getGroupId。

一旦您分组并获得了几乎最终的结果，只需prettify，方法是删除带有一个length的组，然后只选择其余的ids数组：

​

var data = [ {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'}, {id:2,name:'Marc',phone:'22222222',email:'bbbb@test.com'}, {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'}, {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'}, {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'}, {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'}, {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'} ];

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.log(prettify(group(data)))

​

需要注意的一点是，我们不关心属性的数量，因为我们做了Object.values。因此，您可以轻松地将另一个address或fax添加到该列表中，并且仍然可以使用zero code changes。

根据反馈，这里有另一个版本，它的工作方式略有不同：

​

var data = [ {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'}, {id:2,name:'Marc',phone:'22222222',email:'bbbb@test.com'}, {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'}, {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'}, {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'}, {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'}, {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'} ];
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.log(prettify(group(data)))      // OP data
console.log(prettify(group(testData)))  // Test data

​

这个版本的原因是由于testData提供的@Mark提供的第二个元素不匹配的第一个，但匹配的第三个，实际上是匹配的第一个.所以它们都应该是命中的。

为了达到这个目的，一旦我们找到了匹配，我们就会查找相同初始匹配的匹配，并将其推入相同的组中，这样我们就可以获得匹配的最大数据量。

结果是，一旦我们得到了第一组第一个元素，然后我们找到并推送第三个，从那里，它更容易匹配第二个。这个逻辑稍微复杂一些，我可以想象它表现得不那么好。