I want to convert a small Matlab code for a sorted list with key - value pairs (array implementation of a priority queue) to Julia.
Double keys are allowed, but sorted according to addition for causality. Values can be of variable length and type. This seems to rule out PriorityQueue.jl. I also want to compare the speed of Matlab vs. Julia -
I will be happy to report the timings!
So I started naively…
The actual sorting is done in insertion-sort style, so Julia’s insert! appeared close.
The following insert! operations (not so) obviously fail, what’s the correct way?
Please bear with me for the loose syntax below.
A = Vector{Float64} # A = []
insert!(A,1,0.2) # A = [0.2]
insert!(A,1,0.1) # A = [0.1 0.2]
insert!(A,1,0.1) # A = [0.1 0.1 0.2] # allow double entries
insert!(A,2,0.3) # A = [0.1 0.3 0.1 0.2]
and generally, how to do it correctly for
A = Vector({Float64, Any)}
insert!(A,1,('toto'))
insert!(A,2,('titi', 1.0)) # allow multi-parameter and -type
you can have an array of type Any for its elements. But unless you use some structure like a linked list your insert operation might be really slow and inefficient since you need to allocate a new array every time.
String in Julia must be wrapped in double quotes ". ' are reserved for characters.
You want something like this
mutable struct EgList
array::Vector{Any}
EgList() = new([])
end
function insert!(a::EgList, pos, val)
if pos - length(a.array) == 1
push!(a.array, val)
elseif pos == 1
a.array = vcat([val], a.array)
else
a.array = vcat(a.array[1:pos-1], [val], a.array[pos:end])
end
a
end
A = EgList()
insert!(A,1,0.2) # A = [0.2]
insert!(A,1,0.1) # A = [0.1 0.2]
insert!(A,1,0.1) # A = [0.1 0.1 0.2] # allow double entries
insert!(A,2,0.3) # A = [0.1 0.3 0.1 0.2]
A = EgList()
insert!(A,1,("toto"))
insert!(A,2,("titi", 1.0)) # allow multi-parameter and -type
Thx xiaodai!
Except for different syntax, that is exactly how I coded it in Matlab. And no surprise, in Matlab a vector is implemented as (doubly?) linked list. I will look up the equivalent implementation and check the timings.
You be a bit more flexible if you use some other data structure so you can allocate a bigger array before hand or if you know the types of the data, you can avoid the use of Any.
For you want to do EgList may not be the ideal data structure
The Vector data structure is a contiguous one-dimensional array, but you can add and remove items at the front and back, so it works in terms of API for what you want. On modern hardware, a contiguous array is hard to beat and it’s very hard to find a use case where a linked list is better, even for operations that are in principle O(n) for a vector and O(1) for a linked list: Bjarne Stroustrup: Why you should avoid Linked Lists - YouTube.
