Who wrote SortList()?
BlitzMax Forums/BlitzMax Programming/Who wrote SortList()?
| ||
Because I checked the function source and it appears to use a BUBBLE SORT, the slowest sorting algorithm on the face of the planet! You should use this instead. It's Mergesort for linked lists: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html BubbleSort has a worst case time of O(N^2) and is stable. Merge sort has a worst case time of O(n log n) and is also stable. (Stable means two elements with the same value will retain their relative locations in the list.) Merge sort for linked lists also does not require more than a few extra variables of storage to perform the sort. So it is memory efficient. See this page for speed comparisons between sorting algorithms: http://linux.wku.edu/~lamonml/algor/sort/sort.html Look at how fast Mergesort is there compared to Bubble sort. Bubble takes at least several seconds to sort 1000 objects, whereas Merge sort can sort over 100,000 objects in that same time frame. Quicksort is the fastest, but much more complicated, and recursive, and performs really slowly on lists that are nearly sorted. I don't see any mention anywhere about Mergesort having those same issues. [edit] Aha, busted! ModuleInfo "Author: Mark Sibly"[/edit] |
| ||
BubbleSort has one good thing: Its runtime is not a constant no mather of the dataset (as QuickSort has it for example). It can go down to O(N) on a presorted dataset, while QuickSort will still have to run on its O(n lb(n)) (lb for log binary) In a game environment I think especially this special thing is a very great thing as (at least I) enter my data once to a dataset and don't rearrange it anymore afterwards. I only add or remove new thing so it will still run on O(N) with once an O(N^2), while QuickSort would always be O(N lb(N)) which results in quite some time lost just because of its incapability of recognizing presorted data. |
| ||
Actually, sswift, I tried adding mergesort (same page as the one you found) to the linked list, and unfortunately it seems to result in decreased speed (by about 600%). I am most likely doing something wrong (I'd bet on it if it wasn't such a stupid bet), so here's the code if anyone wants to take a look at it. Method Sort( ascending=True ) Local h:TLink = FirstLink( ) If h = Null Then Return If h.NextLink( ) = Null Then Return ' No need to sort one element h = ISort( h, _head ) _head._succ = h While h.NextLink( ) h = h.NextLink( ) Wend If Not ascending Then Swap Reversed( ) End Method ' Internal sort function Function ISort:TLink( h:TLink, oh:TLink ) Local p:TLink, q:TLink, e:TLink, tail:TLink, oldhead:TLink Local insize%, merges%, psize%, qsize%, i% If h = Null Then Return insize = 1 While True p = h oldhead = h h = Null tail = Null merges = 0 While p merges :+ 1 q = p psize = 0 For i = 0 To insize-1 psize :+ 1 q = q.NextLink( ) If Not q Then Exit Next qsize = insize While psize > 0 Or ( qsize > 0 And q ) If psize = 0 Then e = q q = q.NextLink( ) qsize :- 1 ElseIf qsize = 0 Or Not q e = p p = p.NextLink( ) psize :- 1 Else Local cmp% If p._value And q._value Then cmp = p._value.Compare( q._value ) ElseIf p._value cmp = -1 ElseIf q._value cmp = 1 Else cmp = 0 EndIf If cmp <= 0 Then e = p p = p.NextLink( ) psize :- 1 Else e = q q = q.NextLink( ) qsize :- 1 EndIf EndIf If tail Then tail._succ = e Else h = e EndIf tail = e Wend p = q Wend tail._succ = oh h._pred = oh If merges <= 1 Then Return h insize :* 2 Wend End Function At the moment, I don't have time to go over it and ensure it's working 100% correctly. |
| ||
sswift - not exactly related, but.. If you have a poke around in BlitzMax internals you will find a thing called TMaps: C:\Program Files\BlitzMax\mod\brl.mod\map.mod\map.bmx It is very useful for mapping names to Strings/Objects. Items are automatically sorted into a binary tree for fast access. In the example below you will notice that the EachIn loop retrieves the entries already sorted. Very simple example: sites:TMap = New TMap sites.Insert("pf","www.playerfactory.co.uk") sites.Insert("cw","www.codersworkshop.com") sites.Insert("bb","www.blitzbasic.com") sites.Insert("goo","www.google.com") Print String(sites.ValueForKey("bb")) Print "===============" For mysite:TNode = EachIn sites Print String(mysite.Key())+" "+String(mysite.Value()) Next |
| ||
And, if you would like a hash table:Rem HASHTABLE OBJECT - M.Laurenson/Defoc8 2006 EndRem Rem Defoc would appreciate if you credited him if you used this. No credit is to go to me. -Noel EndRem Strict Import Brl.Blitz Import Brl.LinkedList Import "hash.c" Extern "C" Function __c_hash:Int(key$z, length:Int, initval:Int)="Hash" EndExtern Global HashKey:Int(name:String) = gHashKey Function gHashKey%( name:String ) Return __c_hash( name, name.Length, 0 ) End Function Type gHashTable 'private: Field table:TList[] 'protected: Method _rement(key:Int) For Local entry:gHashEntry = EachIn table[key Shr 24] If entry.key = key entry.node.Remove( ) Return EndIf Next End Method Method _addent(key:Int,n:String,o:Object) Local entry:gHashEntry = New gHashEntry entry.key = key entry.obj = o entry.name = n entry.node = table[key Shr 24].AddLast(entry) End Method Method _getent:Object(key:Int) For Local entry:gHashEntry = EachIn table[key Shr 24] If entry.key = key Return entry.obj EndIf Next Return Null End Method 'public: Method New() table=New TList[256] For Local n:Int = 0 To 255 table[n] = New TList Next End Method Method SetEntry( name:String, obj:Object ) Local key:Int = HashKey( name ) Local o:Object = _getent(key) If o And o <> obj Then _rement(key) _addent(key,name,obj) End Method Method InsertEntry(name:String,obj:Object) Local key:Int = HashKey( name ) _addent(key,name,obj) End Method Method RemoveEntry(name:String) Local key:Int = HashKey( name ) _rement(key) End Method Method GetEntry:Object(name:String) Local key:Int = HashKey( name ) Return _getent(key) End Method Method Flush() For Local n:Int = 0 To 255 table[n].Clear( ) Next End Method Method GetEntryCount(index:Int) Return table[index].Count( ) End Method Method ToArray:Object[]( iters%=0 ) Local amnt%=0 For Local i:Int = 0 To 255 amnt :+ table[i].Count( ) Next Local obj:Object[amnt] Local c%=0 For Local i:Int = 0 To 255 For Local n:gHashEntry = EachIn table[i] If iters > 0 Then obj[c] = n Else obj[c] = n.obj EndIf c:+1 Next Next Debuglog " table size: "+c Return obj End Method Method ObjectEnumerator:gHashTableEnum( ) Local e:gHashTableEnum = New gHashTableEnum e.arr = ToArray( ) Return e End Method End Type Type gHashTableEnum Field idx%=0 Field arr:Object[] Method HasNext%( ) If idx < arr.Length Then Return True Debuglog "Has no more elements in the enumerator at idx "+idx Debuglog "Array length is "+arr.Length Return False End Method Method NextObject:Object( ) Debuglog " idx: "+idx idx :+ 1 Return arr[idx-1] End Method End Type Type gHashEntry Field key:Int Field name:String Field obj:Object Field node:TLink End Type |
| ||
Mapping names? Not related? Poking around in it, it seems very related! From what I can tell, I'm pretty sure that you could do this: sites.Insert(Order, ThisSprite) Then each time you add a sprite to it, it would recurse down the binary tree, and insert the sprite at the correct location. And as in your example above, using EachIn to loop through them would return them in the desired order. If you then wanted to change the order of one, you would simply remove it from the list, and then reinsert it with the new Order. This could prove most useful! But is it supported? And is it in the docs anywhere? Do I just have to guess at what the methods do? :-) I wonder if it is faster to use a binary tree rather than looping through a list and simply inserting the sprite at the right location? My intutution says "likely", but I'm not sure. I guess if you end up with a balanced tree, the answer is yes, but if you insert everything in the correct order in the first place you might end up with a string instead of a tree. Unfortunately, I'm not very knowledgeable when it comes to binary trees. I know the basics, but I'd have to go research them to figure out how stepping down a tree and inserting values to the left or right branch if they are greater or less than the current node, leads to a list which is sorted. Are you SURE that that thing always sorts the strings correctly? |
| ||
You know reading all marks code, and noel's code... I'm not really sure this OOP stuff actually makes code easier to understand. :-) |
| ||
I've found that a good sort for a linked list type structure is the selection sort. The idea is to run through the list and find the smallest or largest element, reduce the size of the unsorted list by 1 and repeat. It always does N swaps and (N^2)/2 comparisons. It's simple to implement so there's no overhead or recursion or function calls. |
| ||
LOL i have allso used merge sort from the same page ;) heres my result, its just a little faster then your version noel :/ it must be the overhead of using a double linked list. some timings of sorting 100000 integers in a type: mine = 0.199000001 noels = 0.257999986 array = 0.0869999975 array of ints = 0.0120000001 Function MergeSortList( slist:TList) Local p:TLink, q:TLink, e:TLink, tail:TLink, oldhead:TLink Local insize:Int, nmerges:Int, psize:Int, qsize:Int, i:Int Local list:TLink If slist = Null Then Return If slist._head._succ <> slist._head Then list = slist._head._succ If list = Null Then Return insize = 1 Repeat p = list oldhead = list list = Null tail = Null nmerges = 0 While p <> Null nmerges :+ 1 q = p psize = 0 For i = 0 Until insize psize :+ 1 If q._succ = oldhead Then q = Null Else q = q._succ EndIf If q = Null Then Exit Next qsize = insize While (psize > 0) Or ((qsize > 0) And (q <> Null)) If psize = 0 Then e = q q = q._succ qsize :- 1 If q = oldhead Then q = Null ElseIf (qsize = 0) Or (q = Null) Then e = p p = p._succ psize :- 1 If p = oldhead Then p = Null ElseIf p._value.Compare( q._value) <= 0 Then e = p p = p._succ psize :- 1 If p = oldhead Then p = Null Else e = q q = q._succ qsize :- 1 If q = oldhead Then q = Null EndIf If tail <> Null Then tail._succ = e Else list = e EndIf e._pred = tail tail = e Wend p = q Wend tail._succ = list list._pred = tail If nmerges <= 1 Then Return insize :* 2 Forever EndFunction |