Comparing the efficiency of using arrays versus mapping to an object and accessing data in JavaScript

Question

Comparing the efficiency of using arrays versus mapping to an object and accessing data in JavaScript

When considering the basics of computer science, it is understood that searching an unsorted list typically occurs in O(n) time, while direct access to an element in an array happens in O(1) time for HashMaps.

So, which approach yields better performance: mapping an array to a dictionary and accessing elements directly, or simply using includes()? This question pertains specifically to JavaScript, as the answer likely hinges on how includes() and {} are implemented at their core.

let y = [1,2,3,4,5]
y.includes(3)

or...

let y = {
          1: true,
          2: true
          3: true
          4: true
          5: true
        }
5 in y

javascript arrays json performance dictionary

Answer 1

Answer №1

It is indeed true that object lookup operates in constant time - O(1) - making the use of object properties instead of an array a viable option. However, when you simply need to determine if a value exists within a collection, employing a Set would be more suitable. A Set is a generally unordered group of values that can also be searched in linear time. Opting for a plain object would necessitate having values alongside keys, which may not be relevant. Therefore, opting for a Set is recommended.

const set = new Set(['foo', 'bar']);
console.log(set.has('foo'));
console.log(set.has('baz'));

This approach proves beneficial when multiple values need to be checked within the same Set. Nevertheless, adding elements to the Set (similar to adding properties to an object) entails an operation of O(N). Hence, if you only require a single value lookup once, there is no advantage to utilizing either this method or the object technique. In such scenarios, resorting to using an array and the includes method would suffice.

Answer 2

It is indeed true that object lookup operates in constant time - O(1) - making the use of object properties instead of an array a viable option. However, when you simply need to determine if a value exists within a collection, employing a Set would be more suitable. A Set is a generally unordered group of values that can also be searched in linear time. Opting for a plain object would necessitate having values alongside keys, which may not be relevant. Therefore, opting for a Set is recommended.

const set = new Set(['foo', 'bar']);
console.log(set.has('foo'));
console.log(set.has('baz'));

This approach proves beneficial when multiple values need to be checked within the same Set. Nevertheless, adding elements to the Set (similar to adding properties to an object) entails an operation of O(N). Hence, if you only require a single value lookup once, there is no advantage to utilizing either this method or the object technique. In such scenarios, resorting to using an array and the includes method would suffice.

Answer 3

Answer №2

Updated 04/29/2020

The recent analysis pointed out that V8 may be optimizing the array includes calls. In order to achieve more expected results, it is suggested to assign to a variable and use it. The updated version shows Object address as the fastest, followed by Set has, with Array includes trailing in performance (based on my system/browser).

While I still maintain my original point about testing assumptions when making micro-optimizations, it is important to ensure the validity of your tests ;)

Original

Despite the common expectation that Object address and Set has would have better performance than Array includes, benchmarks against Chrome show otherwise.

In my tests with Chrome, Array includes significantly outperformed the other methods.

Local testing with Node yielded more anticipated results where Object address performed the best, Set has came close behind, and Array includes was slightly slower than both.

The key takeaway here is that if you are considering micro-optimizations, it is advisable to benchmark instead of assuming what might work best for your specific scenario. Ultimately, implementation plays a crucial role, as indicated by your question. Therefore, optimizing for the target platform is essential.

Here are the results obtained:

Node (12.6.0):

ops for Object address 7804199
ops for Array includes 5200197
ops for Set has 7178483

Chrome (75.0):

https://i.sstatic.net/PRLv6.png

Answer 4

Updated 04/29/2020

The recent analysis pointed out that V8 may be optimizing the array includes calls. In order to achieve more expected results, it is suggested to assign to a variable and use it. The updated version shows Object address as the fastest, followed by Set has, with Array includes trailing in performance (based on my system/browser).

While I still maintain my original point about testing assumptions when making micro-optimizations, it is important to ensure the validity of your tests ;)

Original

Despite the common expectation that Object address and Set has would have better performance than Array includes, benchmarks against Chrome show otherwise.

In my tests with Chrome, Array includes significantly outperformed the other methods.

Local testing with Node yielded more anticipated results where Object address performed the best, Set has came close behind, and Array includes was slightly slower than both.

The key takeaway here is that if you are considering micro-optimizations, it is advisable to benchmark instead of assuming what might work best for your specific scenario. Ultimately, implementation plays a crucial role, as indicated by your question. Therefore, optimizing for the target platform is essential.

Here are the results obtained:

Node (12.6.0):

ops for Object address 7804199
ops for Array includes 5200197
ops for Set has 7178483

Chrome (75.0):

https://i.sstatic.net/PRLv6.png

Answer 5

Answer №3

Although not a direct answer to the query, I conducted a related performance test using my Chrome dev tools.

function getRandomInt(max) {
    return Math.floor(Math.random() * max);
}
var arr = [1,2,3];
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var x = arr.includes(getRandomInt(3));
}
console.log(performance.now() - t);
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var n = getRandomInt(3);
    var x = n == 1 || n == 2 || n == 3;
}
console.log(performance.now() - t);
VM44:9 9.100000001490116
VM44:16 5.699999995529652

The array includes syntax appealed to me aesthetically, prompting me to assess its impact on performance when used to check if a variable matches one of several enums. Surprisingly, with a short list, like [1,2,3], there seems to be minimal impact on performance. To verify this, I ran another test.

function getRandomInt(max) {
    return Math.floor(Math.random() * max);
}
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var x = [1,2,3].includes(getRandomInt(3));
}
console.log(performance.now() - t);

var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var n = getRandomInt(3);
    var x = n == 1 || n == 2 || n == 3;
}
console.log(performance.now() - t);
VM83:8 12.600000001490116
VM83:15 4.399999998509884

Interestingly, I found that the method I preferred and actually utilized had a significant impact on performance compared to the initial test, especially when executed multiple times. Therefore, incorporating it within an Array.filter in scenarios like a React Redux selector might not be advisable as initially intended.

Answer 6

Although not a direct answer to the query, I conducted a related performance test using my Chrome dev tools.

function getRandomInt(max) {
    return Math.floor(Math.random() * max);
}
var arr = [1,2,3];
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var x = arr.includes(getRandomInt(3));
}
console.log(performance.now() - t);
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var n = getRandomInt(3);
    var x = n == 1 || n == 2 || n == 3;
}
console.log(performance.now() - t);
VM44:9 9.100000001490116
VM44:16 5.699999995529652

The array includes syntax appealed to me aesthetically, prompting me to assess its impact on performance when used to check if a variable matches one of several enums. Surprisingly, with a short list, like [1,2,3], there seems to be minimal impact on performance. To verify this, I ran another test.

function getRandomInt(max) {
    return Math.floor(Math.random() * max);
}
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var x = [1,2,3].includes(getRandomInt(3));
}
console.log(performance.now() - t);

var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var n = getRandomInt(3);
    var x = n == 1 || n == 2 || n == 3;
}
console.log(performance.now() - t);
VM83:8 12.600000001490116
VM83:15 4.399999998509884

Interestingly, I found that the method I preferred and actually utilized had a significant impact on performance compared to the initial test, especially when executed multiple times. Therefore, incorporating it within an Array.filter in scenarios like a React Redux selector might not be advisable as initially intended.

Comparing the efficiency of using arrays versus mapping to an object and accessing data in JavaScript

Answer №1

Answer №2

Answer №3

Similar questions

Steps to successfully set up a React application without encountering any installation errors

Click on the link to see the jQuery effect in action

What could be causing the code to not wait for the listener to finish its execution?

What are the steps to transform an object containing arrays into strings and then embed them into my HTML code?

PHP struggles to parse a JSON array

What is the best way to ensure that the buttons remain in place once they have been clicked to reveal a drop-down menu?

Is there a way to efficiently update specific child components when receiving data from websockets, without having to update each child individually?

Localhost file not refreshing

What is the process for combining three 2D arrays and showcasing the outcome as an image?

Incorporating AngularJS and Bootstrap for seamless pagination experience

strange occurrences while handling double pointer variables

Troubleshooting node modules for browser compatibility

generate a list based on the data inside an array of objects

Setting up a connection between an Express server and a Mongoose database in

What is the best way to display a loading image and temporarily disable a button for 3 seconds before initiating the process of sending post data from another page via

The `toString` function is displaying an array instead of the expected string

When the button is clicked, the image vanishes into thin

display the values of the array object within the ajax success callback

Determination of Array Size using Powershell

Techniques for transferring JavaScript variables within a URL using AJAX