Hacker News Reader

Comment by glup | Hacker News Reader

One thing that is holding me back in numpy is not knowing the runtime complexity of operations—of course I can profile code, but I should have better awareness when writing code in the first place. Without an algorithms background, I don't have strong intuitions on the runtime complexity of the primitives (np.unique). Any suggestions?

View on HN

Switch to Julia! Hit @edit unique([1,2,3,2]) in the REPL and you see the implementation.

Nice! Ive been meaning to try out Julia for a while now. Is the numpy equivalent in Julia largely written in Julia itself? (as opposed to C/Fortran)

Julia's numpy equivalent is basically the standard Array type from the standard library, which I'm 99% sure is native Julia.

If one is working on small (<= 15 by 15) matrices, the StaticArrays module [1] is also native Julia and is much faster than Base.Array. Since a StaticArray knows its own size after type inference, they are allocated on the stack, which is nice.

One downside is that unless you're doing BLAS-style operations, writing non-trivial transformations of StaticArrays always seems to require generated functions.

Anyway, I think this is a feature that numpy doesn't provide.

[1] https://github.com/JuliaArrays/StaticArrays.jl

You can do the same thing in IPython/jupyter with ?? e.g.

np.unique??

That only works for functions written in pure Python though, right? Although having said that I'm not sure how many of the functions that you'd actually want to look at the source for are written in C/Cython/Fortran.

What other library tells you about complexity? And as you tell, if you don't know algorithns well, I'm pretty sure your implementations won't have better complexity.

C++'s standard library containers & algorithms have strict algorithmic complexity requirements & guarantees.

For example from std::vector::insert [1]:

  Complexity
  1-2) Constant plus linear in the distance between pos and end of the container.
  3) Linear in count plus linear in the distance between pos and end of the container.
  4) Linear in std::distance(first, last) plus linear in the distance between pos and end of the container.
  5) Linear in ilist.size() plus linear in the distance between pos and end of the container.

[1][http://en.cppreference.com/w/cpp/container/vector/insert]

edit: formatting

Well, often there are multiple ways of using numpy operations to do what you want, so it's good to have an idea of what numpy is doing under the hood so you can use the right functionality for the job at hand.

For example, np.einsum for all its greatness in the past wasn't faster than np.tensordot, but it was more flexible. One can tell einsum to try and use the same underlying BLAS functions that tensordot uses (which can parallelise the computation) if applicable, and it will likely be default for einsum to perform this optimisation automatically once the devs iron out some bugs. But for now, it pays to know how the two methods are different.

what an odd hangup. how does this have anything to do with numpy specifically?

the suggestion that jumps out is to just learn about algorithms.

Not odd at all, actually. Numpy might implement certain functions differently from other libraries. With a background in algorithms, you could make an educated guess as to complexity, but without knowing the exact implementation it's still a guess.

Reply on news.ycombinator.com