SortList becomes slower as list is bigger..

BlitzMax Forums/BlitzMax Beginners Area/SortList becomes slower as list is bigger..

BachFire

(Posted 2007) [#1]

Hello,

I needed to sort a list, and was thrilled to discover a command to do just that. I have been playing around with it a bit, and it seems to be very slow?? I use the small code below, to test the command. Just change the first line to change the number of entries that should be sorted. It varies a bit, but if I sort 1000 entries it takes around 0,13 seconds. 5000 takes 3,13 seconds, and 10000 takes a whopping 12,48 secs.

Is there ANY way to speed this up?

EDIT: for the program I work on, I need to sort somewhere between 15000 and 20000..

entries:Int=5000 'number of entries in list
mylist:TList=CreateList()
number:Int=0

SeedRnd MilliSecs()
For a:Int=1 To entries
 number=Rnd(1,255)
 ListAddLast mylist,Chr$(number)
Next

'Sort it..
timestart#=MilliSecs()
SortList mylist
timeend#=(MilliSecs()-timestart)/1000
Print ; Print entries+" entries sorted in: "+timeend+" secs."
End

Dreamora

(Posted 2007) [#2]

Yes replace the sort method with an own one.
There is a quicksort implementation floating around somewhere here.

with the bubblesort like solution of BM you won't be able to sort that massive amount of objects in usefull time (it takes up to 20000^2 comparisions!)

Who was John Galt?

(Posted 2007) [#3]

I don't know what type of sort Blitz uses internally, but the answer to your question is probably YES, you can speed it up. You would need to do some research on fast sorting algorithms and implement your own. Those times for the sort don't seem unreasonable to me. The sort is always going to be slower as the list gets bigger. It's not going to be a linear thing which is what you're seeing.

BachFire

(Posted 2007) [#4]

Thank you guys, I'll look into it.

H&K	(Posted 2007) [#5]

SortList becomes slower as list is bigger

Baring in mind that the list is always going to take longer to sort as the list gets bigger, no matter what you do. Please take a hard look at what you are tring to do.

You can double the speed, on a pc twice as fast (Was that glib or what)
10000 Sorts will probably always take "seconds"

I Know Im being vague, but what Im tring to say is, try not to have to sort through a list of 10000 things, unless your a turn based game, no matter what clever algorithim you use

So you lookup sorting algorithims that are faster for whatever data smaple you expect. But dont expect a super fast one.

BachFire

(Posted 2007) [#6]

Yes, of course it takes more time, the bigger the list is. I know that. ;) But sorting 15-16000 entries takes around 30 secs to complete (on my machine - see sig for specs) with the builtin sort command. I'm hoping to bring it down to around 5-8 seconds. Somehow.. Lol..

Anyway, I have been reading a bit about quicksorting, and it seems to be a genius way of sorting. It's well explained here:

http://www.mycsresource.net/articles/programming/sorting_algos/quicksort/

and here:

http://en.wikipedia.org/wiki/Quicksort

Personally, I'm a bit slow at getting to understand things fully, so coding my own quicksort routine will probably take some time. But I get smarter, so I don't mind too much.. ;)

Suco-X

(Posted 2007) [#7]

Hi BeachFire.
This seems to be faster

entries:Int=5000 'number of entries in list
mylist:TList=CreateList()
number:Int=0

SeedRnd MilliSecs()
For a:Int=1 To entries
 Local Str:String

	For Local i:Int = 0 Until 10
		Str:+Chr(Rand(65, 80))
	Next 

 ListAddLast mylist,Str
Next

'Sort it..
timestart#=MilliSecs()

Local Arr:Object[] = ListToArray(myList)

Arr.Sort()

Mylist = ListFromArray(Arr)


timeend#=(MilliSecs()-timestart)/1000
Print ; Print entries+" entries sorted in: "+timeend+" secs."
End

Mfg Suco

Brucey

(Posted 2007) [#8]

I thought the built-in sort was a quick sort ?
(just guessing here after having looked at the source - blitz_array.c)

BachFire

(Posted 2007) [#9]

@Suco-X

Wow.. It sorts 16000 entries in 0,02 seconds.. Damn.. Didn't hope for anything THAT fast!

It seems a bit too fast, to be working. But I used it in the main program I'm working on, and apparantly it works as expected. Is there a catch? I don't see it.. Well, I guess that makes you my hero, Suco-X! :)

Thank you!

H&K	(Posted 2007) [#10]

It sorts 16000 entries in 0,02 seconds

Well I take back what I said

The bad thing is that I knew that would make it faster, as I suppose Dream and Nomen knew, but I just didnt think to say it. (Honest theres a big long theard about it, which Im sure the other two took part in)

Suco-X

(Posted 2007) [#11]

Hi BeachFire.
No Problem.
I think sorting an array is very fast and lists aren't adapted for such situations. Maybe someone else can show us the catch, I can't.
Mfg Suco

BachFire

(Posted 2007) [#12]

@Brucey

I thought the built-in sort was a quick sort ?
(just guessing here after having looked at the source - blitz_array.c)

I guess array sorting is quicksort, as I have just witnessed. Don't know about the SortList command though, but it seems very slow..

BachFire

(Posted 2007) [#13]

@H&K

The bad thing is that I knew that would make it faster, as I suppose Dream and Nomen knew, but I just didnt think to say it.

Heh.. Not a problem. The human mind works in mysterious ways. Mine does, anyway.. ;)

TaskMaster

(Posted 2007) [#14]

Sorting? You want sorting?

Click here:

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

degac

(Posted 2007) [#15]

Yes - array sort is faster...but what in case of User-type? I mean sort some user-type by a specific field...

Perturbatio

(Posted 2007) [#16]

Yes - array sort is faster...but what in case of User-type? I mean sort some user-type by a specific field...

SuperStrict

SeedRnd MilliSecs()

Type TMyObject
	Field Size:Int
	Field Name:String
	
	Function Create:TMyObject(Size:Int, Name:String)
		Local tempObj:TMyObject = New TMyObject
			If Size < 1 Then Size = 1
			tempObj.Size = Size
			tempObj.Name = Name
		Return tempObj
	End Function
	
	Method Compare:Int(otherObject:Object)
		Local comp:TMyObject = TMyObject(otherObject)
		If comp Then
			If Size > Comp.Size Then 
				Return 1 'if the otherObject is less than this one
			ElseIf Size < Comp.Size Then
				Return -1 'if the otherObject is greater than this one
			Else
				Return 0
			EndIf
		EndIf
		Return 0
	End Method
End Type

Const numItems:Int = 20000
Global list:Object[numItems]
Global StartTime:Int
Global out:String

For Local i:Int = 0 To numItems-1
	Local o:TMyObject = TMyObject.Create( Rand( 1, 100 ) , "Object "+i )
	'list = list[..list.length+1]
	list[i] = o
Next

'don't uncomment these with a large number of items!
'out:+ "~nBefore Sort:~n"
'For Local o2:TMyObject = EachIn list
'	out:+ "Name: "+o2.name + " Size:"+o2.Size+"~n"
'Next
StartTime = MilliSecs()
list.sort()
out:+ "Sort Time: "+((MilliSecs()-StartTime)/1000:Float)+" secs~n"

'out:+ "~nAfter Sort:~n"
'For Local o3:TMyObject = EachIn list
'	out:+ "Name: "+o3.name + " Size:"+o3.Size+"~n"
'Next
Print out

Space Fractal

(Posted 2007) [#17]

Thanks for this info. It was much faster here too, since I stumped on this typic.

For user objects, code like this can also been used (Like that one above):

Type TFileInfo
	Global sortmethod
	
	Field Album$
	Field Artist$
	Field Title$
	Field File$	
	
	Method toString:String()
		Select sortmethod
		Case 0 Return File$
		Case 1 Return Artist$+":"+Title$+":"+Album$
		Default Return Title$+":"+Artist$+":"+Album$
		EndSelect
		Return FILE$
	EndMethod
	
	Method Compare:Int(o2:Object)
		Local a:String=toString()
		Local b:String=TFileInfo(o2).toString()
		If a>b Then Return 1
		If a<b Then Return -1
		Return 0
	EndMethod
EndType


Global Info:TList=New TList ; this hold all object as TFIleInfo objects

Function sort(Sortby$)
	Select Sortby$
		Case "Files" TFileInfo.sortmethod=0
		Case "ArtistTitle" TFileInfo.sortmethod=1
		Case "TitleArtist" TFileInfo.sortmethod=2
	EndSelect
		
	Local Arr:Object[] = ListToArray(Info)
	Arr.Sort()
	Info = ListFromArray(Arr)
EndMethod

Yep, the code can been better, but it works pretty fine....

FlameDuck

(Posted 2007) [#18]

I thought the built-in sort was a quick sort ?

Arrays are, lists are bubblesorted (it is impractical to locate suitable pivots in non-indexed data structures). I'm guessing a mergesort might be able to speed it up.

For reference bubblesort has quadratic O(n*n) timecomplexity, while quicksort is O(n*log(n)). Which is a non-trivial improvement for large (ie > 32) numbers of n.

Dreamora

(Posted 2007) [#19]

although, bubblesort can go to O(n) on pre sorted data, while quicksort will remain O(n*log(n))

degac

(Posted 2007) [#20]

I'm a stupid, I'm a stupid, I'm a stupid, I'm a stupid, I'm a stupid, I'm a stupid, ....

Thanks to Perturbatio & Space Fractal...after more than 1 years using BlitzMax I just re-discovered the fact that array of objects are objects, so they have the Compare methods and I can override it with mine....

I'm a stupid, I'm a stupid, I'm a stupid, I'm a stupid, I'm a stupid, I'm a stupid, ....