1

Can this be optimized

var groups = [];
for (var a in aList) {
  for (var bNumber in bList) {
    groups.push({ a: a, b: b });
  }
}

The code is actually fine, but I just realized that it looks like a cross product of two lists, so instead of looping aList.length*bList.length times, I wondered if there was some smart function to do this.

Mark Amery
  • 143,130
  • 81
  • 406
  • 459
Jamgreen
  • 10,329
  • 29
  • 113
  • 224

1 Answers1

1

Julian pointed out a mistake in my original answer where I was storing elements as opposed to indices.

The existing code is erroneous; there is no variable b. I will assume bNumber was meant to be b (or the other way around; it doesn't matter).

Since you know that arrays are indexed 0...n (I am assuming you declared the arrays in a way such that all indices in that range exist), you certainly shouldn't use a for...in loop (as mentioned in this comment); rather, you should explicitly code in the bounds in a standard for loop (or some nearly identical variant):

var groups = [];

for (var a = 0; a < aList.length; a++){
  for (var b = 0; b < bList.length; b++){
    groups.push({a, b});
  }
}

You shouldn't generally be using var either; you generally want to restrict the scope of your variables to directly within the block in which you are working, and you want to be able to make some variables unassignable.

const groups = [];

for (let a = 0; a < aList.length; a++){
  for (let b = 0; b < bList.length; b++){
    groups.push({a, b});
  }
}

With those changes, this has runtime of around 11% of the code in the answer, with the error fixed.

Original answer, assuming storing elements

First, since you know that you are dealing with lists, you should not use a for...in loop (as mentioned in this comment). Next, this operation is generally called the Cartesian product or direct product, not the cross product.

The existing code is erroneous; there is no variable b. I will assume bNumber was meant to be b (or the other way around; it doesn't matter).

The code can then be rewritten as

var groups = aList.flatMap(a => bList.map(b => ({a, b})))

(Although you shouldn't generally be using var either! You generally want to restrict the scope of your variables to directly within the block in which you are working.)

You will almost always find that the code in the question (with the error fixed) performs better, though, because Array maps have to handle some additional logic costs, like orchestrating the callbacks and list concatenation. Switching your for...in loops to for...of loops actually halves the runtime in my tests.

Avi Mehra
  • 148
  • 1
  • 7
  • If you think people shouldn't use `var`, then just don't use it in the first place and demonstrate with `const` or `let` instead. (As an aside, I disagree that it shouldn't be used, but that's a different discussion.) – Julian Feb 21 '21 at 16:11
  • By "doubles the performance", did you mean "doubles the running time" or "halves the running time"? (Otherwise a good answer, I'll upvote.) – Julian Feb 21 '21 at 16:12
  • 1
    Actually, I just noticed a mistake in your answer. The original code made pairs of *indices* into `aList` and `bList`. Your code makes pairs of *elements* of those arrays instead. – Julian Feb 21 '21 at 16:24
  • You're absolutely correct; I have updated the answer to reflect that. – Avi Mehra Feb 22 '21 at 17:53