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 |
   |