What is the most efficient way to invert an arbitrary length binary array? I.e. set 1 = 0 and 0 = 1 for all 0, 1 in the array.
var arr1 = [ 0, 0, 1, 1, 1, 0, ..., 1 ];
-
3you should have tried something...post that...Adil Shaikh– Adil Shaikh2014-03-28 14:53:21 +00:00Commented Mar 28, 2014 at 14:53
-
I wanted to see if there was anything more than efficient than a trivial for loop, no point posting a trivial for loop.sonicboom– sonicboom2014-03-29 16:51:13 +00:00Commented Mar 29, 2014 at 16:51
Add a comment
|
6 Answers
Using a binary operation should be faster than any other approach.
var arr1 = [ 0, 0, 1, 1, 1, 0, 1 ];
for (var i = 0; i < arr1.length; i += 1) {
arr1[i] ^= 1;
}
console.log(arr1);
# [ 1, 1, 0, 0, 0, 1, 0 ]
We use Binary XOR with 2. It works because
console.log(1 ^ 1); // 0
console.log(0 ^ 1); // 1
7 Comments
Joe
There's a HUGE amount of activity for this very trivial question. It's exciting to watch.
T.J. Crowder
Interestingly, it's pretty much a dead heat across the board, this approach and the conditional: jsperf.com/various-binary-inversions There's maybe the slightest advantage in XOR plus caching the length. Maybe. Not that it remotely matters. :-)
thefourtheye
@T.J.Crowder Interesting, I think chrome does the bitwise operations very efficiently. Because I see only Chrome responds well to the XOR.
T.J. Crowder
@thefourtheye: Yeah, if the starting value is an integer. Chrome is fairly aggressive about keeping numbers integers if it can without violating the semantics, and of course, if the numbers are already integers it makes bitwise ops nice and fast.
thefourtheye
@T.J.Crowder Thank you for the fiddle and the in-depth knowledge. I learn a lot from you :)
|
In general, "efficiency" questions in JavaScript are a pitfall, because different engines are more efficient with different things. Optimizing before there's a problem to solve is almost always a waste of time (regardless of language/environment), but this is particularly true when your optimization targets (JavaScript engines) vary markedly in their performance profiles.
In general, subject to that caveat, I don't think you'll find anything more efficient than a simple for loop where you cache the length.
var arr1 = [ 0, 0, 1, 1, 1, 0, ..., 1 ];
var n, l;
for (n = 0, l = arr1.length; n < l; ++n) {
arr1[n] = arr1[n] === 0 ? 1 : 0;
}
But again, solve performance issues when you run into performance issues, and then solve them by testing in your target environments (either within your app, or with tools like http://jsperf.com).
Comments
Just map the array and return 1 for 0 and 0 for anything else
var arr2 = arr1.map(function(x) { return x === 0 ? 1 : 0; })
4 Comments
Joe
More efficient than a for-loop? Not that it likely matters.
OnlyThenDidIReckonMyCurse
@Joe It depends on whether you want runtime efficiency or programmer efficiency.
Joe
I think it's fairly clear that the question is about run-time efficiency. And I would argue it would take more time to write and think about this one. Again, not that it likely matters.
Joe
To follow this up, it looks like the map performs very well in my browser. Not quite sure why, but the results were surprising. Perhaps there's some parallelisation going on or special optimisations.
This is very inefficient, but a fun way to attack the problem.
var arr1 = [ 0, 0, 1, 1, 1, 0, 1 ];
var swapped = JSON.parse(JSON.stringify(arr1).replace(/[01]/g, function(x){ return x==0?1:0;}));
- Converts array to string
- String Replace match with regular expression, replace character to opposite
- Converts the new string back to an array
Written as multiple lines:
var arr1 = [ 0, 0, 1, 1, 1, 0, 1 ];
var arrayString = JSON.stringify(arr1);
var flip1and0 = arrayString.replace(/[01]/g, function(x){ return x==0?1:0;});
var swappedArray = JSON.parse(flip1and0);
3 Comments
Joe
If you're going to process arrays of under 1000 elements less than once a second, I bet this is just as efficient as the other answers.
T.J. Crowder
@Joe: No, it won't be as efficient (far from it), it just probably won't matter that it's dramatically less efficient.
Joe
From 1,000 ft I don't think it'll make a difference to the operation of the page/app. We're saying the same thing,
You can try with a for loop.
Code:
var arr1 = [0, 0, 1, 1, 1, 0, 1];
for (var i = 0; i < arr1.length; i++) {
arr1[i] = 1 - arr1[i]
}
At the moment binary operation win: http://jsperf.com/test-foor-loop
Comments
Since this seems to have turned into a contest, what about using Typed Arrays?
// Construct an array of length 1024
var length = 1024;
var arr = [];
for (var i = 0; i < length; i++) {
arr.push(Math.random() > 0.5 ? 1 : 0);
}
var typedLoop = function() {
var typed = new Uint8Array(arr);
for (var i = 0; i < typed.length; i++) {
typed[i] = (typed[i] == 0 ? 1 : 0);
}
return arr;
}
var untypedLoop = function() {
for (var i = 0; i < arr.length; i++) {
arr[i] = (arr[i] == 0 ? 1 : 0);
}
return arr;
}
var withClosure = function() {
return arr.map(function(x) { return x === 0 ? 1 : 0; });
}
// A time-elapsed function with a lot of repetitions
var reps = 10000;
var time = function(f) {
var before = new Date().getTime();
for(var i = 0; i < reps; i++) {
f();
}
console.log(new Date().getTime() - before);
}
Some results:
time(typedLoop)
212
time(untypedLoop)
6169
time(withClosure)
601
I think that's really interesting. Using a typed array is the shortest. Using a closure with normal array takes 3x as long. Using the for loop is 30x. On my machine, now, with this release of this browser at this ambient temperature and the wind blowing northerly.
Using elapsed time isn't a very good measure at all but it's a practical indication.
Obviously this doesn't matter at all. You probably won't be calculating thousand-long arrays tens of thousands of times. Go with the clearest code. But it does answer your question about the 'most efficient' (which isn't always the best).
