Quickest way to sort list?
BlitzMax Forums/BlitzMax Programming/Quickest way to sort list?
| ||
| Hi, I've got a TList of types and each type has x and y coords. I want to sort the list of types in descending y coordinate order (with greatest value first). I'm actually converting some old BlitzPlus code that used an array and did a bubble sort on it, which was fine, but bubble sorts aren't that fast. The list can be between 100-200 items so iterating through it too many times isn't cool. I haven't yet investigated the built-in sorting capabilities of TList including the fact that you can supply your own compare function or something. But I had read somewhere that it was a bit bugged, is this still true? Anyway, I was thinking about using this method: Basically I make a new TList and fill that up. A single loop through the original list is required, but for each item in the original list I need to loop through the destination list to find the correct place to insert it. Obviously at the start the destination list won't be very big, but by the end it will contain many items. So this method sounds a tad slow. But is it faster than a bubble sort I wonder? I could try a binary search + sort but that only works on already sorted lists. Other weird and wonder method are listed on wikipedia. What ones have you found easily to implement with good results? Oh yes, I'm aware that a TList can be converted into and array and back again, maybe I should do that first? Thanks in advance. |
| ||
| Hi, Yes, convert it to an array, sort the array, and convert it back. It's reasonably fast, and saves you the trouble of making your own sorting function. |
| ||
| OK thanks. Well I still need a sorting function for the array of types because I'm sorting by the types' y coordinates, not the actual types themselves... |
| ||
| Which of those options have you tried? What didn't you like about them when you actually *tried* them rather than thought about doing them? Is is possible to sort the list first and then insert in the correct place? How often would it need sorting? Can you spread the sort over seperate frames? The quickest way to sort a list might be some hideously complicated, over-the-top, not necessary for what you're trying to do type of process. P.S. I'm not aware of having a problem with the Compare method although SSwift has posted a few times that it messes up findlink and stored links. Maybe, for whatever it is you're doing, that won't be a problem. |
| ||
| Well in my last match-3 game the bubble sorted array worked and was fast but if called a few times a frame due to lots of changes, it could cause a spike in CPU use and result in slowdown on some machines. Also I'm asking advice before I embark on the code in case anyone has tried this before (which they will have) and has some useful info. I think research is important. The sort can't be spread over several frames, it may need to occur more than once per frame as several different routines alter the y coords of the types and therefore the list needs to be resorted. Also some functions depend on the y coords being sorted before they are called. Why? Well the types drop down with gravity and the lowest ones must be moved first - this happens each frame but other actions during the frame may alter their y coords. The list is populated at the level start and can be sorted then with a slow function. After that, when types are deleted or added (sometimes from the top of the screen, other times in the middle), the items need to be added in the correct place, so bunging them on the end of the list and doing an overall sort seemed attractive if slower...kinda fire and forget. That's why I was looking for list sorting code. |
| ||
| If you can start with a sorted list then you won't need to sort it all again just have InsertAfterlink using an index on 'Y'. Somebody will mention TMAP but that's beyond me at the momentm although there's a good example somewhere. <edit> p.s. with 100-200 objects on a list you might even be able to use the list commands rather than the link methods. <edit> P.P.S I think the Compare issue was fixed by the extra comparefunc parm. |
| ||
| Yes I can start with a sorted list (making the code now) but how do I make an "index on Y"? Do you mean just loop through checking Y and insert at the correct point? I guess so. Deleting is fine as the list will handle that automatically, but what about when the Y coordinate of something changes, I guess I'll have to just loop to find the new position and move the link (can you move a link or is it just a case of backup/delete/insert?). Hmm, OK I was going for the brute force approach of sort each time but after thinking a bit more (thanks TonyG) I realise I can be a bit cleverer and just insert or recalc the list position of anything that has moved ... |
| ||
| TonyG: The docs say [code]Method Sort( ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )[/quote] What's this extra comparefunc param? [edit] It's OK I found this: http://www.blitzbasic.com/Community/posts.php?topic=59675#665275 |
| ||
| Hmm, OK I've implement a full sort using CompareFunc and it's fine and fast too. I made this insert method but I'm not convinced it's that fast because doesn't FindLink have to loop through the whole list looking for the matching object? Is this a dumb way to do it? Should I be looping through the Links directly instead of the list, and are the links *always* in the same order as the the list (maybe that's a dumb question)? Heres some code: Type TGemList Extends TList Method InsertGem(ins:TGem) 'Loop through the already sorted (largest Y first) list checking the Y coord 'and insert the passed in Gem in the correct place. Local added=0 For Local g:TGem = EachIn Self If ins.Y > g.Y Then InsertBeforeLink(ins, FindLink(ins)) Added=1 Exit 'done EndIf Next 'If it wasn't inserted, add on the end If Not added Then AddLast(ins) End Method End Type |
| ||
| It would probably be quicker to do it by link or via TMAP/Hash 'map'(?) but looping and inserting into 100-200 will be negligable. Try timing it and see what happens. <edit> You might now want to override the Compare method to do your findlink() |
| ||
| I guess you are right, (it is effectively looping twice though, once to compare, and again to find the correct link) but I could be doing it up to say 20 times a frame. It's really the idea that if you have a game, this is just one part of the logic and where possible I try to get it all optimised well so that overall it runs well to keep a high FPS. |
| ||
| Why loop twice? Use the Compare override and then Insert |
| ||
| I'll think about that, but I don't fully understand how to implement that...Anyway, surely compare has to loop as well? |
| ||
| Yep, compare and insert in the same loop if you're list is already sorted. |
| ||
My compare funciton looks like this:Function CompareY%(o1:Object, o2:Object) If TGem(o1).Y<TGem(o2).Y Then Return 1 Return 0 End Function Then in TGemList I have this method: Method SortAll() Sort(True, TGem.CompareY) EndMethod I'm not sure how I'm supposed to use that function in the InsertGem method I posted...? |
| ||
| You should be using your comparefunc to override the sortlist function and compare to override the findlink function. Findlink will return the link which you use in InsertAfterLink or InsertBeforeLink. Alternatively, do it by hand. Check your.y against listobject.y, get the listfindlink using the matching object then InsertAfter/BeforeLink. |
| ||
| regretably you've lost me. I can't be to hot on TLists and TLinks oh well...I do understand overriding in derived types though, luckily. |
| ||
| OK, last one before Germany vs Argentina. Your list has been sorted using SortList with your CompareFunc method.... OK? That leaves the FindLink method free to use your overridden Compare method. Your custom compare method returns the link of the object 'matching' your 'to-be-inserted' object. This is used to InsertAfterLink (or InsertBeforeLink if required) the new object onto the list. |
| ||
| WAH! You just better go and watch the footbal. Thanks anyway... |
| ||
In the end I changed the Insert method to this:Method InsertGem(ins:TGem) 'Loop through the already sorted (largest Y first) list checking the Y coord 'and insert the passed in Gem in the correct place. Local added=0 Local L:TLink = FirstLink() While True Local g:TGem = TGEm(L.Value()) If ins.Y > g.Y Then InsertBeforeLink(ins, L) Added=1 Exit 'done EndIf L = L.NextLink() 'Is the end of the list reached? If L = Null Then Exit Wend 'If it wasn't inserted, add on the end If Not added Then AddLast(ins) End Method It's just using links so should be faster. |
| ||
| tonyg: I totally understand what you are saying! It took me a few hours to absorb what was going on here, but now that I have working code, it makes perfect sense! Thanks! |
| ||
| Ignore I'd forgot too check to see if I was adding the first entry.... |
| ||
| You got me excited. I could actually have slightly helped on sorting functions. |
| ||
| "TGemList Extends TList Method InsertGem(ins:TGem)" Hey, are you letting on that your new game has gems in it ;-D |
   |