4

What can be the most efficient way to find an item in an array, which is logical and understood by a web developer?

I came across this piece of code: 

var inArray = function(a, b, c, d) {
    for (c in b) d |= b[c] === a;
    return !!d
};

It works fine. Can someone please explain me the code?
I also came across an exact same question that might make mine as a duplicate. But my real question lies in explanation of the above code and why bitwise operator has been used into it.
Also, can there be a way without any for loop, or iteration to get index of an item in an Array?

Community
  • 1
  • 1
Om Shankar
  • 7,989
  • 4
  • 34
  • 54

4 Answers4

5
var inArray = function(a, b, c, d) {
    for (c in b) d |= b[c] === a;
    return !!d
};

That is some terrible code, and you should run away from it. Bitwise operators are completely unnecessary here, and c and d being parameters makes no sense at all (as Raymond Chen pointed out, the author of the code likely did it to safe space of declaring local variables -- the problem though is that if true is passed in for d the code is suddenly broken, and the extra parameters destroys any sense of understanding that glancing at the declaration would provide).

I'll explain the code, but first, here's a better option:

function inArray(arr, obj) {
    for (var i = 0; i < arr.length; ++i) {
        if (arr[i] === obj) {
            return true;
        }
    }
    return false;
}

Note that this is dependent on the array being an actual array. You could use a for (k in arr) type loop to generalize it to all objects.

Anyway, on to the explanation:

for (c in b) d |= b[c] === a;

This means that for every key in b (stored in c), we will check if b[c] === a. In other words, we're doing a linear scan over the array and checking each element against a.

d |= val is a bitwise or. The bits that are high in val will be set high in d. This is easier to illustrate in languages where bits are more exposed than in JS, but a simple illustration of it:

10011011
01000001
--------
11011011

It's just OR'ing each individual bit with the same location bit in the other value.

The reason it's an abuse here is that it convolutes the code and it depends on weird implicit casts.

x === y returns a boolean. A boolean being used in a bitwise expression makes little sense. What's happening though is that the boolean is being converted to a non-zero value (probably 1).

Similarly, undefined is what d will be. This means that d will be cast to 0 for the bitwise stuff.

0 | 0 = 0, but 0 | 1 = 1. So basically it's a glorified:

for (c in b) d = (d || (b[c] === a));

As for !!x that is just used to cast something to a bool. !x will take x, implicitly cast it to a bool and then negate it. The extra ! will then negate that again. Thus, it's likely implicitly casting to a bool (!!x being true implies that x is at least loosely true (1, "string", etc), and !!x implies that x is at least loosely false (0, "", etc).

This answer offers a few more options. Note though that all of them are meant to fallback to the native indexOf that will almost certainly be faster than anything we can code in script-land.

Community
  • 1
  • 1
Corbin
  • 33,060
  • 6
  • 68
  • 78
  • c and d being declared as parameters is a lazy way of declaring them as local variables with the added risk that if somebody calls with four parameters, the initial value of d will be wrong! – Raymond Chen Dec 30 '12 at 19:23
  • @RaymondChen Ah, I suppose that it why it was done. The author of that terrible little snippet was apparently determined to make it stupidly compact :). Never even occurred to me that they did it to save a few characters. – Corbin Dec 30 '12 at 19:24
2

This code is pretty poorly written, and barely readable. I wouldn't qualify it as "awesome"...

Here's a rewritten version, hopefully more readable:

function inArray (aElt, aArray) {
  var key;
  var ret = false;
  for (key in aArray)
    ret = ret || (aArray[key] === aElt);
  return ret;
}

The for loop seems like the most natural way to do that. You could do it recursively but that doesn't feel like the easiest approach here.

Jonathan Protzenko
  • 1,709
  • 8
  • 13
  • 2
    That can be rewritten to be significantly more efficient in cases where the element exists in the array and is not the last element. Just return true when the element is found, otherwise, return false at the bottom of the function. That way the for loop short circuits when the element is found. – Corbin Dec 30 '12 at 19:09
  • This isn't true. `x = 1; x |= 2; x; // 3`. `|=` is a binary OR [assignment operator](https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Operators/Assignment_Operators), not a logical OR. – Paul S. Dec 30 '12 at 19:09
  • @PaulS.: Yes, but `===` can only evaluate to true or false, which map to 1 and 0 as numbers. For that limited range of values, `|` and `||` are effectively identical (except for short-circuit evaluation). – Ilmari Karonen Dec 30 '12 at 19:17
  • The code that I had put was a one-liner `var inArray = function(a,b,c,d){for(c in b)d|=b[c]===a;return!!d };` modified to look good by some mod just now. It being one-liner made me look at it as awesome may be – Om Shankar Dec 30 '12 at 19:30
  • Sure, I was just trying to rewrite this in a more readable fashion. More efficient ways include exiting from the loop when the element is found, or simply relying on the built-in `indexOf` function. – Jonathan Protzenko Dec 30 '12 at 19:30
  • @OmShankar Just wait until you spend 3 hours debugging something only to find out that it's a bug in someone's one line mess. Then you'll love one liners. You'll 'love' them with a passion. – Corbin Dec 30 '12 at 19:43
  • @Corbin, true that :). Sorry for putting it that way – Om Shankar Dec 30 '12 at 19:47
  • @PaulS. The `d|= b[c] === a` is bothering me. Per your info, `2 | 0; // 2` and `2 | 1; // 3`. Even though the right hand side resolves to 1, Ilmari seems right. Only when the left side is also `0` or `1`, the equation seems useful – Om Shankar Dec 30 '12 at 19:51
  • @OmShankar it is a binary or. Let's write the numbers in binary using 2 bits, `0` is `00`, `1` is `01`, `2` is `10` and `3` is `11`. Now, wirting in binary, `10 | 01` is `11` which is `3` in dec. `x | x` and `x | 0` will always be `x`. The reason the output is only ever `0` or `1` is because `false` gets converted to `0` and `true` to `1`. In my earlier comment I was just pointing out that it isn't a logical or but a binary one. – Paul S. Dec 30 '12 at 19:57
2

What can be the most efficient way to find an item in an array, which is logical and understood by a web developer?

Either the native method, haystack.indexOf(needle) !== -1 or a looped method which returns as soon as it can

function inArray(needle, haystack) {
    var i = haystack.length;
    while (i) if (haystack[--i] === needle) return true;
    return false;
};
Paul S.
  • 64,864
  • 9
  • 122
  • 138
  • That's a very `C` style while loop. A for loop would be a lot more readable, though that is of course just opinion. – Corbin Dec 30 '12 at 19:20
  • @Corbin I don't think I've ever written in C. I just know `while` is _very fast_ and `n !== 0 == true` – Paul S. Dec 30 '12 at 19:27
  • A `for` loop is essentially a `while` loop. Computers have no concept of a `for` loop (or even a while loop). A similarly constructed for loop, or even `while (i > 0)` is going to have identical performance (or perhaps so little difference that it is truly negligible by any comparison). I'm just being picky (and obnoxiously opinionated) though :-). Either way, +1. – Corbin Dec 30 '12 at 19:31
  • Computers don't have the concept, but compilers will usually optimise/compile `while` differently to `for` so you can sometimes squeeze a tiny bit more if you choose a `while`. You are right though, the difference is minimal. The question asks for the **most efficient** way and this should be it (that it matches my preference is just a coincidence). – Paul S. Dec 30 '12 at 20:02
  • @PaulS. In that case, bitwise operators are even more fast. so the one-liner that created this doubt could be the fastest. I also wanted a **logical, understood by a web-developer** Solution. Reason being, there are Web Devs like me who don't have a Computer Science background :) – Om Shankar Dec 30 '12 at 20:13
  • Thanks all for your answer, my confusing **bits** got clear. I think I should dive immediately in eloquentjavascript.net – Om Shankar Dec 30 '12 at 20:17
  • @OmShankar if you don't understand any part of the two examples in my answer please ask. There are two problems with the bitwise method in question; 1 is that the loop doesn't terminate as soon as the final `ret` is known and the second bitwise is not always the fastest choice in JavaScript because all variables are actually structures internally. – Paul S. Dec 30 '12 at 20:19
  • @PaulS. I actually wouldn't be surprised if `for` is often optimized better than `while`. `for` is effectively a constrained `while` loop after all. Though really I'd be surprised if any modern compiler doesn't optimize them essentially the same. We're splitting hairs though since at that low of level it's not going to matter anyway. If a few cycles actually matters, JS is the wrong language to begin with :). – Corbin Dec 30 '12 at 20:20
  • @Corbin, true that again. May be this thing can be checked with jsperf.com. Coming back to answer, Paul - I understood your answer. +1. But I needed an explanation for the `|= true/false` thing. Since an **answer** which explains this is Corbin's I am accepting that. Thanks all – Om Shankar Dec 30 '12 at 20:24
2

You asked for a recursive version

var inArray = function(arr, needle, index) {
    index = index || 0;
    if (index >= arr.length)
        return false;
    return arr[index] === needle
         ? true
         : inArray(arr, needle, index + 1);
}

console.log(inArray([1,5,9], 9));
goat
  • 31,486
  • 7
  • 73
  • 96