I’d never had a need to use qSort before today and I found it a bit confusing at first, but now I’ve found my solution I thought I’d put a little challenge up to see who can make the best solution… is there a better way than qSort?
vals = #(#(0,400,1),#(0,100,2),#(10,200,3),#(0,200,4),#(0,300,5))
--I Need it to return in this order, so sorted by 2nd value of array then first, but ignoring the 3rd.
--#(0,100,2)
--#(0,200,4)
--#(10,200,3)
--#(0,300,5)
--#(0,400,1)
the question is how many items in the array… the best solution might be different for 1000 and 100,000
In this particular instance not many, probably under 100… but it would be interesting to see the comparisons? Perhaps someone else wants to join the party before Denis owns this one
if we talk about qsort i think that will be hard to beat just simple:
fn sortByIndex v1 v2 = if (v1[1] < v2[1]) then -1 else if (v1[1] > v2[1]) then 1 else if (v1[2] < v2[2]) then -1 else if (v1[2] > v2[2]) then 1 else 0
here is a template to play:
seed 0
num = 10000
arr = for k=1 to num collect #(random 0 1000,random 0 1000,random 0 1000)
fn sortByIndex v1 v2 = if (v1[1] < v2[1]) then -1 else if (v1[1] > v2[1]) then 1 else if (v1[2] < v2[2]) then -1 else if (v1[2] > v2[2]) then 1 else 0
t1 = timestamp()
m1 = heapfree
qsort arr sortByIndex
format "time:% memory:%
" (timestamp() - t1) (m1 - heapfree)
arr
for the sample array above …
using c# on-fly assembly VS mxs qsort:
C# time:44 memory:2400280L
MXS time:240 memory:2227016L
so c# solution is much faster
How do you pass a ND Array to #C?
The only way I’ve found is to convert it to 1D Array.
this is the base c# sort function (sort by first and by next) :
public static object[][] Sort(object[][] array)
{
Array.Sort(array, delegate(object[] x, object[] y)
{
int result = (x[0] as IComparable).CompareTo(y[0]);
return (result != 0) ? result : (x[1] as IComparable).CompareTo(y[1]);
});
return array;
}
array of several types (integer, float, string) max automatically converts to object[]
Thank you Denis!
And for Point2/Point3 they should be converted to array first?
#( #([1,1,1],[2,2,2],[3,3,3]), #([4,4,4],[5,5,5],[6,6,6]) )
#( #(#(1,1,1),#(2,2,2),#(3,3,3)), #(#(4,4,4),#(5,5,5),#(6,6,6)) )
true… only three base mxs types max aromatically converts to .net array (object)… also arrays of .net objects (classes)
Aha but your code is incorrect Denis…
Yours returns…
#(#(0, 100, 2), #(0, 200, 4), #(0, 300, 5), #(0, 400, 1), #(10, 200, 3))
not
#(#(0, 100, 2), #(0, 200, 4), #(10, 200, 3), #(0, 300, 5), #(0, 400, 1))
it’s because you Need it to return in this order, so sorted by 2nd value of array then first
i’ve sorted in the order “first-second”
here is what you asked. but the performance must be the same:
fn sortByIndex v1 v2 = if (v1[2] < v2[2]) then -1 else if (v1[2] > v2[2]) then 1 else if (v1[1] < v2[1]) then -1 else if (v1[1] > v2[1]) then 1 else 0
time:283 memory:1384L
My Solution…
seed 0
num = 10000
arr = for k=1 to num collect #(random 0 1000,random 0 1000,random 0 1000)
fn compareFN v1 v2 =
(
Case of
(
((v1[2]) == (v2[2]) and (v1[1] < v2[1])) : -1
((v1[2]) == (v2[2]) and (v1[1] >= v2[1])) : 1
((v1[2]) < (v2[2])) : -1
((v1[2]) > (v2[2])) : 1
default: 0
)
)
t1 = timestamp()
m1 = heapfree
qsort arr compareFN
format "time:% memory:%
" (timestamp() - t1) (m1 - heapfree)
arr
global i
fn sortCorrect v1 v2 =
(
i += 1
if v1 < v2 then -1 else if v1 > v2 then 1 else 0
)
fn sortIncorrect v1 v2 =
(
i += 1
if v1 < v2 then -1 else if v1 >= v2 do 1
)
(
seed (i = 0)
arr = for k=1 to 100 collect (random 1 3)
t1 = timestamp()
m1 = heapfree
qsort arr sortCorrect
format "correct iterations:% time:% memory:%
" i (timestamp() - t1) (m1 - heapfree)
arr
)
(
seed (i = 0)
arr = for k=1 to 100 collect (random 1 3)
t1 = timestamp()
m1 = heapfree
qsort arr sortIncorrect
format "incorrect iterations:% time:% memory:%
" i (timestamp() - t1) (m1 - heapfree)
arr
)
check this snippet…
qsort – it’s “quick sort” algorithm. it needs to know every time if “pivot” element less, equals, or greater than a “compared to”. it works with only two conditions (for example – “less and not less”), but it stays in-place when three-condition algorithm goes to the next element in case of “equals”.
try to run the same snippet for 1,000 elements… 10,000… don’t try 100,000!
This is the only thing I can think of…
Case of
(
((v1[2]) == (v2[2]) and (v1[1] < v2[1])) : -1
((v1[2]) == (v2[2]) and (v1[1] == v2[1])) : 0
((v1[2]) == (v2[2]) and (v1[1] > v2[1])) : 1
((v1[2]) < (v2[2])) : -1
((v1[2]) > (v2[2])) : 1
default: 0
)
100
1000
10000
Yeah I’m not going to try 100000
OK
sortCorrect()
sortIncorrect()
correct iterations:399 time:1 memory:3392L
#(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …)
incorrect iterations:1165 time:3 memory:38096L
#(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …)
OK
sortCorrect()
sortIncorrect()
correct iterations:3332 time:10 memory:159016L
#(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …)
incorrect iterations:86508 time:157 memory:4818376L
#(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …)
OK
sortCorrect()
sortIncorrect()
correct iterations:36699 time:74 memory:2023344L
#(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …)
incorrect iterations:8388633 time:16438 memory:23001380L
#(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …)
So by having my function as…
Case of
(
((v1[2]) == (v2[2]) and (v1[1] < v2[1])) : -1
((v1[2]) == (v2[2]) and (v1[1] > v2[1])) : 1
((v1[2]) < (v2[2])) : -1
((v1[2]) > (v2[2])) : 1
default: 0
)
I Should be ok?
that’s OK. but if you would count the worse case you see that it needs make 6 comparisons.
why? if you can do the same for only 4?
fn sortByIndex v1 v2 = if (v1[2] < v2[2]) then -1 else if (v1[2] > v2[2]) then 1 else if (v1[1] < v2[1]) then -1 else if (v1[1] > v2[1]) then 1 else 0