Sortable and Reallocatable
Monkey Forums/Monkey Programming/Sortable and Reallocatable
| ||
I currently use the Diddy ArrayList which is great for sorting isometrically drawn sprites. However, I'd like to be able to reallocate entries instead of straight up creating new ones in the same way you can in BRL.POOL. Does anyone know if such a thing exists? Ta! :) |
| ||
You can use two separate lists, an active and inactive object list, and keep the active list sorted whereas the inactive list gets reset. Actually that sounds exactly like what brl.pool already does, so why not just use it? You'll need reset methods for your object or interface, to free up an object for later use. Instead of instancing you'll pop from the pool, and instead of destroying, you push to it. |
| ||
Oh... can I sort a pool then? Or is it relatively trivial to implement pool sorting? |
| ||
Diddy's ArrayList is being replaced you should check out the new code their creating to see if it has the functionality that you need. As for brl.pool I myself have still to actually look at it, i really should tho, at the moment with my little orbit project I have a bool field on each object class, so any of my objects are either active or inactive, when they are active they get drawn and updated, when they are not they are ignored, in my new method I only call new upto a max number of objects, for example 50 asteroids, if I then need a 51'st asteroid my code looks for an asteroid that's no longer active and relocates it to its new position resets its values and then sets its bool to active so its once again in play. I'm going to use orbit as my test for using the brl.pool class but before I do I want to see how fast things are my way, I think I will try giving each object an Active and Inactive list next to see how that changes the performance, and then finally I will try implementing this brl.pool and see how quick that is. |
| ||
If you look at the generic Pool class, you will see that internally it uses a stack:Class Pool<T> Method New( initialCapacity:Int=10 ) For Local i:=0 Until initialCapacity _pool.Push New T Next End Method Allocate:T() If _pool.IsEmpty() Return New T Return _pool.Pop() End Method Free:Void( t:T ) _pool.Push t End Private Field _pool:=New Stack<T> End Too bad that _pool is private, or you could just extend it and add a sort method. The good thing though is that the class is so simple and small that you can just implement your own pool class and provide a method to sort the internal stack using the stack's Sort method (which oddly enough is absent from the documentation) Class MyPool<T> Method New( initialCapacity:Int=10 ) For Local i:=0 Until initialCapacity _pool.Push New T Next End Method Allocate:T() If _pool.IsEmpty() Return New T Return _pool.Pop() End Method Free:Void( t:T ) _pool.Push t End Method Sort:Void(ascending:Bool) _pool.Sort(ascending) End Field _pool:=New Stack<T> End Edit: You'd likely have to re-implement stack as well, giving it a Compare method for whichever class you are using. This one you could just extend though, and overload the Compare method with your object |
| ||
Just looked at it a bit more. Here's a quick example that could get you started (not really tested, but compiled without any errors)Import brl.pool Import monkey.stack Class Sprite Field x:Int Field y:Int Field zOrder:Int End ' Extend the stack class so we can overload the compare method for ' sorting sprites based on zOrder. ' Look at how FloatStack/IntStack/StringStack extend Stack in the monkey.stack module for clues... Class MyStack Extends Stack<Sprite> Method New( data:Sprite[] ) Super.New( data ) End Method Equals:Bool( lhs:Sprite,rhs:Sprite ) Return lhs.zOrder=rhs.zOrder End Method Compare:Int( lhs:Sprite,rhs:Sprite ) Return lhs.zOrder-rhs.zOrder End End ' Create our own pool class with the ability to sort the stack Class MyPool<T> Method New( initialCapacity:Int=10 ) For Local i:=0 Until initialCapacity _pool.Push New T Next End Method Allocate:T() If _pool.IsEmpty() Return New T Return _pool.Pop() End Method Free:Void( t:T ) _pool.Push t End Method Sort:Void(ascending:Bool=True) _pool.Sort(ascending) End Field _pool:=New MyStack<T> End |
| ||
Nice one, cheers Jon, will give it a look :) |
| ||
Yeah the new DiddyStack class will handle most of the sorting stuff for you if you make your class implement IComparable or if you assign a comparator to the stack. DiddyStack extends the official Monkey Stack class and adds the extra functionality ArrayList supports. Edit: I could probably make a simple DiddyPool class that extends DiddyStack to do this kind of thing. |
| ||
That'd be great Samah, if I can keep it all within the same module, perfik. |
| ||
Righto, done. Basically it's a DiddyStack with another internal DiddyStack to hold unallocated objects. If your class implements IPoolable, it will automatically call Reset() when you Free() an object. Edit: Grab it from the tip of the containers branch. http://diddy.googlecode.com/archive/containers.zip Edit 2: Added some comparison stuff to the example and print values before and after sorting. Example: Import diddy Class Foo Implements IPoolable, IComparable Field val:Int Method New() val = Rnd(1,100) End Method Reset:Void() Print "resetting" val = Rnd(1,100) End Method CompareTo:Int(other:Object) If Foo(other) Then Local f:Foo = Foo(other) Return Self.val-f.val End Return 0 End End Function Main() ' creates a DiddyPool with an empty "active" stack and 10 objects in the "free" stack Print "Instantiating with 10 free items" Local p:DiddyPool<Foo> = New DiddyPool<Foo>(10) ' Count() and FreeCount() to get "active" and "free" counts respectively Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount() ' removes one instance of Foo from the "free" stack, adds it to the "active" stack, and returns it Print "Allocating 1" Local f:Foo = p.Allocate() Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount() ' removes the object from the "active" stack and puts it back in the "free" stack ' also prints "resetting", because Foo implements IPoolable Print "Freeing 1" p.Free(f) Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount() ' removes 30 items from the "free" stack and adds them to the "active" stack, creating new instances if necessary Print "Allocating 30" p.Allocate(30) Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount() ' frees the item at index 10 - same as p.Free(p.GetItem(10)) Print "Freeing at index 10" p.FreeIndex(10) Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount() ' loop on the elements Print "Looping on all active (unsorted)" For Local f:Foo = EachIn p Print f.val Next ' sort the items in the "active" stack Print "Sorting active" p.Sort() ' loop on the elements Print "Looping on all active (sorted)" For Local f:Foo = EachIn p Print f.val Next ' loop on the free elements, if you need to Print "Looping on all free" For Local f:Foo = EachIn p.FreeItems ' do something with f Print "one loop on a free item" Next ' free all the active elements Print "Freeing all active" p.FreeAll() Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount() ' clear the free elements Print "Clearing all free" p.ClearFree() Print "Active/Free elements: "+p.Count()+" / "+p.FreeCount() End |
| ||
Hey Samah, thanks for that :D I understand ArrayLists are on the way out (and are not present in the above version of Diddy either) so am wondering what exactly I should be replacing them with? Below is how I've been using them. For Local i:Int = 0 Until activeObjects.Size() activeObjects.Get(i).FullUpdate() End Ta:) EDIT: Think I've figured it, am updating my code to use DiddyList EDIT 2 : Hmm maybe not, DiddyList seems much slower than ArrayList |
| ||
I understand ArrayLists are on the way out Not if I have anything to do with it ;) Samah IS going to keep them as I have several projects using them myself... and he is going to benchmark the new stuff to see if they are worthwhile - that's why they are on a different branch. |
| ||
ArrayList has been replaced with DiddyStack, because it extends the official Monkey Stack which basically works the same way as ArrayList. Using the containers branch is of course optional. therevills is just scared of change. :) In fact, DiddyStack should be FASTER than ArrayList, because ArrayList used a lot of boxing. Stack uses the actual generic type. |
| ||
Using the containers branch is of course optional. therevills is just scared of change. :) I'm not... I've just got lots of previous projects using ArrayList and I don't want to go thru them. In fact, DiddyStack should be FASTER than ArrayList Sounds like you need to benchmark it... "In fact" and "should" shouldn't be used in the same sentence ;) |
| ||
Ooooo intermodule beef right here! Thanks you two :D I'll give DiddyStack a look |
| ||
Ooooo intermodule beef right here! Haha! Samah and myself normally have healthy discussions regarding programming - its all good :) |
| ||
Edit: Ran it again without the string manipulation, and also trying with an object rather than a primitive. (HTML5 in Chrome 35.0.1897.2 dev-m) Function Main:Int() Local total:Int = 0 For Local a:Int = 0 Until 10 Local s:DiddyStringStack = New DiddyStringStack Print "adding 5000000 items" Local startTime:Int = RealMillisecs() For Local i:Int = 0 Until 5000000 s.AddItem("Item") Next Local endTime:Int = RealMillisecs() total += endTime-startTime Print "took "+(endTime-startTime)+"ms" Next Print "total "+total+"ms" Print "average "+(total/10)+"ms" Return 0 End adding 5000000 items took 386ms adding 5000000 items took 339ms adding 5000000 items took 352ms adding 5000000 items took 362ms adding 5000000 items took 353ms adding 5000000 items took 335ms adding 5000000 items took 329ms adding 5000000 items took 343ms adding 5000000 items took 338ms adding 5000000 items took 307ms total 3444ms average 344ms Function Main:Int() Local total:Int = 0 For Local a:Int = 0 Until 10 Local s:StringArrayList = New StringArrayList Print "adding 5000000 items" Local startTime:Int = RealMillisecs() For Local i:Int = 0 Until 5000000 s.Add("Item") Next Local endTime:Int = RealMillisecs() total += endTime-startTime Print "took "+(endTime-startTime)+"ms" Next Print "total "+total+"ms" Print "average "+(total/10)+"ms" Return 0 End adding 5000000 items took 1451ms adding 5000000 items took 1254ms adding 5000000 items took 1305ms adding 5000000 items took 1229ms adding 5000000 items took 1231ms adding 5000000 items took 1291ms adding 5000000 items took 1203ms adding 5000000 items took 1171ms adding 5000000 items took 1224ms adding 5000000 items took 1161ms total 12520ms average 1252ms Function Main:Int() Local total:Int = 0 For Local blah:Int = 0 Until 10 Local s:DiddyStack<Test> = New DiddyStack<Test> Local t:Test = New Test Print "adding 5000000 items" Local startTime:Int = RealMillisecs() For Local i:Int = 0 Until 5000000 s.AddItem(t) Next Local endTime:Int = RealMillisecs() total += endTime-startTime Print "took "+(endTime-startTime)+"ms" Next Print "total "+total+"ms" Print "average "+(total/10)+"ms" Return 0 End Class Test End adding 5000000 items took 379ms adding 5000000 items took 332ms adding 5000000 items took 353ms adding 5000000 items took 340ms adding 5000000 items took 344ms adding 5000000 items took 354ms adding 5000000 items took 386ms adding 5000000 items took 374ms adding 5000000 items took 357ms adding 5000000 items took 368ms total 3587ms average 358ms Function Main:Int() Local total:Int = 0 For Local blah:Int = 0 Until 10 Local s:ArrayList<Test> = New ArrayList<Test> Local t:Test = New Test Print "adding 5000000 items" Local startTime:Int = RealMillisecs() For Local i:Int = 0 Until 5000000 s.Add(t) Next Local endTime:Int = RealMillisecs() total += endTime-startTime Print "took "+(endTime-startTime)+"ms" Next Print "total "+total+"ms" Print "average "+(total/10)+"ms" Return 0 End Class Test End adding 5000000 items took 528ms adding 5000000 items took 553ms adding 5000000 items took 556ms adding 5000000 items took 504ms adding 5000000 items took 545ms adding 5000000 items took 555ms adding 5000000 items took 505ms adding 5000000 items took 514ms adding 5000000 items took 563ms adding 5000000 items took 498ms total 5321ms average 532ms |
| ||
After a slight hiccup (involving me freeing items as I was iterating through the pool instead of just calling freeall() afterwards), I am now happily using DiddyPool and DiddyStack and finding much less memory and CPU usage :) Thanks for all the help, I'm mighty impressed! |
| ||
You're welcome. :) Now I just have to actually work on my own game. XD (inb4 therevills) |