CODEWITHSUNDEEP
javascript
sonicboom
sonicboom

Reputation: 5028

Inverting a binary array?

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 ];

Upvotes: 1

Views: 416

Answers (6)

Joe
Joe

Reputation: 47619

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).

Upvotes: 0

epascarello
epascarello

Reputation: 207521

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);

Upvotes: 2

thefourtheye
thefourtheye

Reputation: 239493

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

Upvotes: 3

T.J. Crowder
T.J. Crowder

Reputation: 1074495

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).

Upvotes: 3

Irvin Dominin
Irvin Dominin

Reputation: 30993

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

Demo: http://jsfiddle.net/IrvinDominin/Kw3e6/

Upvotes: 0

adeneo
adeneo

Reputation: 318232

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; })

FIDDLE

Upvotes: 2

Related Questions