Random Access Types
Blitz3D Forums/Blitz3D Programming/Random Access Types
| ||
| The Object/Handle commands can be very powerful since they allow random access to types. Types can be useful since they use only the memory necessary for each field per type, whereas arrays or will pad out the memory allocation regardless of whether any data has actually been written. In a particular scenario, however, I found that I had a large number of instances with a certain field that I wanted to check for equivalents/duplicates. With a LOT of instances,. it was apparent that iterating through was way too slow. One simple solution might usually be to allocate the Handles of these instances into an array cross-referenced with the field value I was looking for - however, with massive (10^5 + ) variance in the number of possible instances, it would be unwise and maybe even not realistically feasible to iterate through the array lists, since this could still be just as slow as iterating through the type instances. Well, I had a great idea! I was able to utilise the EntityName and FindChild power of Blitz3D to result in INCREDIBLY fast "labelling" of my instances by creating pivots with references in their names. The ability of B3D to "instantly" (you know what I mean) retrieve an entity by the Name in this fashion allows for a much more versatile random access of objects such as type instances, where the list is too long or too varied to be iterated through. The essentials of the method is included below, however - I would much prefer this to be possible in BlitzPlus, but I'm not aware of any techniques that can instantly retrieve objects and related objects in the way that FindChild() does with 3D entities The reason why my instances do not suit iterating, is because I am using them to store pixel data for images (therefore potentially millions of pixels) yet I also wanted to limit the number of types by not repeating, say, those with identical RGB (which is a field within the type) The fact that images can have pretty much any combination of RGB values makes identifying where duplications arise difficult - too many possibilities for storing these ,and too many gaps in between to try iterating through. I hope this is all explanatory enough and if anyone has any suggestions, I'd really love to hear them! |
| ||
| I would much prefer this to be possible in BlitzPlus, but I'm not aware of any techniques that can instantly retrieve objects and related objects in the way that FindChild() does with 3D entities ? BlitzPlus doesn't have 3D entities...? (Unless you count the little bOGL engine, which does support an GetChildByName.) I don't actually understand what you're doing, but here are some general observations: 1) The best way to attach extra data to an existing entity or other object is generally not to try to pack an extension object into whatever you currently have, because usually it wasn't designed for that; better is to make the new type the base type and give it an "ent" field. Instead of extracting extension data from entities, design your engine's API to handle this new extension type as its base type for all extended-entity operations (bonus: this doesn't require you to use Handle at any point). 2) Don't try to combine entity-unique data and shared data in the same object; instead, factor all shared data out into a second sub-object type (the same as entities are a sub-object of the new base type), and give the shared objects an explicit refcount; "copy" operations increment, only creating a new instance if the data changes, and "free" operations decrement and only deleting the instance if the refcount hits zero. 3) (an extension of point 1) Don't be afraid for your API functions to take strongly-typed objects as their main argument (e.g. 'Function DoSomething(this.ExtendedEnt, ...'). Using int handles as your primary way of controlling objects has no real benefits once you get used to it not looking like B3D's core functions. 4) ....because I really don't understand what you're doing, this may be off-base, but in general I don't see how you can ever check existing instances for duplication without iterating over a whole collection, unless you take care that duplicates are simply never created. You have to compare to the existing set somehow! 5) Consider fully-automatic or semi-automatic memory management (i.e. GCs) if it's keeping track of your allocated objects that is causing problems for you. There's a reason all future BRL languages use GC. 6) It's possible to use a global array as a substitute for Object/Handle in some circumstances (the array gives O(1) access to objects via int and the object gives O(1) access to int if you manually store its fake-handle in a field; Object and Handle give O(log N) access as I think they use a std::map internally), if you don't mind the memory cost. Remember you can shrink arrays again and re-allocate slots for freed objects, which is good because you never run out of indices, but bad if you rely on checking whether an int ever returns Null (Object/Handle will never reallocate the same int handle - they can run out eventually, but you can also prove that an object has been deleted). |
| ||
| Thanks for replying, Yasha - I'm sorry if I wasn't able to explain it all very well so I'll try again! The FASTEST way to describe things, is ultimately trying to retrieve the "Custom Type Object Instance" that holds a random, passed (given) value for a specific Field without Iterating through Objects or lengthy arrays. With the criteria that the value will be unique. I can see how the original post can be misleading. What I meant was, that I wanted to be able to randomly access some kind of "object" in BlitzPlus which could store information (like a hash key) to then retrieve a specific handle. If there are any hierarchial or linked associations that are possible in BlitzPlus that work something like the 3D Parent/child entity relations to achieve the same result as below: Name$=Str(The_Field__Value_To_Check_For_Duplicates) CustomChild=FindChild(CustomEntity,Name);This quick access is what I wish to achieve CustomChildStorage=GetChild(CustomChild,1);.... Name=Int(EntityName(CustomChildStorage)) TheHandleIWant=Int(Name);So I can get this value pretty much instantly without iterating MyType.SomeType=Object.SomeType(TheHandleIWant)));And Now I have the Type Instance containing that field value (if it exists already) So the entities are not required for any 3D context but purely to act as "storage" and references so the hierarchy/parent/child relationship can be utilised to cross-reference other data. It's a weird kinda of concept, but basically consider: 1) A number of type instances - this number is variable and can be very small, i.e. (1) or extremely large, (10^5 or more) and the entire range in between 2) Instances of these Type objects have a particular field which is populated during runtime. However, there is a requirement to not allow more than one type instance having the same value for this field. 3) It is not feasible (or at least, I don't believe so) to use the field values as an array index etc, since the values for this field can also vary immensely (full range of Long-Integer possible) 4) I was hoping to identify the fastest means of identifying any duplicate without having to iterate through tens of thousands. Because of the huge possibility of numbers involved, though, I wanted to avoid lists and arrays since these would double the memory usage of the Type instance at least! I hope this is much clearer now! Regarding your points, I believe 1 and 2 are irrelevant, since Ideally, I would not work with 3D entities, and because the values ultimately stored in the Types have no correlation to handles of anything, there isn't really a means to store handles as fields within the types. Point 3 - The reason for the Handle as an argument (as 'stored' in string format in the EntityName...) is because otherwise directly going for the Instance ("Strongly-Worded" as you say) for Type instances, Str() returns details of other fields which could overcomplicate things? (As if it wasn't already!, still a few string checks shouldn't be too much of a hassle...) Point 4 - Well, this is what I'm trying to do, and the example in B3D shows a means of how to do just that by (ab)using the parent/child relationship between entities, and the ability to store a user-defined hash in the entity name - only, I was hoping there may be some way to go that didn't need Blitz3D :) Point 5 & 6 All kind of deep and while it probably wont be an equivalent to what I'm looking for, I think that there is a benefit in the better object management that I might gain - I'll need to read it in more detail and get my head around it though! As I write this, I am wondering if perhaps various different Types may be possible: Type MasterType Field TypesUnder5000.FieldsLessThan5k Field Types5000To1000.FieldsBetween5and10k ;...etc. End Type Type FieldsLessThan5k Field The_Field End Type Type FieldsBetween5and10k Field The Field End Type ;... etc Which may still require iteration, but could be greatly reduced. Another thought maybe to (ab)use the BlitzPlus GUI gadgets, since I believe these have something of a hierarchial relationship, and also have 'names' or at least value fields' that might work.... |
| ||
| Aha, it clicked when you said "hash key". I have the feeling the easiest way to get what you want is with a sorted tree: http://www.blitzbasic.com/codearcs/codearcs.php?code=2574 You could always use a literal hash table; exporting the one from the C++ standard library might work if it has an implementation tuned for your key distribution. They're often less efficient for smaller sets though. This - the map, that is - is the same mechanism (although the internal C++ one will obviously be super-fast) that I think B3D uses internally to match Object and Handle itself... (You want something similar to Object/Handle but with arbitrary handles not derived from B3D's system?) |
| ||
| I've only skimmed over your posts so this might not be very relevant but what I do with my types is use a dummy type object as a demarcation bookmark so as to easily group and get to groups of types quickly. To allocate a newly created type to a group I simply insert it after the dummy object - then if I want to walk through all objects in a group I start at the dummy object then just walk through each type until I hit another dummy object or NULL from running out of objects. |
   |