JavaScript中最佳的算法分组数据

Question

以下是（简化后的）JSON数据类型，定义了一个联系人： ```html

以下是（简化后的）JSON数据类型，定义了一个联系人：

```

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

有以下一组数据：

+---+----------+-------------+---------------------------+ 
|id | name     | phone       |email                      | 
+---+----------+-------------+---------------------------+
|1  | John     | 11111111    |[e-mail]              | 
|2  | Marc     | 22222222    |[e-mail]              | 
|3  | Ron      | 99999999    |[e-mail]              |
|4  | Andrew   | 55555555    |[e-mail]              |
|5  | Wim      | 99999999    |[e-mail]              |
|6  | Marc     | 33333333    |[e-mail]              |
|7  | Dan      | 44444444    |[e-mail]              |
+---+----------+-------------+---------------------------+

目标是使用JavaScript（可选Lodash，但主要思路是清晰的算法）找到属于同一组的联系人，根据以下约束条件：当名称、电话或电子邮件相同时，联系人属于一个组。结果显示作为数组的ID分组的数组。属于1组的联系人将被忽略。

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

背景： 一种有效的解决方案是对每个项目进行迭代，并检查列表的余下部分是否具有相同的名称、电子邮件或电话。如果是，则将它们分组并从列表中取出（在示例中，我们将1与列表中的所有项进行比较，只发现3）。问题是需要再次检查下一个项目是否属于这些组，因为在这种情况下还未检测到5作为组的一部分。这使得算法变得复杂，而我怀疑在线性时间内解决这个问题的简单方法。这种类问题可能也有一个名称？

- Han

---

看起来这是一个很酷的问题...只是为了确保我理解正确：如果#2有以下电话号码，期望的结果会是什么？ 99999999？它会是 [[1, 2, 3, 5, 6, 7]] 吗？ - Josep

正确，我们将会有一个组。 - Han

Answer 1

思路：

• 从0个组开始
• 迭代您的联系人列表
• 检查是否存在一个以联系人姓名、电话或电子邮件为名的组。将这些组的所有成员合并为同一组。然后将自己添加到该组中。如果没有，则以自己为起点开始一个新组，并将名称、电话和电子邮件组设置为自己。

并查集是处理不相交集合合并的有效结构。代码取自此处。由于它使用路径压缩和按秩合并，因此可以认为整个代码对联系人数量是线性的。

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

// 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)

- juvian

---

使用Map而不是JS对象可以避免使用hasOwnProperty。您已经在使用具有类似API和优势的Set。 - tucuxi

你的代码似乎大部分与我的相同，但你在运行时即时合并组，而我则等待所有组建立完成后才开始处理合并。两种方法都应该是按照项目数量线性执行的。 - tucuxi

@tucuxi 我通常只使用 map 来进行对象引用，但它确实可以被使用。这是一个不需要额外结构（如并查集）的好解决方案。我已经测试了数据复制达到 450k 条目，你的代码执行时间为 850ms，而我的为 1050ms，两者都是线性的 ^^ - juvian

Answer 2

任何一个迭代每个 n 条目，然后在一个不断增长的 m 组列表上进行匹配的答案，其最坏时间性能将为 O(n*m)（当没有任何两个条目在任何项上匹配时发现）。

任何一个迭代每个条目，然后遍历组，并使用数组来测试匹配值中的 q 选项的答案，将进一步支付每次匹配的 O(q) 的惩罚。在最坏情况下，例如所有电子邮件相同且所有电话号码不同，这将意味着 O(n*m)。

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

有一个额外的复杂性需要解决，即在过程的后期，我们可能会发现两个（甚至三个）组之间的桥梁，因为条目可以在不同的字段上与来自不同组的条目匹配。这可能会发生多次。为避免在主循环期间重建组，我们将合并留到最后，首先建立一个映射表，指示每个组最终会移动到哪里，然后最终将所有条目 ID 移动到其最终组。这可以在 O(m) 的时间内完成，其中 m 是组数；在实际将条目 ID 复制到合并组时还需要额外的 O(n)：总体而言，我们仍处于 O(n) 领域。

最后一行从合并的组中构建 id 数组，并过滤掉任何不超过1个元素的数组。

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

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]]

- tucuxi

Answer 3

这里有另一个建议，你可以采取这种方法。想法是使用一个 Array.reduce 来按 id 进行分组，并将所有值 (vls) 和组合结果 (ids) 保存在该 accumulator object 中。

这样，你就可以轻松地使用 Array.some + Array.includes（这就是 getGroupId 函数所做的）来比较 name/phone/email。

一旦你分组并且几乎得到最终结果，只需通过删除长度为一的组并仅选择其余部分的 ids 数组来 prettify 它：

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

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添加到列表中，而且仍然可以在零代码更改的情况下正常工作。

根据反馈，这里有另一个略有不同的版本：

var data = [ {id:1,name:'John',phone:'11111111',email:'[e-mail]'}, {id:2,name:'Marc',phone:'22222222',email:'[e-mail]'}, {id:3,name:'Ron',phone:'99999999',email:'[e-mail]'}, {id:4,name:'Andrew',phone:'55555555',email:'[e-mail]'}, {id:5,name:'Wim',phone:'99999999',email:'[e-mail]'}, {id:6,name:'Marc',phone:'33333333',email:'[e-mail]'}, {id:7,name:'Dan',phone:'44444444',email:'[e-mail]'} ];
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

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

为了达到这个目的，一旦我们找到一个匹配项，我们就会寻找相同初始匹配项的匹配项，并将其推入同一组，以便我们可以拥有最大数量的数据进行匹配。

结果是，一旦我们得到了第一组的第一个元素，我们就会找到并推入第三个元素，从那里开始匹配第二个元素就容易多了。逻辑稍微复杂一些，我想性能也会更差一些。

- Akrion

---

我期望这些都在同一组中：{id:1,name:'John',phone:'1',email:'a'}, {id:2,name:'Marc',phone:'2',email:'b'}{id:3,name:'Ron', phone:'1',email:'b'}，但似乎漏掉了其中的2。 - Mark

由于注释部分的奇怪格式，我第一次没有理解它，但你是正确的。我更新了另一个版本，与预期相匹配。谢谢。 - Akrion

匹配代码似乎要迭代所有值。这是浪费的，因为在正确的字段上，映射可以以O(1)的时间复杂度报告匹配项。您的代码很简短（我没有检查其正确性），但不能达到最优。 - tucuxi

为了获得分组的正确性，您必须在获得初始匹配后进行扫描。我并不是说它完美无缺，但它相当通用，肯定可以进一步优化。 - Akrion

Answer 4

一种实现你所需的方法是将联系人分成不同的组。每个组都包含一个名为names、phones和emails的列表。

然后遍历联系人，查看当前联系人是否属于任何一个组。如果不属于任何一个组，则创建一个新组，并设置其names/phones/emails，以便下一个联系人可能属于同一组。

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

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.log(output);   //[ [1,3,5] , [2,6,7] , [4] ]

- Ahmad

---

O(n^2*log(n))？我认为OP正在寻找最优解。 - joyBlanks

log(n) 部分没问题，但是二次方 n^2 的乘法会在更大的数据集上引起问题。然而，我自己没有更好的解决方案。 - Han

根据原始问题，只有一个元素的组不应该包含在结果中。[4] 不应该出现在结果中。 - Akrion