Hi,
I wonder if there is specific sorting functions for StaticArrays (e.g. sorting network) ?
I found this GitHub - JeffreySarnoff/SortingNetworks.jl: Sort 1..25 values with conditional swaps !
Unfortunately, it stops at 25 item (I have 40…)
StaticArrays have the advantage of compile-time known size. Other than for small sizes (less than 20), I think this does not help substantially for sorting. So going with regular sorting routines should not add significant overhead.
As for sorting networks (which are in a different model of computation than CPUs which are Von Neumann / Turing type), they can be easily recursively defined for larger arrays, but since they are not adaptive to data, they are actually worse in the sense of doing some spurious comparisons (e.g. if a < b and b < c, we do not need to compute a < c, but this cannot be known before the first two comparisons are made).
1 Like
StaticArrays uses BitonicSort for static arrays of length less than 20. For longer arrays it might not be useful but it is possible although not documented:
x = @SArray(rand(40))
sort(x, alg=StaticArrays.BitonicSort)
1 Like
This has been requested before. I will add implementations through 32 inputs
.
1 Like
ahh – you want to do this with 40 items – so I will extend it to 48 items.
3 Likes
here is swapsort for 40 items (exactly)
each empty line separates the 17 internally parallelizable layers
each group must be processed in order (sequentially)
there are 265 comparisons
faster than sort
| with | |
|---|---|
| 3x | Float32 |
| 2x | Float64 |
| 1.5x | Int |
const ITEMS_MAX = 40
const VALS = ([Val{i} for i=1:ITEMS_MAX]...,)
@inline function min_max(a::T, b::T) where {T<:Real}
return (b < a ? (b, a) : (a, b))
end
@inline function swapsort(vec::AbstractVector{T}) where {T}
n = length(vec)
n > ITEMS_MAX && throw(ErrorException("swapsort(vector) not defined where length(vector) > $ITEMS_MAX"))
return swapsort(VALS[length(vec)], vec)
end
function swapsort(a::T, b::T, c::T, d::T, e::T, f::T, g::T, h::T, i::T, j::T, k::T, l::T, m::T, n::T, o::T, p::T, q::T, r::T, s::T, t::T, u::T, v::T, w::T, x::T, y::T, z::T, aa::T, bb::T, cc::T, dd::T, ee::T, ff::T, gg::T, hh::T, ii::T, jj::T, kk::T, ll::T, mm::T, nn::T) where {T}
a, b = min_max(a, b)
c, d = min_max(c, d)
e, f = min_max(e, f)
g, h = min_max(g, h)
i, j = min_max(i, j)
k, l = min_max(k, l)
m, n = min_max(m, n)
o, p = min_max(o, p)
q, r = min_max(q, r)
s, t = min_max(s, t)
u, v = min_max(u, v)
w, x = min_max(w, x)
y, z = min_max(y, z)
aa, bb = min_max(aa, bb)
cc, dd = min_max(cc, dd)
ee, ff = min_max(ee, ff)
gg, hh = min_max(gg, hh)
ii, jj = min_max(ii, jj)
kk, ll = min_max(kk, ll)
mm, nn = min_max(mm, nn)
a, c = min_max(a, c)
b, d = min_max(b, d)
e, g = min_max(e, g)
f, h = min_max(f, h)
i, k = min_max(i, k)
j, l = min_max(j, l)
m, o = min_max(m, o)
n, p = min_max(n, p)
q, s = min_max(q, s)
r, t = min_max(r, t)
u, w = min_max(u, w)
v, x = min_max(v, x)
y, aa = min_max(y, aa)
z, bb = min_max(z, bb)
cc, ee = min_max(cc, ee)
dd, ff = min_max(dd, ff)
gg, ii = min_max(gg, ii)
hh, jj = min_max(hh, jj)
kk, mm = min_max(kk, mm)
ll, nn = min_max(ll, nn)
a, e = min_max(a, e)
b, f = min_max(b, f)
c, g = min_max(c, g)
d, h = min_max(d, h)
i, m = min_max(i, m)
j, n = min_max(j, n)
k, o = min_max(k, o)
l, p = min_max(l, p)
q, u = min_max(q, u)
r, v = min_max(r, v)
s, w = min_max(s, w)
t, x = min_max(t, x)
y, cc = min_max(y, cc)
z, dd = min_max(z, dd)
aa, ee = min_max(aa, ee)
bb, ff = min_max(bb, ff)
gg, kk = min_max(gg, kk)
hh, ll = min_max(hh, ll)
ii, mm = min_max(ii, mm)
jj, nn = min_max(jj, nn)
a, i = min_max(a, i)
b, j = min_max(b, j)
c, k = min_max(c, k)
d, l = min_max(d, l)
e, m = min_max(e, m)
f, n = min_max(f, n)
g, o = min_max(g, o)
h, p = min_max(h, p)
r, u = min_max(r, u)
t, w = min_max(t, w)
y, gg = min_max(y, gg)
z, hh = min_max(z, hh)
aa, ii = min_max(aa, ii)
bb, jj = min_max(bb, jj)
cc, kk = min_max(cc, kk)
dd, ll = min_max(dd, ll)
ee, mm = min_max(ee, mm)
ff, nn = min_max(ff, nn)
a, y = min_max(a, y)
b, z = min_max(b, z)
c, aa = min_max(c, aa)
d, bb = min_max(d, bb)
e, cc = min_max(e, cc)
f, dd = min_max(f, dd)
g, ee = min_max(g, ee)
h, ff = min_max(h, ff)
i, gg = min_max(i, gg)
j, hh = min_max(j, hh)
k, ii = min_max(k, ii)
l, jj = min_max(l, jj)
m, kk = min_max(m, kk)
n, ll = min_max(n, ll)
o, mm = min_max(o, mm)
p, nn = min_max(p, nn)
b, c = min_max(b, c)
d, m = min_max(d, m)
f, k = min_max(f, k)
g, j = min_max(g, j)
h, v = min_max(h, v)
i, q = min_max(i, q)
n, o = min_max(n, o)
s, gg = min_max(s, gg)
x, ff = min_max(x, ff)
z, aa = min_max(z, aa)
bb, kk = min_max(bb, kk)
dd, ii = min_max(dd, ii)
ee, hh = min_max(ee, hh)
ll, mm = min_max(ll, mm)
d, g = min_max(d, g)
e, s = min_max(e, s)
f, z = min_max(f, z)
h, dd = min_max(h, dd)
j, m = min_max(j, m)
k, gg = min_max(k, gg)
o, ii = min_max(o, ii)
p, x = min_max(p, x)
q, y = min_max(q, y)
v, jj = min_max(v, jj)
bb, ee = min_max(bb, ee)
hh, kk = min_max(hh, kk)
d, r = min_max(d, r)
i, q = min_max(i, q)
k, y = min_max(k, y)
l, v = min_max(l, v)
m, u = min_max(m, u)
p, dd = min_max(p, dd)
s, cc = min_max(s, cc)
t, bb = min_max(t, bb)
w, kk = min_max(w, kk)
x, ff = min_max(x, ff)
a, i = min_max(a, i)
b, d = min_max(b, d)
e, q = min_max(e, q)
g, m = min_max(g, m)
h, t = min_max(h, t)
k, s = min_max(k, s)
l, n = min_max(l, n)
o, w = min_max(o, w)
r, z = min_max(r, z)
u, gg = min_max(u, gg)
v, dd = min_max(v, dd)
x, jj = min_max(x, jj)
aa, cc = min_max(aa, cc)
bb, hh = min_max(bb, hh)
ff, nn = min_max(ff, nn)
kk, mm = min_max(kk, mm)
c, g = min_max(c, g)
e, i = min_max(e, i)
f, h = min_max(f, h)
j, t = min_max(j, t)
k, q = min_max(k, q)
m, y = min_max(m, y)
n, z = min_max(n, z)
o, aa = min_max(o, aa)
p, bb = min_max(p, bb)
u, ee = min_max(u, ee)
x, dd = min_max(x, dd)
ff, jj = min_max(ff, jj)
gg, ii = min_max(gg, ii)
hh, ll = min_max(hh, ll)
b, e = min_max(b, e)
c, q = min_max(c, q)
d, f = min_max(d, f)
g, s = min_max(g, s)
j, r = min_max(j, r)
l, p = min_max(l, p)
m, o = min_max(m, o)
n, t = min_max(n, t)
u, aa = min_max(u, aa)
v, hh = min_max(v, hh)
w, ee = min_max(w, ee)
x, ll = min_max(x, ll)
y, cc = min_max(y, cc)
z, bb = min_max(z, bb)
ii, kk = min_max(ii, kk)
jj, mm = min_max(jj, mm)
c, i = min_max(c, i)
d, k = min_max(d, k)
f, j = min_max(f, j)
g, m = min_max(g, m)
h, n = min_max(h, n)
l, r = min_max(l, r)
o, u = min_max(o, u)
p, v = min_max(p, v)
s, y = min_max(s, y)
t, z = min_max(t, z)
w, cc = min_max(w, cc)
aa, gg = min_max(aa, gg)
bb, hh = min_max(bb, hh)
dd, kk = min_max(dd, kk)
ee, ii = min_max(ee, ii)
ff, ll = min_max(ff, ll)
c, e = min_max(c, e)
g, k = min_max(g, k)
h, l = min_max(h, l)
m, q = min_max(m, q)
n, r = min_max(n, r)
o, s = min_max(o, s)
p, t = min_max(p, t)
u, y = min_max(u, y)
v, z = min_max(v, z)
w, aa = min_max(w, aa)
x, bb = min_max(x, bb)
cc, gg = min_max(cc, gg)
dd, hh = min_max(dd, hh)
jj, ll = min_max(jj, ll)
d, e = min_max(d, e)
f, m = min_max(f, m)
h, o = min_max(h, o)
j, q = min_max(j, q)
l, u = min_max(l, u)
n, s = min_max(n, s)
p, w = min_max(p, w)
r, y = min_max(r, y)
t, cc = min_max(t, cc)
v, aa = min_max(v, aa)
x, ee = min_max(x, ee)
z, gg = min_max(z, gg)
bb, ii = min_max(bb, ii)
jj, kk = min_max(jj, kk)
e, i = min_max(e, i)
f, g = min_max(f, g)
h, k = min_max(h, k)
j, m = min_max(j, m)
l, n = min_max(l, n)
o, q = min_max(o, q)
p, u = min_max(p, u)
r, s = min_max(r, s)
t, y = min_max(t, y)
v, w = min_max(v, w)
x, z = min_max(x, z)
aa, cc = min_max(aa, cc)
bb, ee = min_max(bb, ee)
dd, gg = min_max(dd, gg)
ff, jj = min_max(ff, jj)
hh, ii = min_max(hh, ii)
g, i = min_max(g, i)
h, j = min_max(h, j)
k, m = min_max(k, m)
l, o = min_max(l, o)
n, q = min_max(n, q)
p, r = min_max(p, r)
s, u = min_max(s, u)
t, v = min_max(t, v)
w, y = min_max(w, y)
x, aa = min_max(x, aa)
z, cc = min_max(z, cc)
bb, dd = min_max(bb, dd)
ee, gg = min_max(ee, gg)
ff, hh = min_max(ff, hh)
f, g = min_max(f, g)
h, i = min_max(h, i)
j, k = min_max(j, k)
l, m = min_max(l, m)
n, o = min_max(n, o)
p, q = min_max(p, q)
r, s = min_max(r, s)
t, u = min_max(t, u)
v, w = min_max(v, w)
x, y = min_max(x, y)
z, aa = min_max(z, aa)
bb, cc = min_max(bb, cc)
dd, ee = min_max(dd, ee)
ff, gg = min_max(ff, gg)
hh, ii = min_max(hh, ii)
return a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, aa, bb, cc, dd, ee, ff, gg, hh, ii, jj, kk, ll, mm, nn
end
swapsort(x::NTuple{40,T}) where {T} =
swapsort(x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17], x[18], x[19], x[20], x[21], x[22], x[23], x[24], x[25], x[26], x[27], x[28], x[29], x[30], x[31], x[32], x[33], x[34], x[35], x[36], x[37], x[38], x[39], x[40], )
swapsort(::Type{Val{40}}, x::AbstractVector{T}) where {T} =
swapsort(x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17], x[18], x[19], x[20], x[21], x[22], x[23], x[24], x[25], x[26], x[27], x[28], x[29], x[30], x[31], x[32], x[33], x[34], x[35], x[36], x[37], x[38], x[39], x[40], )
2 Likes
Thank you very much !