CODEWITHSUNDEEP
arraysdata-structuresmaps
Lencalot
Lencalot

Reputation: 395

How many items need to be stored before a Map become more efficient than an array

I feel this question should have probably been answered somewhere but I haven't been able to find it. I'm working on some legacy code(first job) and I've come across a point where a map is being used to store exactly 23 variables(and from my understanding of the code this number never changes). Fundamentally I understand access time for a map is O(1) but I've always heard there is some overhead when dealing with maps.

So my question is at what point does it become more efficient to use a map, and not just have an array that stores these 23 values. I guess essentially I would be creating my own map in the code, where whenever I need to store xValue, I just access the array where I know xValue is being stored.

Is the overhead for a map so small that I'm overthinking this? I figure the readability of the code might be a bit easier for the map, since the key being used is essentially a description of what the xValue is.

Upvotes: 0

Views: 188

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 134085

Using a map (or dictionary) is unlikely to be faster than direct array access. That is, if you know that you have exactly N items and you know what those items are, you can create an array and constants that say where in the array each item is. For example (pseudocode):

const NumItems = 22
const ItemType1 = 0
const ItemType2 = 1
const ItemType3 = 2
...
const ItemType22 = 21

Array myItems[22]

Then, if you want to access the value for item type 15, it's simply myItems[ItemType15].

The drawback to this approach is that you must have storage space for one of every possible item. So if you have 20,000 items instead of just 23, you would have to allocate your array to hold all 20,000 possible items. And create constants to define where each item type would be stored.

A map lets you save space, but at some memory cost. The per-item overhead can be two or three times the per-item cost of an array. But if you have a huge number of possible items but you're only going to have a few dozen at a time, then the map is more memory efficient. Say you're going to have 30 items out of 20,000 possible. A full array would cost you storage for 20,000 items. The map would cost you storage for, perhaps 90 items (three times the cost of a 30-item array).

The point here is that a map trades speed for storage space. The map can store a subset of the entire universe of items more efficiently than an array can, but it takes more time to access an individual item.

So the issue really isn't "which is faster," but rather if the space savings afforded by a map is worth the extra processing time. In your case, where you have exactly one each of a small number of items, there is no advantage to using a map.

Upvotes: 1

Related Questions