Help with Merge or Quick sort


#1

I am creating a Rhinoscript to sort surfaces based on proximity along a curve. I implemented a Bubble sort, but it is too slow. I have ~16,000 surfaces, pre-sorted into 42 “rows” of ~400. The Bubble sort takes about 2 minutes per 400 surfaces, so it would take about 84 minutes to run the script. I’d like to bring that down, thus my desire to implement a Merge or Quick sort. If anybody would be willing to help me implement a better sort algorithm, I greatly appreciate it. My script looks like this so far:


Sub SortSrfAlongCrv()

	Dim arrSrf : arrSrf = Rhino.GetObjects("Select panels to sort", 8)
	If IsNull(arrSrf) Then Exit Sub
	
	Dim strCrv : strCrv = Rhino.GetObject("Select control curve", 4)
	If IsNull(strCrv) Then Exit Sub
	
	Call Rhino.Print(Time)
	
	Call Rhino.EnableRedraw(False)
		
	'BUBBLE SORT
	Dim n : n = UBound(arrSrf) + 1
	Dim newn
	Dim swapped: swapped = False
	Dim srf1, srf2, arrCen1, arrCen2, param1, param2
	Dim temp
	Dim j
	
	Do	
		newn = 0
		For j = 1 To UBound(arrSrf)
			
			arrCen1 = Rhino.SurfaceAreaCentroid(arrSrf(j - 1))
			arrCen2 = Rhino.SurfaceAreaCentroid(arrSrf(j))
			
			param1 = Rhino.CurveClosestPoint(strCrv, arrCen1(0))
			param2 = Rhino.CurveClosestPoint(strCrv, arrCen2(0))
			
			'If this pair is out of order
			If (param1 > param2) Then
				'Swap them and remember something changed
				temp = arrSrf(j)				
				arrSrf(j) = arrSrf(j - 1)
				arrSrf(j - 1) = temp
				newn = j
			End If
			
		Next
		n = newn
	
	Loop While n <> 0
	
	'Give each surface a name based on it's material and index value
	Dim i, arrCen
	For i = 0 To UBound(arrSrf)
		
		Call Rhino.ObjectName(arrSrf(i), id)
		arrCen = Rhino.SurfaceAreaCentroid(arrSrf(i))
		Call Rhino.AddTextDot(CStr(i), arrCen(0))
		
	Next
	Call Rhino.EnableRedraw(True)
	
	Call Rhino.Print(Time)

End Sub


#2

I don’t have time to write and test now (gotta get on an airplane tomorrow) but one little Python trick is that you can sort tuples by their first element and it will bring along the rest of the elements… sorta like sorting an ordered dictionary.

mylist=[(4,"ham"),(2,"eggs"),(1,"green"),(3,"and")]
mylist.sort()
print mylist

>>>[(1, 'green'), (2, 'eggs'), (3, 'and'), (4, 'ham')]

So the first element of each tuple could be the distance and the second element could be the surface ID. But, of course, you would have to use python.

A long time ago, I wrote a “gnome sort” for vbscript… should be faster than bubble, but it’s not the fastest either…

Function GnomeKVSort(ByVal arrK, ByVal arrV)
    'Script written by Mitch Heynick
    'Version November 24, 2009	
	'Sorts Keys (objects - arrK) by Values (numbers - arrV)
	'by default lowest value will be first in output array
	Dim arrVTemp,arrKTemp,i,j
	i=1 : j=2
	Do While i <= Ubound(arrV)
		If arrV(i-1) <= arrV(i) Then  'For highest value first, change to >=
			i=j : j= j+1 
		Else 'swap values
			arrVTemp=arrV(i) : arrKTemp=arrK(i)
			arrV(i)=arrV(i-1) : arrK(i)=arrK(i-1)
			arrV(i-1)=arrVTemp : arrK(i-1)=arrKTemp
			i=i-1 'go back one index
			If i=0 Then
				i=j : j=j+1
			End If
		End If		
	Loop
	GnomeKVSort=arrK 'output is array of keys
End Function

–Mitch


(Dale Fugier) #3

See if any of this helps:



http://wiki.mcneel.com/developer/scriptsamples/sortkeyvalues


(Willem Derks) #4

Hi Damon,

I wrote this version, I think the comments although brief might be enough.
Basically I added a function I have for sorting numbers by indices.
0: make an array to get all parameters (and while calculating them anyway an array to store the centers)
1: sort the parameters array and return a new array with the indices in order.
2: go through the sorted indices and annotate the surfaces.

A short test made it appear much faster.

Call SortSrfAlongCrv()
Sub SortSrfAlongCrv()

	Dim arrSrf : arrSrf = Rhino.GetObjects("Select panels to sort", 8)
	If IsNull(arrSrf) Then Exit Sub

	Dim strCrv : strCrv = Rhino.GetObject("Select control curve", 4)
	If IsNull(strCrv) Then Exit Sub

	Call Rhino.Print(Time)

	Call Rhino.EnableRedraw(False)

	Dim j

	'create arrays for  parameters and centers
	Dim arrParms
	ReDim arrParms(Ubound(arrSrf))
	Dim arrCenters
	ReDim arrCenters(Ubound(arrSrf))
	Dim p
	For p=0 To Ubound(arrSrf)
		arrCenters(p) = Rhino.SurfaceAreaCentroid(arrSrf(p))(0)
		arrParms(p) = Rhino.CurveClosestPoint(strCrv, arrCenters(p))
	Next
	
	Dim arrSortedIndices
	arrSortedIndices = SortNumbersIndices(arrParms, True)
	
	
	'Give each surface a name based on it's material and index value
	Dim i, index ,  arrCen
	For i = 0 To UBound(arrSortedIndices)
		index = arrSortedIndices(i)
		Call Rhino.ObjectName(arrSrf(index), i) 'change "id" to "i"
		Call Rhino.AddTextDot(CStr(i), arrCenters(index))

	Next
	Call Rhino.EnableRedraw(True)

	Call Rhino.Print(Time)

End Sub



Function SortNumbersIndices(ByVal arrNumbers, blnAscending)
	'function sorts numbers and returns an array with the indices of the sorted numbers
	Dim arrRef : arrRef = Rhino.SortNumbers(arrNumbers, blnAscending)
	Dim UB : UB = Ubound(arrNumbers)
	Dim arrSorted :	ReDim arrSorted(UB)
	
	Dim i,j
	For i=0 To UB
		For j=0 To UB
			If Not IsNull(arrNumbers(j)) And Not IsNull(arrRef(i)) Then
				If arrRef(i) = arrNumbers(j) Then 
					arrSorted(i) = j
					arrNumbers(j) = Null
					arrRef(i) = Null
				End If
			End If
		Next
	Next
		
	SortNumbersIndices = arrSorted
End Function

HTH
-Willem

BTW how do I format code properly again?


#5

Thank you all for your quick replies! I love the Rhino community.
I will take a look at each solution tomorrow and let you know how I get along.


#6

So I started with Willem’s code, since it was the most explicit. (FYI, to format your code, three forward ticks (`) then vbscript or python, then your code, then three more ticks at the end of your code.)

One row (~400 surfaces) runs very quickly. So far, so good! Thank you, Willem.

I’m integrating this into my larger script and report back.


#7

So I think I’ve got it working, but as I’m running it I’m finding that it slows down. I’ve sorted the surfaces into rows, then I’m sorting each row sequentially. The first row took ~1 second to run, the 30th row took ~1m45s to run.

Any thoughts? I don’t know enough about memory management, but intuitively that’s what I think I need to address.