Optimization on list handling

For a mobile device, I would ask 'Do you really need those 10k items in memory at all times?' Assuming each item holds 10MB of data, that's 100MB you're burning just for that list. I believe first-gen iPads have 256MB of memory which you have to share with the OS and all other apps running. Oh and your models, and your graphics, and your sounds...you get the picture. Even if the size isn't an issue, say each item is 500KB, I'd still be hesitant to have a list of 10k items on a mobile app unless it is truly necessary.

Regarding the parallel list question, it depends on how you have it setup. Take this C# example:

 List<Object> listA = new List()<Object>;
 List<Object> listB = new List()<Object>;    
 Object a = new Object();
 listA.Add(a);
 listB.Add(b);

There is a small memory overhead, but both lists are pointing to the same location in memory so it's rather minor. However if you do this:

 List<Object> listA = new List()<Object>;
 List<Object> listB = new List()<Object>;    
 Object a = new Object();
 listA.Add(a);
 a = new Object();
 listB.Add(b);

Then you're using 2x the memory because you have multiple copies of the object.

For managing that many items on a mobile app, my first approach would be to identify the truly core items, the ones that must be available instantly at all times. I would then load those into a static list. Then I would create groups of lists based on where I am in the game, and dynamically load those as needed. No need to have the shop keeper's inventory loaded if I'm down in the dungeon and can't shop.

Class to struct? Shouldn't have any impact from a memory perspective. I would actually recommend against this as in C# structs are passed by value instead of by reference, which in a mobile app could be a major problem.

Hope this helps.

Some rough envelope calulations: suppose your custom type is 3 ints and a float. That's about 16 bytes, so 160,000 bytes ~0.16M for a size 10,000 array. Yes, structs use less memory. A struct is part of the array. A class is created where-ever, and the actual array has a 4-byte pointer to each item -- goes to ~0.2M total space. The larger the custom class is, the less you notice the extra 4 bytes.

If you use a linked list, you have to pay for a pair (I believe) of extra 4-byte previous/next pointers: a linked list costs you per item: 16 + 4*2(next/prev) + 4(pointer to item) = 28. Almost double the space for an array, but, again, the extra 12ish bytes don't matter as much as your custom datatype gets bigger. Of course, if you do a lot of mid insert/delete, you pretty much need the linkedList for speed.

"...a list of integers with just the indexes of the main list?"

Yes. The absolute most memory efficient way to create a sublist would be to create an array of ushorts as indexes. An unsigned short is only 2 bytes and counts 0 to 65,000. If you used structs for the main type, you pretty much need to store indexes. If the custom datatype is a class, the automatic reference to it costs you only 4 bytes anyway, and might be easier to use. But, if you can't put an upper bound on the sublist size, the arrays need to be size 10K.

Say you have 6 sublists and preallocate a size 10K array for each. That's 6arrays 10K 2bytes= 0.12M for all sublists. Say the sublists tend to be about 2000 long and you used linked lists. That's 6lists 2Klong 12bytesSize = 0.144M. About the same either way, and about doubles the total space you need. As your custom data type gets larger (12 ints and a string,) the size of the sublists is a smaller and smaller proportion and it isn't worth getting cute to save space on them.

The best improvements are then in the custom data type -- tricks like using uchar for ints you know only go from 0 to 255; or storing 12.39 as 1239 in a 2-byte short, if you know you only need 2-digits precision and never go above 320.00.