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

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

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

Wrap the words around to fit a rectangle with a specific ratio, rather than a specific size

Locate the next element with the same class using jQuery across the entire document

Error 500 on Firebase: Issue solving "firebase" in "firebase.js" not resolved

The PHP echo function is unable to properly display the values when comparing two arrays

Angular variable resets to initial value after modification

Changing date and time into milliseconds within AngularJS

Breaking up an array in PHP according to search outcomes

Tips on creating a transition in React to showcase fresh HTML content depending on the recent state changes

AngularJS - retrieving and displaying the selected value from an HTML dropdown menu

Saving functions in the localStorage API of HTML5: A step-by-step guide

Make a POST request using Express API, supporting both JSON and XML data

Calculating variables in JavaScript

Creating Transparent Rounded Backgrounds in Google Chrome Packaged Apps: Achieving the same look as Google Hangout app

Using setAttribute will convert the attribute name to lowercase

Ways to clear TextField status

Error encountered when accessing Spotify API. The requested action requires proper permissions which are currently missing. Issue arises when attempting to

JavaScript - Retrieve the name of an object from a separate array

Node scripts and node bins are causing errors in Vue.js when running npm

Setting the default selected row to the first row in ag-Grid (Angular)

Looking for assistance in setting up a personalized slideshow to automatically play on its