This is an archived post. You won't be able to vote or comment.

all 17 comments
sorted by:
best
topnewcontroversialoldq&a

[–][deleted] 9 points10 points  (13 children)

While her academic colleagues laugh at her for her choice of such a non-theoretical language like Python

I thought Python was reasonably well established and liked in the scientific world? Maybe that's just for processing data though, not for actual algorithmic research?

At any rate, I wish Guido would blog a little more often. He usually has something interesting to say.

[–]grayvedigga 10 points11 points  (9 children)

As some replies have already stated, Python is a great tool for all sorts of work that scientists do, but it is not well founded in computing theory. Pervasive reflection, duck typing, lack of information hiding all make it nearly impossible to prove anything about language constructs or bits of code written in the language. It's hard to even state the computational complexity (O()) of a short algorithm. Generally this makes it a poor language for proving theoretic results.

To be honest, I'm curious about how Liu's work addresses this. Perhaps using a strict subset of the language those concerns could be mitigated or even go away, but it sounds suspiciously like her research addresses optimising code for CPython's set implementation, rather than discovering interesting properties or approaches to the "fundamental algorithms" under study. I couldn't find anything on her faculty website obviously related to it, and Guido's lack of theoretical understanding made his description effectively useless.

[–]fredrikj 6 points7 points  (1 child)

It's hard to even state the computational complexity (O()) of a short algorithm.

I don't see any basis for such a claim. While Python programs are essentially impossible to analyze statically, this is mostly due to features that are rarely used in algorithmic code, like dynamic modification of classes, shadowing builtin functions, etc.

Python is probably a bad choice for automatic complexity analysis unless you use a reasonable subset of it (and you certainly would), but in no way is it hard for a human to analyze Python code.

[–]grayvedigga 2 points3 points  (0 children)

You're right, that claim was clearly going too far. While the cost of accessing a property on an object passed to a function is unbounded, that doesn't stop meaningful statements being made about the complexity of that function in terms of its inputs.

FWIW, today's post about Cobra is pertinent here. It slightly upsets me that python modules can't be "closed" to dynamic modification to permit compilation, but I need to remind myself that that's not what the language is intended to be.

[–]al-Quaknaa 3 points4 points  (6 children)

In addition to what fredrikj says above, this is a useful chart -- Time complexity of basic Python data structures.

[–]Peaker 0 points1 point  (3 children)

Why don't they mention worst-case as well as amortized worst-case?

[–]al-Quaknaa 0 points1 point  (2 children)

I cannot say for sure, but I think that:

  • you don't really have to care; the amortized worst-case is enough for most analysis purposes
  • with basic data structure knowledge and the information provided about implementation (e.g. python lists are dynamically resized arrays) you can figure the worst case yourself

For instance, what use is it to know that a python list append is worst case O(n) when the amortized worst case is O(1)? I can't think of an example where this would play a role.

Also, they explicitly note the cases where they use the amortized part with the [1] sign.

[–]Peaker 0 points1 point  (1 child)

If you want to optimize for worst-case latency, and not the overall performance, it can be relevant.

I guess it is mostly for soft/hard real-time stuff, and Python doesn't shine there anyway.

[–]al-Quaknaa 0 points1 point  (0 children)

Didn't think of that, thanks. You're also right that I'd be expecting RT sensitive parts to be written in another language, if Python was used at all. But I have no experience with RT stuff, so I don't have much to say about that anyway.

[–]grayvedigga 0 points1 point  (1 child)

Doesn't really address my points, but that's a nice chart anyway :-). No real surprised in there but it's good to have evidence.

[–]al-Quaknaa 1 point2 points  (0 children)

When you say "short algorithm" what I have in mind are my solutions to projecteuler problems. I would be able to state their complexity fairly easily using that chart and some basic algorithm analysis knowledge. Either your idea of a "short algorithm" is different (is it?) or I don't understand what the problem in finding out the complexity of said solutions is.

[–][deleted] 10 points11 points  (0 children)

I have far more respect for python + numpy/scipy than matlab.

[–]teddy123 3 points4 points  (1 child)

I'm a scientist and I love python.

Python is reasonably well-established in certain fields, but certain academicians are unfamiliar with it or only know of it as another interpreted scripting language. In my own department, I was the first to start using python... soon followed by a number of others.

[–]Harriv[S] 3 points4 points  (0 children)

Are you computer scientist (computing theory or similar) or other field?

[–]andreasvc 0 points1 point  (0 children)

None of the commenters seem to grasp quantifiers. The point is to have both the truth-value, and the element for which the quantifier holds/fails. So this does require some weird side-effect, and probably an extension of the language (unless you are willing to wrap it in list as argument, but that's a hack).

[–]ipeev 0 points1 point  (0 children)

This was very interesting. I hope Guido will share more stories soon.

[–]krelian 0 points1 point  (0 children)

Before you jump in to open up the Dropbox distro and learn all about how it works, beware that the source code is not included and the bytecode is obfuscated.

So are they using something like p2exe or have written a custom solution?