[Edu-sig] Edu-sig Digest, Vol 22, Issue 9

[Toby Donaldson]

> If one uses linked lists, then it is a flaw in Python. Personally, I have
> never needed a linked list in Python.
> 
> I can't agree with this statement. 

:-) You must know something about my programs that I don't!

> There are many situations where a 
> linked structure us the _right_ implementation of a particular 
> abstraction. 
>
> If you want an indefinitely large queue in Python with 
> constant time operations, then a linked list is probably the best way to 
> do it. 

Ah. Your willingness to settle with "probably the best" in this instance
explains much of what we disagree about.

I am not saying you are disinterested in performance or not interested in
doing the "best" or "right" thing. I am not making a universal claim that
performance is the most important thing above and beyond all other concerns.
Nor am I saying that it's not perfectly acceptable to settle for "good
enough" performance or quality if that's appropriate. What I am saying is
that, for the case of a queue and similar utility data structures and
algorithms that can be frequently used in many different programs, *I* am
*not* happy with anything less than the best possible performance that can
be achieved on the machine (not the *language*, the *machine*) I run it on.
*I* do not want my machine wasting *any* time on useless overhead.

> Furthermore, it is very easy to implement this in Python. Using 
> linked lists for this in no way illustrates any flaw in Python.

:-) Do you know anyone who claims this?

> The reason you may not have seen linked lists in Python is that the 
> built-in continguous implementation is so good. Still, there are cases 
> where reference-based linked structures are a good thing: ordered 
> structures with constant time insertion, graphs, trees, sparse matricies 
> (perhaps), etc. Sometimes, the linked list is entirely hidden in the 
> logic of the problem. I once did a backtracking solution to n queens in 
> Python and discovered only after the fact that I had actually built a 
> linked list.

:-) Gee Dr. Science! Linked lists are cool!

> > Do you think Python would be a better language for beginners if a fixed
size
> > array data type was added to it that had a different interface than the
> > current dynamic lists?
> >  
>
> No. 

Good. Can you explain why it is a good thing for LISP?

> The important thing to keep in mind is that it is not a design flaw 
> simply that a language makes it easy to write inefficient programs. 

So long as you don't need to write programs for use in the real world!

> This is ususally the sign of a higher-level language. 

"the" sign? It's certainly possible to write inefficient programs in
low-level languages.  Constructs like functions, loops, if-statements,
classes, etc. are a more accurate indicator.

> It becomes easier to 
> write an inefficient program simply because it is easier to write 
> programs period. Again, the queue example shows this. It is absolutely 
> trivial to implement using append and pop(0). 

Well, in a Turing-complete language I could simulate any computation by
doing it on a Turing machine or in the lambda calculus (speaking of LISP
:-)), so obviously any powerful enough language allows you to write simple
programs in a complex way.

My point is that if a language *only* allows for an inefficient
implementation of something (or makes it too difficult to achieve), then it
is flawed. Having to write an assembly language module or use some other
special tool is fine, but I would prefer the language to do it itself.

Maybe *you* don't care about that particular thing, but for someone who
*does*, it is a real and significant problem that you can't talk away.

> If O(n) efficiency is good enough for the problem at hand, what's wrong 
> with that?

Nothing. But what if it's not good enough?

As you know, O-notation only partially orders algorithms by efficiency, and
doesn't distinguish between algorithms of the same order. It's no good for
deciding which of two O(n) algorithms is better. This is why, for instance,
Knuth precisely counts assembly-language steps in his algorithm analyses,
and why programmers developing algorithms and data structures for the real
world resort to empirical experiments.

Performance is of course not the only thing, but it is important, often
vital. Especially in the real world. Remember, Knuth said "premature
optimization is the root of all evil". Don't ignore the word "premature".
Knuth, in particular, is keenly interested in optimization.

Anyways, this is all getting pretty far a field from Python education.

Toby