using qsort to sort one array based on another array?

Become a member of the CGSociety

Connect, Share, and Learn with our Large Growing CG Art Community. It's Free!

THREAD CLOSED
 
Thread Tools Search this Thread Display Modes
Old 12 December 2010   #1
Question using qsort to sort one array based on another array?

Hi,
I am trying to optimize a function using qsort to sort a very large array of Point3 world coordinates. I found it was faster to precompute the values and store them in a parallel array with a for-collect loop. My question is: using qsort, how do I reference these values to sort the Point3 array directly? My current work-around requires two additional for-collect loops as in this example:
valueArr = #() -- declare here so it can be seen by functions
  fn sortFn a b = if valueArr[a] > valueArr[b] then 1 else -1
  fn sortPoints pointArr =
   (
   	   indexArr = for i = 1 to pointArr.count collect i -- collect the indices, these are what we sort
   	   valueArr = for p in pointArr collect (cos p.x + sin p.y) -- compute a value to sort by
   	   qsort indexArr sortFn -- sort the indices
   	   for i = 1 to pointArr.count collect pointArr[indexArr[i]] -- return the points sorted by index
   )

This works fine, but for large point counts it would be faster without the first and last for-collect loops. Is it possible to do something like this:
valueArr = #() -- declare here so it can be seen by functions
   -- here's the part I don't know how to do: getting the index of a or b
   fn sortFn a b = if valueArr[(index of a)] > valueArr[(index of b)] then 1 else -1
   fn sortPoints pointArr =
   (
   	  valueArr = for p in pArr collect (cos p.x + sin p.y) -- compute some value to sort by
   	  qsort pointArr sortFn -- sort the actual point array
   )

any help is appreciated. Thanks!
 
Old 12 December 2010   #2
the sort will be faster as it only has to swap integer values and not point3 values, I guessing about 3 times faster. If you need to actually sort the array then at some stage you are always going to have to do the point3 "swaps". You can always access the point3 array via the index array though e.g. verts[indices[i]] not very neat and probably quite slow.
 
Old 12 December 2010   #3
I think the fastest way to sort this kind of data will be:

 -- make a buffer, for example:
 seed 0
 data = for k=1 to 100000 collect 
 (
 	d = random [-180,-180] [180,180]
 	cs = (cos d.x) + (sin d.y)
 	#(d, cs)
 )
 -- sort by sincos
 fn sortByN2 a b = if a[2] < b[2] then -1 else if a[2] > b[2] then 1 else 0 
 qsort data sortByN2 
 final = for d in data collect d[1]
 

Last edited by denisT : 12 December 2010 at 12:39 AM.
 
Old 12 December 2010   #4
thanks DenisT! Pairing the sort value along with the world coordinates is a great solution, it saves me from having an extra array floating around outside the functions, and let's me eliminate one of the for-collect loops. My code is cleaner now, and a touch faster too. Thanks again!
 
Old 12 December 2010   #5
Originally Posted by theTavis: ... it saves me from having an extra array floating around outside the functions...

probably some of maxscript coders don't know that is possible to pass extra parameters to qsort function. like:

fn sortbybuffer a b buffer: = if buffer[a] < buffer[b] then -1 else if buffer[a] > buffer[b] then 1 else 0
qsort data sortbybuffer buffer:other_array

or:

fn power a b = pow a b
fn sortwithfunction a b fun:  =
(
	 d1 = fun a b 
 	 d2 = fun b a
	 if d1 < d2 then -1 else  if d1 > d2 then 1 else 0
)
qsort data sortwithfunction fun:power


PS. the last sample is just a sample. It's not a good idea to use any calculation inside qsort loop. The warranty of any fast sorting is the data prepared in advance .
 
Old 12 December 2010   #6
Thread automatically closed

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.
 
Thread Closed share thread



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
CGSociety
Society of Digital Artists
www.cgsociety.org

Powered by vBulletin
Copyright 2000 - 2006,
Jelsoft Enterprises Ltd.
Minimize Ads
Forum Jump
Miscellaneous

All times are GMT. The time now is 02:53 PM.


Powered by vBulletin
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.