I’m trying to create a heap:
h = Collections.heapify([1])
But I get this error: “UndefVarError: Collections not defined”. I’m using Julia version 1.6.3.
It’s not really clear from just one line of code, but where does Collections come from? It’s not part of Julia’s stdlib, and doesn’t show up in JuliaHub. Is this perhaps code you’ve copied from another source?
It might be useful if you provide a bit more context
Collections was a built-in module in ancient versions of Julia (e.g. Julia 0.4), and there was indeed a function Collections.heapify. So, I’m guessing that @hexolio is trying to run some ancient (pre-1.0) Julia code.
We don’t see much pre-1.0 Julia code nowadays. One approach is to go back to ancient Julia versions (0.4, 0.5, 0.6, 0.7), all of which can still be downloaded, and upgrade the code step-by-step, fixing the deprecation warnings at each upgrade. Or you can just try to port it directly to 1.x, but then you will get no warnings — you will just get errors for obsolete functions like Collections.heapify, and will need to figure out what the modern analogue is.
In this particular case, Collections.heapify was moved to DataStructures.heapify in the DataStructures.jl package.
2 Likes
Haha, no. Nothing that important. I’m actually trying to complete this coding challenge. I managed to complete it in Python using its built-in heapq module (other approaches I tried were too slow). I’m trying to translate every Python solution I do into Julia to help me learn it, and I must have found some ancient Stack Overflow answer that referenced the Collections module.
But it looks like the DataStructures package is not part of the standard library (I tried adding using DataStructures at the top with no luck). So I’m guessing they took min-heaps and priority queues and other useful stuff like that out of the standard library – why would they do that?
I’m hoping I’m wrong, because you’re obviously only allowed to use the standard library in coding challenges, so without those data structures, I’m all out of ideas (apart from implementing a binary heap myself from scratch!). This might be veering slightly off-topic now, but I’m going to be cheeky and ask: are there any other data structures like those that work in linear or linearithmic time that could be used in their place and happen to be built into Julia?
that doesn’t seem an obvious rule.
Or indeed a sensible one.
Julia (like LaTeX) is not a language designed to be used without it’s ecosystem.
It has a package manager built in for a reason.
using Pkg
Pkg.add("DataStructures")
using DataStructures
h = DataStructures.heapify([1])
1 Like
Maybe I’m wrong, but I’ve always assumed it wouldn’t be accepted because the code has to run on the site’s servers and I’m sure they wouldn’t want users installing just any third-party package. And I don’t think I’ve ever seen another accepted solution that used them.
Julia code in the stdlib is not privileged — there’s nothing you can do in the stdlib (or even Base) that you can’t also implement in a package — and Julia’s built-in package manager makes installing packages easy. Conversely, there is a big advantage to keeping code in a separate package outside of the stdlib — outside packages can be updated much more frequently, since they aren’t tied to Julia releases.
The main reasons to put something in the stdlib are (a) its implementation is tightly coupled to Julia internals (typically because it shares code used internally by Base) or it is otherwise used by the core Julia (e.g. the Test package), (b) to load more quickly for large core packages (stdlibs are built-in to the default system image), (c) it’s something that we want to encourage all Julia users to standardize on (e.g. Pkg), or (d) historical reasons that make something painful to spin off.
In the case of heaps, priority queues, and other data structures, since these are not needed by Julia Base or stdlibs, it was decided that it would be more beneficial to spin them off into a separate package.
4 Likes
Interesting. That makes sense, I suppose. So I guess that means Julia’s standard library is pretty small, and I’m all out of luck if I want to use something like a heap or priority queue? Is there anything else that can approximate those?
I did said it all made sense, but actually I was a bit confused by this:
Wouldn’t this be true for all programming languages? Isn’t that what Turing-complete means (unless I’m misunderstanding what you’re saying)?
No, that’s not what Turing-complete means. All Turing-complete languages can solve the same computational problems. That doesn’t mean they solve the problems equally efficiently.
For example, code in the Python standard library is often implemented with the help of low-level C code, which is therefore impossible to match (efficiency-wise) in pure-Python modules. It may even be impossible to replicate in Python modules that include compiled C code, if the stdlib uses internal functions or data structures that are not part of the public API.
Hmm… I didn’t consider efficiency. So you’re saying that someone could write a Julia package that replicates any of the built-in Julia functions without losing any efficiency? That’s quite a cool property for a language to have. That also makes the decision to spin unneeded functions off into separate packages make more sense. The only people I can think of whom this might possibly disadvantage are those with artificial constraints put on them, such as people like me doing stdlib-only coding challenges – unless we have enough programming know-how to implement any non-stdlib function from scratch (in which case we’d be doing a much harder challenge!). The only other people possibly in this category I can think of are those without appropriate permissions on their work computer, maybe? I’m not sure about that one.
For the most part, yes — almost all of the built-in functions are implemented purely in Julia. There are only a handful of functions, mostly to do with low-level memory management, that use C internals and would be harder to replicate. (In fact, the built-in parser is implemented in Scheme for bootstrapping reasons, and there was an external Julia-based package that was actually faster than the built-in version. It’s actually not too uncommon to have packages that beat the “built-in” performance for specialized tasks, from radix sorting to bignum arithmetic.) Even things as basic as arithmetic promotion rules, which in most languages are built-in and immutable, are programmable in Julia because they were implemented in pure-Julia code.
Indeed, it was one of the core driving principles of Julia — the less that has to be “built into” a language, the more powerful user code becomes. Read e.g. Jeff Bezanson’s PhD thesis about the design of Julia.
1 Like
I just checked, and it seems to work just fine to install and load external packages the DataStructures.jl package seems to be pre-installed on codewars.com.
e.g. if you do
module DblLinear
using DataStructures
export dbl_linear
function dbl_linear(n::Int)
additions = PriorityQueue{Int,Int}((1 => 1,))
while n > 0
x = dequeue!(additions)
n -= 1
for y in (2x+1, 3x+1)
additions[y] = y
end
end
return dequeue!(additions)
end
end
in your solution for this coding challenge, it succeeds. (The advantage of having a built-in package manager!)
Update: DataStructures.jl is pre-installed on codewars.com — no need for import Pkg; Pkg.add("DataStructures"). And it seems that installing most other packages times out, unless the package is very small.
1 Like
While it is nice to know this works, it really smells to me like an oversight from the server maintainers. My experience with this kind of site/competition is that you are never allowed to use external packages unless it is a curated set.
1 Like
Actually, it appears that the DataStructures.jl package is already in their curated list of pre-installed packages (along with IterTools.jl and Lazy.jl) — you can just delete the Pkg.add from my code above and it works. Trying to install anything else seems like it times out in most cases, unless the package is very small (e.g. installing LaTeXStrings.jl works).
This is extremely helpful to know – thank you for investigating. Thinking about it now, I’ve actually seen people use numpy in Python solutions even though it’s not part of the standard library. They must allow certain pre-installed packages.
One thing though – I kinda feel like I’ve been given an unfair advantage after glancing at your solution (even though it’s basically the same as my Python one with a few optimizations). It’s just that I wanted to translate it to Julia myself. Is there any way of using “spoiler” tags on here, like on Reddit?
Thanks again for your sharing your broad knowledge and careful explanations – I’m already finding that the community here is way more patient and kind than the one on Stack Overflow!
2 Likes
Julia is a functional language and has a rich type system.
One of the surprisign things to me is that user defined types are not ‘second class citizens’.
I believe the same can be said about user defined functions. Anyone care to comment?