current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 down vote favorite

During work, I was given this task: to group elements with similar properties in the array.

In general, the problem is as follows:

var list = [
    {name: "1", lastname: "foo1", age: "16"},
    {name: "2", lastname: "foo", age: "13"},
    {name: "3", lastname: "foo1", age: "11"},
    {name: "4", lastname: "foo", age: "11"},
    {name: "5", lastname: "foo1", age: "16"},
    {name: "6", lastname: "foo", age: "16"},
    {name: "7", lastname: "foo1", age: "13"},
    {name: "8", lastname: "foo1", age: "16"},
    {name: "9", lastname: "foo", age: "13"},
    {name: "0", lastname: "foo", age: "16"}
];

If I group this elements by lastname and age, I will get this result: 

var result = [
    [
        {name: "1", lastname: "foo1", age: "16"},
        {name: "5", lastname: "foo1", age: "16"}, 
        {name: "8", lastname: "foo1", age: "16"}
    ],
    [
        {name: "2", lastname: "foo", age: "13"},
        {name: "9", lastname: "foo", age: "13"}
    ],
    [
        {name: "3", lastname: "foo1", age: "11"}
    ],
    [
        {name: "4", lastname: "foo", age: "11"}
    ],
    [
        {name: "6", lastname: "foo", age: "16"},
        {name: "0", lastname: "foo", age: "16"}
    ],
    [
        {name: "7", lastname: "foo1", age: "13"}
    ]         
];

After some experimentation, I came to the following solution:

    Array.prototype.groupByProperties = function(properties){
        var arr = this;
        var groups = [];
        for(var i = 0, len = arr.length; i<len; i+=1){
            var obj = arr[i];
            if(groups.length == 0){
                groups.push([obj]);
            }
            else{
                var equalGroup = false;
                for(var a = 0, glen = groups.length; a<glen;a+=1){
                    var group = groups[a];
                    var equal = true;
                    var firstElement = group[0];
                    properties.forEach(function(property){

                        if(firstElement[property] !== obj[property]){
                            equal = false;
                        }

                    });
                    if(equal){
                        equalGroup = group;
                    }
                }
                if(equalGroup){
                    equalGroup.push(obj);
                }
                else {
                    groups.push([obj]);
                }
            }
        }
        return groups;
    };

This solution works, but is this a right and best way? It still looks a little ugly to me.

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

I felt compelled to write that you probably should combine forEach and map with the answer of Alexey Lebedev. 

function groupBy( array , f )
{
  var groups = {};
  array.forEach( function( o )
  {
    var group = JSON.stringify( f(o) );
    groups[group] = groups[group] || [];
    groups[group].push( o );  
  });
  return Object.keys(groups).map( function( group )
  {
    return groups[group]; 
  })
}

var result = groupBy(list, function(item)
{
  return [item.lastname, item.age];
});
share|improve this answer
    
'groups[group] = groups[group] || [];' - NICE and CLEAN!! –  Saike Dec 11 '13 at 14:22
add comment
up vote 5 down vote

I find the functional aspect of JavaScript to be a big advantage. When it comes to looping, Array.prototype.forEach and cousins can help your code be more descriptive:

Array.prototype.defineProperty('groupByProperties', {
    value : function(properties){                       
        // will contain grouped items
        var result = []; 

        // iterate over each item in the original array
        this.forEach(function(item){
            // check if the item belongs in an already created group
            var added = result.some(function(group){
                // check if the item belongs in this group
                var shouldAdd = properties.every(function(prop){
                    return (group[0][prop] === item[prop]);
                });
                // add item to this group if it belongs 
                if (shouldAdd) {
                    group.push(item);
                }
                // exit the loop when an item is added, continue if not
                return shouldAdd;
            });

            // no matching group was found, so a new group needs to be created for this item
            if (!added) {
                result.push([item]);
            }
        });
        return result;
    }
});

While i don't consider it a best practice to add custom functionality to predefined objects (Array.prototype in this case), i left that part of your solution in. However, I added groupByProperties as a non-enumerable property of Array.prototype so it doesn't appear in for..in enumerations.

share|improve this answer
    
Great! But some tests shows that forEach method much slower than for loop with predefined length. You disagree? =) –  Saike Dec 10 '13 at 13:03
    
Indeed, forEach may be about 5 times slower than a for loop. It's still pretty fast and I for one am a fan of writing clearly and optimizing the bottlenecks if needed. –  Tibos Dec 10 '13 at 13:38
    
The same issue is with creating a local variable that stores the length of the array you're looping over. It is probably a lot faster to access local variable than array.length, but when you're iterating that is not the bottleneck, so a loop with saved variable is about as fast as a regular loop with array.length. (The exception to that rule is when length is not a static property, but computed on the fly, like in a live NodeList). –  Tibos Dec 10 '13 at 14:10
    
Nonetheless.. Your example much more beautiful and elegant. Thank u for answer! –  Saike Dec 10 '13 at 16:09
add comment
up vote 3 down vote

The main problem with your function is quadratic time complexity in the worst case. Also, if we first implement a general groupBy function, grouping by properties becomes trivial.

function arrayFromObject(obj) {
    var arr = [];
    for (var i in obj) {
        arr.push(obj[i]);
    }
    return arr;
}

function groupBy(list, fn) {
    var groups = {};
    for (var i = 0; i < list.length; i++) {
        var group = JSON.stringify(fn(list[i]));
        if (group in groups) {
            groups[group].push(list[i]);
        } else {
            groups[group] = [list[i]];
        }
    }
    return arrayFromObject(groups);
}

var result = groupBy(list, function(item) {
    return [item.lastname, item.age];
});

You might want to add hasOwnProperty check into arrayFromObject, if your coding convention doesn't forbid extending object prototype.

share|improve this answer
    
Привет украине! =) Ща затестим твой вариант. –  Saike Dec 11 '13 at 10:27
    
Perhaps you should consider passing a serialization function to your groupBy method. With toString there are several problems: item1 = { lastName : [1,2], age : 3 } and item2 = { lastName : 1, age : [2,3] } and item3 = { lastName : '1,2', age : 3 } will all be put in the same group in your example. –  Tibos Dec 11 '13 at 10:40
    
Tibos: you're right, that's a bug waiting to happen. I've changed toString() to JSON.stringify(). The speed is comparable, assuming that JSON is implemented natively. –  Alexey Lebedev Dec 11 '13 at 12:16
    
Using the stringify as the key is brilliant, +1 –  konijn Dec 11 '13 at 13:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.