оптимальный алгоритм группировки данных в javascript - PullRequest
0 голосов
/ 20 ноября 2018

Следующий (упрощенный) тип данных 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 (необязательно в lodash, но основная идея - прояснить алгоритм) в соответствии со следующим ограничением: контакт принадлежит к группе, когда любой из следующих критериев одинаков: имя, телефон или адрес электронной почты.Результаты показывают, что идентификатор сгруппирован как массивы в массивах.контакт в группе из 1 игнорируется.

В приведенном выше примере это означает, что контакты с идентификаторами 1,3,5 принадлежат друг другу, поскольку 1,3 используют один и тот же адрес электронной почты, а 3 и 5 - один и тот же номер телефона.,Аналогично 2,6,7: 2 и 6 имеют одинаковые имена, а 6 и 7 имеют одинаковые адреса электронной почты.5 не имеет ничего общего.Следовательно, ожидаемый результат:
[[1,3,5], [2,6,7]]

Справочная информация. Одно из решений, которое работает, - это перебирать каждый элемент и проверять оставшуюся часть списка, если имя, адрес электронной почты или телефон совпадают.Если это так, сгруппируйте их и удалите из списка (в примере мы сравниваем 1 со всеми элементами в списке, и только 3 найдено).проблема заключается в том, что следующие элементы также должны быть проверены снова для этих групп, потому что в этом случае 5 еще не обнаружен как часть группы.Это делает алгоритм сложным, хотя я подозреваю, что есть простой способ решить это за линейное время.Там также может быть название для этого класса проблем?`

Ответы [ 4 ]

0 голосов
/ 21 ноября 2018

Любой ответ, который повторяется по каждой из 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-where, а затем, наконец, перемещаем все идентификаторы записей в их последнюю группу. Все это может быть сделано в O(m), с m количество групп; с дополнительным O(n) при фактическом копировании идентификаторов записей в объединенные группы: в целом, мы все еще находимся на O(n) территории.

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

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]]
0 голосов
/ 20 ноября 2018

Идея:

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

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

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)
0 голосов
/ 21 ноября 2018

Вот еще одно предложение маршрута, по которому вы могли бы пойти.Идея состоит в том, чтобы использовать один 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:'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, у которого 2-й элемент не соответствует первому, но соответствует 3-му, который фактически соответствует 1-му... так что все они должны быть хитами.

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

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

0 голосов
/ 20 ноября 2018

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

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

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