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.
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'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. ;-)
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...
--Chris
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
