Is there a memory size difference between these two?
Item[] itemDB = new Item[10000];
itemDB[9283] = new Item("Health Potion", 992);
and
Item[] itemDB = new Item[10000];
itemDB[9283] = new Item("Health Potion", 992);
itemDB[8233] = new Item("Mana Potion", 436);
itemDB[5487] = new Item("Rage Potion", 122);
itemDB[1235] = new Item("Bloodhorn", 10);
And if there is a size difference, how big is it?
Does each empty entry take the exact same space as a full one or just 8 bits to save the null address?
These examples are simplified.
I have an item database of 115.000 items and their IDs range from 25 to 170.000.
I want to establish wether or not it would be smart to access them via this array[id] method, so i won’t have to iterate through the whole list to search for an id.
The items would also have not two attributes (as in the example) but more like 30.
Assuming Item is a class, then second example takes up more space for the Item objects you are allocating (the array only contains references to them), but both take the same amount of space for the array itself (somewhere on the order of 80 KB).
If you have a “sparse” array where only a few of the indexes have real values assigned to them, it’s often a good idea to use a Dictionary instead.
Mh that would be 0.5mb wasted with the real database. That would be manageable.
A dictionary? You mean like an auto-generated array that translates an id to its corresponding index?
I don’t think that this would be good in my main case. In the example case, sure, but maybe not in my main case.
I would go from having a single 175000 array to an 175000(dictionary) and an additional 115000(itemDB) array, which would in total take up even more memory. I can not loop through these when accessing an item. It would certainly cause a lag.
A Dictionary is a data structure for a collection of data with unique keys, where the keys are not necessarily numbers or consecutive. Under the covers it is implemented using a hash table, which is highly efficient for sparse data. The amount of memory it requires scales with the number of things you actually put in it, not the size of your indexes. It does take more space per item than a fully-utilized array, but it takes far less memory than a mostly-empty array.
If Item is a class, the array will always have the size of n*8Byte as it is just an array of pointers. Each object pointed to might be anywhere else on the heap. Iterating over the pointers is going to be fast, as they are continuos in memory but anything beyond null checks is likely going to cause a cache-miss as the prefetcher likely didn’t cache the memory that was pointed to.
If Item is a struct, the entire array is going to be of size n*StructSize and everything you didn’t write to is initialized as default(Item). Iterating over it will be blazingly fast as everything can be prefetcher (except for pointers in the struct).
With the amount of data you have, you should question what problem your trying to solve and what the most common and time critical actions are going to be. If you’ll iterate seldomly, e.g. for setup and saving, but will have lookups of singular items everywhere, a dictionary gets you fast lookups, but slow and costly iteration.
Also, why would you leave that much empty space in there? If it is about using the index as a “key” then maybe it’s better to have a list with key value structs and then you can iterate over these and check against the key, if iteration over all of it is more common than lookups.