Most efficient way to map one fileID to another

Question

I am in the process of localizing a game. I have roughly 1% of the game assets (around 200 of 20k files) that need to be replaced per language with different assets, 1 to 1. I am mulling over the 'best' way to do this in a very RAM starved envirnoment. Here's my current list of ideas:

• Hash off the file IDs to convert at nearly constant time 1 to another. Advantage is speed. Disadvantage is this can be memory hungry and is not as memory efficient as other methods.

• Enter each file ID to be translated into a map. Log time lookups, but perhaps more memory efficient? I'm not as experienced with this as other solutions so I cannot say how well this will work.

• Enter each file ID as a pair into a vector, sort the vector when done, and bsearch off it. Log time lookups and perhaps more efficicent than the map?

• On any step, add a bit boolean table of kIsThisAssetTranslated[] on the front end to constant time bail early if the assets is unchanged.

Just looking for some experience and opinions on which methods (or something I've missed) the community would consider. I'm leaning towards the hash as this will be called per file access, but as always, the question of Ram vs performance is an interesting one.

Answer 1

Depends on how much RAM you have. A hashtable with 200 to 20k entries doesn't really take up much memory (by desktop PC standards). If you have to determine at runtime if a file is translated or not, then why not just create a map which contains all the files which are translated, and create subdirectories for all available languages. And then after doing the lookup, just load it from the locale directory (e.g. en-US) or add a prefix/suffix to the filename.

Answer 2

You can pre-calculate the FileIDs that you need to convert. Look up perfect hashes; this may be what you need. However, 2log(200) is only 8. The overhead of hashing is significant, even more so for perfect hashing.

And remember that files are slow - 8 memory accesses for a binary search will take perhaps a microsecond, not even flash is that fast.