Christopher Smith wrote:
guy keren wrote:
i once started writing a book to teach data structures and algorithms
in python. after a while i found that i had to struggle in order to
check the efficiency of the algorithms - because the underlying
structure of tuples and lists in python is opaque - unless you look at
the underlying code (which happens to be written in C).
>
It's pretty easy... you instrument your different primitive operations
and then you just collect reports which show how many times each
operation was used. If you don't want to do that, simple benchmarking
will serve well enough.
>
it's not pretty easy for a young student. and benchmarking is one of the
things that most people don't do properly.
when you want to calculate complexity - you need to know how things
work, algorithmically. indeed, in my python half-written-book, i went
out and performed some benchmarking, in order to demonstrate my claims.
i still wanted to see how things work from the inside, and wanted to
explain that, to the extent that it can be done to people with very
little prior programming experience.
the nice thing about C (as well as pascal), is that the underlying
operations are transparent - you can see that accessing an array
element is realy an O(1) operation - because grasping the underlying
implementation is very easy. more then this - when and where i was in
school - we learned assembly language before we learned about data
structures (at least if you took the courses in the recommended order)
- so it was easy enough to calculate the actual time (and space)
complexity of operations.
>
Incorrect. The nice thing about C is that the underlying operations
*appear* to be transparent. Modern OS's get in the way of things such
that even a simple memory read may be a potentially very complicated
procedure. Even if you run on bare metal with straight assembly, you
still have to worry about cache lines, set associativity, register
renaming, pipelines, virtualization, etc.
>
you are right. which is why, after the data structures course, there was
the operating systems course (to teach about the software part of how
the computer works) and a "computers structure" course - to teach about
virtual memory, and pipelines, and caches, and what-not. to that - add
the "logic design" course - in which a CPU was built from basic logic
gates - and you see that they realy worked hard to give people the
knowledge. and yet - it was structured in a way that will allow people
to get to know things in a pace they could grasp. i think the pace was
still too fast for most of us - but i'm not sure how it could have been
done better.
You're happily assuming these operations are transparent, and you can do
the same thing with a higher level language.
this is not true for higher level languages - their basic constructs
are quite complex, and you need to know C in order to understand how
exactly they work.
>
It's amazing that LISP developers were ever able to understand what they
were doing before C was invented. ;-)
>
and yet - they had to know assembly in order to see how LISP worked from
the inside. or are you talking about "LISP machines"?
in this regards, it doesn't matter if the language is Java, C#, Python
or anything similar - what you conceive as an atomic operation - may
be quite complex. what you grasp as taking O(1) memory - might take
much more due to its underlying implementation (although this is far
less common - usually just the constant is higher than a young student
imagines).
...and of course even malloc() consumes more memory than you ask for as
well...
true - which is why this issue used to be covered in the 'intro to
operating systems' course (or in one course after that). sadly, it looks
like this issue was removed from the teaching programs (or perhaps my
memory fails me - and it was taught in an optional course). in the last
few years - i met very little graduates that have any idea about how
malloc is implemented, or even how virtual memory works. at least in my
area of work - this knowledge is very important.
--guy
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
