DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

Cover image for What data structure is best for caching? An experiment ๐Ÿงช
eitanwaxman
eitanwaxman

Posted on

What data structure is best for caching? An experiment ๐Ÿงช

While trying to broaden my horizons about data structures, I learned about two native JavaScript structures I had never heard of - Sets and Maps.

Now why had I never heard of them? Is it because I am a complete noob? Or maybe they are just not so common? (my nice way of saying useless).

To figure it out I decided to run a small experiment to test the build and retrieval times for each of the big 4 - Arrays, Objects, Sets, and Maps.

Here's what I did:

  1. First I tested Arrays- constructing it with a for loop and retrieving using the indexOf method (for a worst case scenario item).
const myArray = []

function storeWithArray(array, itemToFind) {
    const startTime = Date.now()

    for (let i = 0; i < 10000000; i++) {
        array.push(i)
    }

    const buildTime = Date.now()
    console.log("Array Build Time: ", buildTime - startTime)

    console.log(array.indexOf(itemToFind) === itemToFind)

    const retrievalTime = Date.now()
    console.log("Array Retrieval Time: ", retrievalTime - buildTime)
}

Enter fullscreen mode Exit fullscreen mode

Then I used the array I built to test the other three structures:

Sets

function storeWithSet(array, itemToFind) {
    const startTime = Date.now()

    const mySet = new Set();

    array.forEach((item) => {
        mySet.add(item)
    })

    const buildTime = Date.now()
    console.log("Set Build Time: ", buildTime - startTime)

    console.log(mySet.has(itemToFind))

    const retrievalTime = Date.now()
    console.log("Set Retrieval Time: ", retrievalTime - buildTime)
}
Enter fullscreen mode Exit fullscreen mode

Objects

function storeWithObject(array, itemToFind) {
    const startTime = Date.now()

    const myObject = new Object();

    array.forEach((item) => {
        myObject[item] = item;
    })
    const buildTime = Date.now()
    console.log("Object Build Time: ", buildTime - startTime)

    console.log(myObject[itemToFind] === itemToFind)

    const retrievalTime = Date.now()
    console.log("Object Retrieval Time: ", retrievalTime - buildTime)
}
Enter fullscreen mode Exit fullscreen mode

Maps

function storeWithMap(array, itemToFind) {
    const startTime = Date.now()

    const myMap = new Map();

    array.forEach((item) => {
        myMap.set(item, item)
    })
    const buildTime = Date.now()
    console.log("Map Build Time: ", buildTime - startTime)

    console.log(myMap.get(itemToFind) === itemToFind)

    const retrievalTime = Date.now()
    console.log("Map Retrieval Time: ", retrievalTime - buildTime)
}
Enter fullscreen mode Exit fullscreen mode

And run time:

storeWithArray(myArray, 9999999)
storeWithSet(myArray, 9999999)
storeWithObject(myArray, 9999999)
storeWithMap(myArray, 9999999)
Enter fullscreen mode Exit fullscreen mode

Here are the results:
results of experiment

Unsurprisingly Array retrieval time was the longest, but the build time was much shorter than Sets and Maps!

Objects seem to be the clear winner with the shortest build time and marginally longer retrieval time than Maps and Sets (sometimes it even beat them).

So basically if you need to store and retrieve information - objects are your best bet.

Then what are Maps and Sets good for?
I know they poses unique qualities - they are ordered like Arrays and can prevent duplicate values etc. But what is the use case that warrants their apparent inefficiency?

Top comments (0)

Timeless DEV post...

How to write a kickass README

Arguably the single most important piece of documentation for any open source project is the README. A good README not only informs people what the project does and who it is for but also how they use and contribute to it.

If you write a README without sufficient explanation of what your project does or how people can use it then it pretty much defeats the purpose of being open source as other developers are less likely to engage with or contribute towards it.