So I wrote an inplace selection sort in Julia, to compare its performance
against a Java counterpart,
Here is the code
function selectionSort!{T}(v::AbstractVector{T}, f)
n = length(v)
for i=1:n-1
min = i
for j=i+1:n
if f(v[j], v[min])
min = j
end
end
tmp = v[i]
v[i] = v[min]
v[min] = tmp
end
end # selection Sort
The equivalent java code is
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i + 1; j < N; j++) {
if (a[j].compareTo(a[min]) < 0) {
min = j;
}
}
Comparable temp = a[i];
a[i] = a[min];
a[j] = temp;
}
}
I have the following questions
(1) the function f passed in to selectionSort should have the type f: (T,T)
=> Boolean, ie it takes two elements of the Vector and tells whether they
are in correct order or not. This could be < for example. How do I state
this in Julia iow, how do I specify the function signature?
(2) Are there any horrendous inefficiencies in the Julia code which are
apparent to experienced Julians? When I benchmark against the equivalent
Java I'm getting a factor of 10+ slowdown for larger arrays (though both
seem O(n^2) as it should be)
size(of array, uniform distribution of doubles between 0 and 1),time taken
to sort in Java (in milliseconds), time taken to sort in Julia. both times
are an average of 5 runs for each array size
1000,0.003,0.010
2000,0.003,0.041
4000,0.011,0.165
8000,0.044,0.664
16000,0.206,2.660
I readily admit I have very little idea of what it takes to write
performant code in Julia. Any help greatly appreciated.
Of course, I might be doing something really stupid in the first place,
which happens all to frequently sadly enough. Please point out any mistakes
in my code.
Thanks in advance,
Ravi
