Variable list... List or Array?
BlitzMax Forums/BlitzMax Programming/Variable list... List or Array?
| ||
| I have designed what should be a simple and hopefully working "variables" system, which stores information on objects in a simple, flexible way. The system works something like this: "Variables" contain two separate variables: A key and a value. The key is an integer which gives the variable a unique identifier (I opted against Strings for the sake of speed), while the value is what that key "points to". To achieve this, there is a single command: AddVariable. This command takes two arguments: A Key variable, and a Value variable. The Key variable is actually a pointer to a Global variable, while the Value is a string/pointer/int. Of course, as is obvious, that method of storing variable keys as integers has a problem: How can the developer or the program keep track of this? Normally, would have to be all manually declared as constants when the program starts. The keys would all need to be manually given different values, etc. This would not be in any way enjoyable and would not work well for an Extension system, for example. To solve this, the AddVariable function is rather a magical function. As I said, the key argument is a pointer to a Global variable. What this function does is it gives that Key a unique identifier automatically. If that key already has an identifier, it can be assumed that a variable with this key already exists for something else so the key is left as-is. (This is built for having multiple Variable lists for different objects, I should add; the idea is mainly so that Extensions can have their own settings that any other code can access in as quiet a way as possible. For example, to create a file loader, you may have a "Variable" which stores what kind of file that Extension will load under a FileType key). Okay, so that's all sorted... my question! I have a choice here: Store Variables in a List (which has many methods and things that I probably won't use), or in an Array. I would need to resize the Array continually via that Slices stuff, whereas the List could just be added to endlessly. Recalling Keys from the array would be easy (just set whatever index to the value; the keys already act perfectly as array indexes), while recalling them from the List would be a bit slower (it looks like I would have to use Search, which goes through every link until it finds one). Naturally, they seem to both have their strengths and weaknesses. Which do you think is more suited to this? What kind of performance hit is there with using Arrays and Slicing them compared to using Lists and Searching them? |
| ||
| I skipped some, but since you're using a Key/Value system, wouldn't TMaps be more appropriate? Anyway, in a straight fight between arrays and lists, I believe the rule of thumb is that arrays are much faster if you're not constantly resizing them, and lists are faster if you are. |
| ||
| Thanks for telling me about Maps, Gabriel! This page helped explain them rather nicely: http://blitzwiki.org/index.php/Map I guess they do sort of do what I want and it doesn't look like I actually have to use Strings anywhere (that should be pointed out in the article...), but they won't do that magical transformation of empty Globals into working keys so I'll still need to write my own code for that (which is a good thing, because otherwise it will feel like I've achieved nothing!). Anyhow, compared to Arrays and Lists, Maps definitely look more suited for this. |
| ||
| I'd use a hash table. It offers the best of all worlds. For instance, it has constant time lookup like an array (where a TMap will have O(log n) lookup time) and you can use a string as the key. They grow as needed and so in this regard behave like a list (this is the only time they're 'slow', as they need to allocate new memory and rehash all of the entries. This can be avoided by selecting an appropriate initial size, and an appropriate growth factor.) Some implementations of them will also allow you to store multiple entries per key, should you so desire. In fact, I've got a hash table module I've been working on. It's mighty fast and can store either a single object per key, or multiple objects per key. The only functionality I don't have fully implemented is automatic resizing (although you can manually call the grow function...adding automatic resizing should be quite simple, too.) The hashtable that I've been working on stores objects, so you can store basically anything in the table. All you have to do is cast it back to the proper type when you get it back from the hash table. If you want to store integers/floats/doubles etc, you can wrap them in an object and then store that (unfortunately you can't store them directly - although you could easily modify the code to make it hold a specific type of variable.) Basically the code would look like this
'initial size of 25
Hashtable:THashtable = THashtable.constructor( 25 )
'strings are treated as objects in BMax, and so can be
'inserted directly into the table
Hashtable.insertEntry( "TestKey", "TestValue" )
'cast the result back to a string and print it
print( string(Hashtable.getEntry( "TestKey") ) 'prints "Testvalue"
'you can also insert other types into the table. You can even store a hash table in a hashtable
secondhashtable:THashtable = THashtable.constructor( 5 )
secondhashtable.insertentry( "2ndTestIndex", "2ndTestValue" )
hashtable.insertentry( "Hashtable" , secondhashtable )
'now we'll retrieve the second hash table from the first
'hash table, and get & print the value for the key "2ndTestIndex"
local returnedhash:THashtable
'we've got to always cast the result because the table returns a plain ol' object
returnedhash = THashtable( hashtable.getentry( "Hashtable" ))
print( returnedhash.getentry( "2ndTestIndex" ) '<---prints "2ndTestvalue"
If you're interested let me know. I can send the code your way (it's fairly well documented, too). |
   |