What is the most optimal way to check if something in an array exists?

Question

the project I'm creating involves having an array being searched through a bunch of times, I realize that if I don't do this the most optimal way possible I might see server performance issues.

I was wondering what is the least server intensive way to find a value in an array, your help would be appreciated.

I've seen some people answer this on this website but there's mixed answers, some people say a basic for loop is best and other say indexOf and findIndex would perform better but not sure which is best or if there's a different option.

Search complexity comparing `array` and `set` is O(N) vs O(1). — Johnny, Oct 02 '19 at 14:38
Server perf is not related. Javascript array search will be anyway executed on client side. And @VLAZ, I dont think Set exist in javascipt... — Camille, Oct 02 '19 at 14:38
@Camille You should tell that to the [MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set) then ;) And there's node, i.e. server-side JS. — , Oct 02 '19 at 14:40
@Camille [it does since ES6](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set) — VLAZ, Oct 02 '19 at 14:41
Can you add things to sets similar to pushing things in an array? I forgot to mention that the array is dynamic and won't always have the same values if that's relevant — Buckets, Oct 02 '19 at 14:45
For searching on list of object, a simple array with primary key as index and object as value is really fast. I didn't experiment Set in JS yet, but `has` on object but be slower than `indexOf` on a integer/string — Camille, Oct 02 '19 at 15:04
Or not... [Javascript Set vs Array](https://stackoverflow.com/questions/39007637/javascript-set-vs-array-performance) — Camille, Oct 02 '19 at 15:22

Yousaf · Answer 1 · 2019-10-02T14:46:23.997

1

Time complexity of searching in an array of length n is O(n) whereas using a Map will give you time complexity of O(1) because you don't need to iterate over a Map to know if particular element exists in it. You can get the element by using its key.

If elements exists, it will be returned in O(1) time, otherwise you will get undefined meaning element you searched for doesn't exists in the Map

So its better to use Map instead of an array in your case.

edited Oct 02 '19 at 14:46

answered Oct 02 '19 at 14:44

Yousaf

27,861
6
44
69

I'd say use a Set - there is no real benefit to a Map, if you don't have a key-value relationship and an array mostly doesn't. Unless indexes are important but it's a bit doubtful for just searching). – VLAZ Oct 02 '19 at 14:46
2

@VLAZ But if they are objects that I put into a set, it wouldn't work though right? When I tested it, it seemed that the .has method in sets would return false if I asked for the same object in the set but Im not sure – Buckets Oct 02 '19 at 14:58
@Buckets Depends on what you're searching for. If it's an *object*, then you need the original reference but that's also the case with `Array#indexOf` and `Array#includes`. Since you mentioned those, I assumed that you are either searching for primitives or for an existing object. If you need to do searching by parameter, that is not reflected in your question. – VLAZ Oct 02 '19 at 15:00
@Buckets that's why i suggested to use a `Map` instead of a `Set`. In `Map`, you can provide a unique `key` when adding an object in a `Map`. When you need to search for any object, just use its `key` – Yousaf Oct 02 '19 at 15:05

score 0 · Answer 2 · answered Oct 02 '19 at 14:58

0

Even the most optimal search through a list would have a runtime complexity of O(n). A basic for loop would be the fastest since you could make it terminate at the first occurrence. Things get slightly more interesting when you're searching for objects.

function arrayHasObj(obj, list) {
  var i = list.length;
  while (i--) {
    if (JSON.stringify(list[i]) === JSON.stringify(obj)) {
      return true;
    }

    return false;
  };
}

Here the while loop is obviously O(n), but we also need to account for the serialization of an object to JSON. This falls out of any standard time-complexity analysis. If anyone can weigh on this please do.

Generally optimizing a search through a single array isn't necessary. There is some larger optimization that need to happen in your algorithm, or if you're truly using a large dataset you should use be querying from a database.

EDIT: Obviously a dictionary/set has its merits. The OP is specifically asking about arrays.

answered Oct 02 '19 at 14:58

Joseph Cho

4,033
4
26
33

"*Even the most optimal search through a list would have a runtime complexity of O(n)*"??? a sorted list can easily be binary searched in `O(log(n))`. If you maintain a lookup table with a hash a hash structure, then your search would be `O(1)` with a good hashing algorithm and bucketing. – VLAZ Oct 02 '19 at 15:02
We can't assume the list is sorted, it was never specified. Sorting a list with your standard quicksort would add a runtime of `O(n * log(n))`. – Joseph Cho Oct 02 '19 at 15:03
And now you're making an assumption - the list might be already sorted or static. If it's not changing, then doing `O(n*log(n))` once to speed up many lookups is negligible. I'm contesting the assertion that *any* search is `O(n)`. Sure, it adds assumptions, but it takes assumptions to claim otherwise, too. – VLAZ Oct 02 '19 at 15:05
@VLAZ if you're going to nitpick, please educate me and weigh in on the runtime complexity of `JSON.stringify` instead of trying to walk me through algorithims 201. – Joseph Cho Oct 02 '19 at 15:09
Sorry if I didn't add enough context, I have a grid of about 6000 squares I suppose you can say with a player that can move around through it, I'm trying to make it so while the player is moving square to square it checks if there's something in the square that blocks it from moving there, like collision. Obviously I don't want to loop through all 6000 squares to check if something is in one of the squares each time so I was trying to figure out a more optimal way of checking the square the player is in @VLAZ – Buckets Oct 02 '19 at 15:17
1

It would be implementation dependant but *slow* as it requires parsing. Also, it is unreliable - `JSON.stringify({a:1, b:2}) === JSON.stringify({b:2, a:1})` might or might not work depending on the platform with odds being good that it doesn't work. `JSON.stringify({a:1, b:2}) === JSON.stringify({a:1, b: 2})` has a higher chance of success but it's still platform dependent. The problem is that JS didn't support consistent ordering of keys [until ES6](https://stackoverflow.com/questions/30076219/does-es6-introduce-a-well-defined-order-of-enumeration-for-object-properties) and that's not – VLAZ Oct 02 '19 at 15:18
1

implemented on every platform. Even if it *is* you can fall into a trap: `JSON.stringify({a: 1, 1: true}) === JSON.stringify(1: true, a: 1)` on compliant platfoms, since numeric keys would be put in front. Then you also have a problem with being limited to JSON serialisable content - functions and (non-basic) objects would have a different representation, `undefined` is not present in JSON and Symbol keys are not supported. So, it's not a perfect solution. – VLAZ Oct 02 '19 at 15:18

What is the most optimal way to check if something in an array exists?

2 Answers2