5
\$\begingroup\$

I'm writing a function that receives an array and returns an object with the count of unique values, pretty much like other questions here or in StackExchange. Except that in my case, this array may contain a nested array, like:

var array = [1, 2, 'a', 'b', [3, 'c', 1], 'd', 2, 'b'];

Here is my code:

function findUniques(array, occurrences) {
    if (!occurrences) {
        occurrences = {};
    }

    //checking if parameter passed is an array
    if (Array.isArray(array)) {
        for (let i = 0; i < array.length; i++) {
            //if item is a nested array, call findUniques again
            if (Array.isArray(array[i])) {
                occurrences = findUniques(array[i], occurrences);
            } else {
                //add to/update count in occurrences object
                occurrences[array[i]] = occurrences[array[i]] + 1 || 1;
            }
        }
    }

    return occurrences;
}

It's returning the following object, as it was supposed to:

{ 
    '1': 2, 
    '2': 2, 
    '3': 1, 
    a: 1, 
    b: 2, 
    c: 1, 
    d: 1 
}

My worry is that I'm using recursion.

Is it possible to optimize this function?

(Bear in mind that I must only use vanilla JavaScript)

\$\endgroup\$
  • 1
    \$\begingroup\$ Just noting that the input array you have above does not generate the output object you have below. \$\endgroup\$ – cbojar Sep 7 '15 at 20:54
  • \$\begingroup\$ I didn't notice. Just fixed :) \$\endgroup\$ – gfnogueira Sep 8 '15 at 15:09
4
\$\begingroup\$

When we use recursion, we are building an algorithm based on an implicit1 stack, the function call stack. We are pushing and popping elements, essentially every time we recurse down and back up. If we make the stack explicit in our code, we can make the method iterative instead, and skip the recursive calls.

A pseudocode version of the algorithm would look like:

function findOccurences(array):
    ensure array is actually an array

    set occurrences to empty object

    create a stack
    push all elements in array onto the stack
    while the stack is not empty:
        if pop returns an array:
            push all of the elements in the popped array onto the stack
            continue while

        process the popped element

    return occurrences

A nice feature in Javascript arrays is that they have stack semantics2, so we can just use a built in array as our stack. We can actually get a little more clever than that, though. Since we are putting every element from one array into our stack, which is also an array, we could just as effectively clone the original array and use that as our stack3. We can then just translate the pseudocode into Javascript.

function findOccurrences(array) {
    if(!Array.isArray(array)) {
        return {};
    }

    var occurrences = {};

    // JS arrays don't have a native clone method so
    // Array#slice with a start point of 0 creates
    // a copy of our array. If handling in the same
    // order is important, tack a .reverse() at the
    // end.
    var stack = array.slice(0);

    while(stack.length !== 0) {
        var nextElement = stack.pop();
        if(Array.isArray(nextElement)) {
            // We use some fanciness here so we don't have
            // to write out an explicit loop
            [].push.apply(stack, nextElement);
            continue;
        }

        occurrences[nextElement] = occurrences[nextElement] + 1 || 1;
    }

    return occurrences;
}

1 Implicit to our algorithm, explicit to our runtime.

2 Array#push, Array#pop

3 We could just use the original array, but since it is passed by reference, we are going to corrupt the array in the process and that could lead to unwanted side effects.

\$\endgroup\$
  • \$\begingroup\$ I really like the way you explained it all. But as @ErikR mentioned in the other answer, it will create a new copy of the array. Won't it affect performance on large arrays just like in the other answer? \$\endgroup\$ – gfnogueira Sep 8 '15 at 15:01
  • 1
    \$\begingroup\$ @gfnogueira It does create a new copy of the array, which might affect performance. To know for sure, someone would have to profile the code to compare. If the array copy becomes a bottleneck, this can be adapted. If we don't care about preserving the original array, we can just use it directly as a stack. If we need to preserve it, but don't want to copy it, we can make the code much more complicated by only using the stack on elements that are arrays. That would look ugly and confusing, but would use less memory. \$\endgroup\$ – cbojar Sep 8 '15 at 15:20
1
\$\begingroup\$

This may or may not result in faster code, but you can avoid checking that occurrences is defined as well as avoid returning it by writing the code this way:

function findOccurrences(array) {
    var occurrences = {};
    findOccurrences0(array, occurrences)
    return occurrences
}

function findOccurrences0(array, occurrences) {
    var len = array.length;
    for (var i = 0; i < array.length; i++) {
        if (Array.isArray(array[i])) {
            findOccurences0(array[i], occurrences);
        } else {
          ...
        }
    }
}

Note that findOccurrences0 always assumes that occurrences is defined, and it doesn't have to return it since all invocations modify the same object.

\$\endgroup\$
1
\$\begingroup\$

First of all, I would correct that data if possible. If it's "a list of items", then it should be "a list of items", and not a list of mixed data. Unpredictable data structures is one of the nightmares that causes apps to break. Developers tend to work around them instead of solving the root problem, because writing code that works around the issue is faster than updating the logic the creates it... and deadlines.

Anyways, if you're just counting occurrences, you could just flatten out the array, and start counting. Flattening it out first would mean you have a 1D array to play with, easier to comprehend at first read than having to step through the code.

function findOcurrences(array){
  // flatten out the array
  var flat = array.reduce(function(carry, item){
    // This allows us to append either a value or an array without fuss
    return carry.concat(item);
  }, []);
  
  // count the ocurrences
  return flat.reduce(function(carry, item){
    carry[item] = (carry[item] || 0) + 1;
    return carry;
  }, {});
}

var array = [1, 2, 'a', 'b', [3, 'c', 1], 'd', 2, 'b'];

var occurrences = findOcurrences(array);

// SE should seriously have a console printer instead of an HTML results view
document.write(JSON.stringify(occurrences));

\$\endgroup\$
  • 2
    \$\begingroup\$ Correct me if I'm wrong, but flattening will create a whole new copy of the array(even if the array has no nested sub-arrays), and this will affect performance when used on large arrays. A recursive solution only requires O(d) space where d is the maximum number of nested arrays. \$\endgroup\$ – ErikR Sep 8 '15 at 1:03
  • 1
    \$\begingroup\$ @ErikR Yup. That's true. But the OP never specifically said optimize for performance, and I'm optimizing for conciseness. Fast code is worthless if you start to use bandaids 2 weeks from now. \$\endgroup\$ – Joseph Sep 8 '15 at 2:04
  • \$\begingroup\$ @JosephtheDreamer my mistake, I should've mentioned it was to optimize for performance. But your idea to flatten the array gave me ideas to refactor other projects that I'm working on. \$\endgroup\$ – gfnogueira Sep 8 '15 at 14:56

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.