1
\$\begingroup\$

I need to organize the following objects in a array applying the following rules:

  • Group all object by source
  • In each group order them by order property
  • Rewrite each order property keeping their order starting from 0

I have drafted an initial solution below, the final result is present in the code comment and the script does its job.

But I would like to have your code review specially in term of performance, as the real world array could contain hundreds of objects.

Please note a new array is created for this example, as I do not need to change the original array in place.

   var data = [
          {
              id: 'g',
              order: '0',
              source: '3-j'
          },
          {
              id: 'c',
              order: '40',
              source: '1-x'
          },
          {
              id: 'd',
              order: '0',
              source: '2-y'
          },
          {
              id: 'b',
              order: '30',
              source: '1-x'
          },
          {
              id: 'e',
              order: '1',
              source: '2-y'
          },
          {
              id: 'h',
              order: '1',
              source: '3-j'
          },
          {
              id: 'a',
              order: '20',
              source: '1-x'
          },
          {
              id: 'f',
              order: '2',
              source: '2-y'
          }
        ];
        var flags = {};
        data.forEach(function (item) {
            flags[item.source] = true;
        });
        var sources = [];
        Object.keys(flags).forEach(function (flag) {
            sources.push(flag);
        });
        sources.sort();
        var newData = [];
        sources.forEach(function (source) {
            var dataFiltered = data.filter(function (item) {
                return item.source === source;
            });
            dataFiltered.sort(function (a, b) {
                return a.order - b.order;
            });
            dataFiltered.map(function (item, index) {
                item.order = index;
            });
            newData = newData.concat(dataFiltered);
        });
        console.log(JSON.stringify(newData));

    /*
       Final result:
        [
            {
                "id": "a",
                "order": 0,
                "source": "1-x"
            },
            {
                "id": "b",
                "order": 1,
                "source": "1-x"
            },
            {
                "id": "c",
                "order": 2,
                "source": "1-x"
            },
            {
                "id": "d",
                "order": 0,
                "source": "2-y"
            },
            {
                "id": "e",
                "order": 1,
                "source": "2-y"
            },
            {
                "id": "f",
                "order": 2,
                "source": "2-y"
            },
            {
                "id": "g",
                "order": 0,
                "source": "3-j"
            },
            {
                "id": "h",
                "order": 1,
                "source": "3-j"
            }
        ]
    */

\$\endgroup\$
2
\$\begingroup\$

I think this could be greatly simplified, as you are currently iterating through the input data many more times than is necessary.

There are a number of possible approaches you could take to optimize this. One option might be to simplify this down to one call to Array.sort() to apply multi-level sorting, followed by iterating the array to reset order values.

// sort data
data.sort(
    (a, b) => {
        if (a.source < b.source) return -1;
        if (a.source > b.source) return 1;
        if (a.order < b.order) return -1;
        if (a.order > b.order) return 1;
        return 0;
    }
);

// iterate data, applying new order value
var currentGroup = null;
var counter = 0;
for (var i = 0, len = data.length; i < len; i++) {
    if (currentGroup !== data[i].source) {
        counter = 0;
        currentGroup = data[i].source;
    } else {
        counter++;
    }
    data[i].order = counter;
}

The sort here would be \$O(n log(n))\$ on average or \$O(n^2)\$ worst case (based on underlying quicksort implementation for sort()). And the mapping on new count values would execute in \$O(n)\$. So, you would have \$O(n^2 + n)\$ worst case complexity.

Memory utilization is also probably close to optimal for this approach, as you are modifying data in place for both the sort and the re-writing of order values.

If you wanted to consider alternate output data structures such as the following, where you use index position in array as "order" rather than having to apply an order value on the item, you might be able to improve performance.

{
    "source1": [
        {"id": "somevalue"},
        {"id": "someothervalue"},
        ...
    ],
    "source2": [
        ...
    ],
    ...
}

Some partially-implemented code for this approach might look like:

var output = {};
for(var i = 0, len = data.length; i < len; i++) {
    var el = data[i];
    var group = el.source;
    var insert = { 'id': el.id };
    if(group in output) {
        // perform sorted insert into array at group
        sortedInsert(output[group], insert);
    } else {
        output[group] = [ insert ];
    }
}

Note I say "partially" implemented based on my not having implemented the mechanism for sorted insert into group array. You can certainly search online for an optimized approach for performing a sorted insert into an array which might use insertion sort, quicksort, heapsort, or some combination of those depending on expected array sizes.

This approach has you iterating the input data array only a single time, but with each pass you would be performing an increasingly complex insert which could range from \$O(1)\$ to \$O(n log(n))\$ (if appropriate sorting logic is used).

This could lead to worst case \$O(n^2 log(n))\$ operation. This my sound bad but consider that if you had X groups in your data set each of roughly similar size such that typical group size m = n / X that average case could actually could improve significantly:

\$O(n * m log(m)) \rightarrow O(n * (\frac{n}{X}) log (\frac{n}{x}))\$

For "worst case" example list of 1000 items in single group:

\$O(1000 * 1000 * log(1000)) \rightarrow O(3000000)\$

vs. better example of 1000 items in 10 equal groups:

\$O(1000 * 100 * log(100)) \rightarrow O(200000)\$

vs. first example of sort + mapping, again with 1000 items (number of groups doesn't matter):

\$O(1000^2 + 1000) \rightarrow O(1001000)\$

With the second approach, if you needed to, you could then "flatten" the data structure to get to your desired output, an operation that would cost an additional \$O(n)\$. If would be \$O(201000)\$ if we extended the 1000 items in 10 equal groups example.

You can see that the value of n that you expect for your use cases and how items are distributed amongst groups may become important to understanding which approach might be optimal for your application.

This leads to the most important point of this whole post, which is that if you are truly trying to optimize performance, you may need to potentially attempt several different implementations and then actually test them against your expected typical and "worst case" data sets to understand what sort of performance you might actually expect from this piece of code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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