Sorting arrays of structures


#1

Dear All,

Could you, please, give me a hand in a sorting problem:

mutable struct Vox
    radiusR::Float64
    x::Int32
    y::Int32
    z::Int32
end

Voxels=Vector{Vox}(undef, 0)
#loop starts here to fill the arrays of Vox structures
push!(Voxels,Vox(computeRadius[j,k,i], j, k, i))
#loop ends here

sort!(Voxels, by=expression, rev=true)
#e.g., expression=getfield.(tmp, :radiusR) or any other way to extract this vector of data

I get an error: ERROR: MethodError: objects of type Array{Float64,1} are not callable
Use square brackets for indexing an Array.
I tried many ways around with sort function, but finally only one worked as described below.

Now, if i substitute the above-mentioned array of structures with a tuple of the form:
v=Array{Tuple{Float64,Int,Int,Int}}(undef,0); loop to fill the array: push!(v,(computeRadius[j,k,i], j, k, i)); sort!(v, by=first, rev=true)
and i get what i want. Is there a way to sort original array of structures in a fast and elegant fashion?


#2

By the way, you’ll be more likely to get useful help if you post code that actually works (or at least actually reproduces the error you’re asking about). Currently, your code relies on computeRadius, i, j, k, and expression, which are all undefined, so we have to guess what you mean in order to be helpful.

But I think what you want is something like:

julia> sort!(Voxels, by = v -> v.radiusR, rev=true)
2-element Array{Vox,1}:
 Vox(2.0, 2, 3, 4)
 Vox(1.0, 2, 3, 4)

The by argument takes a function, so in this case I’ve used an anonymous function.


#3

I would normally just define isless(::Vox, ::Vox). Then any kind of sorting problem should just work without needing the anonymous function.

julia> mutable struct Vox
           radiusR::Float64
           x::Int32
           y::Int32
           z::Int32
       end

julia> import Base: isless

julia> isless(a::Vox, b::Vox) = isless(a.radiusR, b.radiusR)
isless (generic function with 67 methods)

julia> xs = [Vox(x, 1,2,3) for x = 10.0:-1.0:1.0]
10-element Array{Vox,1}:
 Vox(10.0, 1, 2, 3)
 Vox(9.0, 1, 2, 3) 
 Vox(8.0, 1, 2, 3) 
 Vox(7.0, 1, 2, 3) 
 Vox(6.0, 1, 2, 3) 
 Vox(5.0, 1, 2, 3) 
 Vox(4.0, 1, 2, 3) 
 Vox(3.0, 1, 2, 3) 
 Vox(2.0, 1, 2, 3) 
 Vox(1.0, 1, 2, 3) 

julia> sort!(xs)
10-element Array{Vox,1}:
 Vox(1.0, 1, 2, 3) 
 Vox(2.0, 1, 2, 3) 
 Vox(3.0, 1, 2, 3) 
 Vox(4.0, 1, 2, 3) 
 Vox(5.0, 1, 2, 3) 
 Vox(6.0, 1, 2, 3) 
 Vox(7.0, 1, 2, 3) 
 Vox(8.0, 1, 2, 3) 
 Vox(9.0, 1, 2, 3) 
 Vox(10.0, 1, 2, 3)

#4

Thank you, Raf! This also worked perfectly.
However, i do have some additional question if you do not mind:

Just to understand Julia better, did you do here something we could call overloading isless and adding sorting as a private function of the Vox class (from C++ perspective)?


#5

My apologies, I actually tried to describe the problem as brief as possible, the code to fill in the array has nothing to do with the sorting problem. But i shall consider copying the whole code next time if this is more useful…

Thank you very much, this solution worked just fine!


#6

This is multiple dispatch at work. You created your own type (Vox), and overloaded the definition of the isless function to work with elements from your type. I don’t know how that compares to C++


#7

That is not really necessary. The thing to do is to make a minimal working example (or non-working, as the case may be), that is, make an example which is as simple as possible, but demonstrates what you want help with.

Here’s a MnWE, borrowing from @Raf and you:

mutable struct Vox
    radiusR::Float64
    x::Int32
    y::Int32
    z::Int32
end

xs = [Vox(x, 1,2,3) for x = 10.0:-1.0:1.0]
sort!(xs, by=getfield.(xs, :radiusR), rev=true)

together with the error message.

BTW: are you sure you need Vox to be mutable? Just curious, but small structs like these are often good candidates to be immutable, potentially with much better performance.


#8

For homogeneous vectors, this really works entirely the same way as in C++: You pass a singleton object (Function object) in the by parameter that does the comparisons; dispatch is at compile time and hence comparisons can be inlined. Only that in julia, there is a Base.isless that is used by default, and holds a julia “Function”, which is basically a bunch of compiled julia methods (C functions); when your sort(arr::Vector{T}) is compiled (jitted), then the correct method is selected.

You don’t need to have public/private/virtual isless methods attached to your type in C++ either.

That being said, I prefer the julia syntax for this kind of thing. For heterogenous arrays, I’d get a headache trying to get this right in C++.


#9

Not much to add. But writing a minimum working example lets other people run your code, understand the problem, and make changes without doing too much work themselves.

In terms of the “overloading” in Julia it is best described as adding a method to the Base function isless for your custom type Vox. Multiple dispatch will choose your isless method from the 67 possible methods when isless(::Vox, ::Vox) is called.