Python vs. Perl

[Alex Martelli]

"Jonathan Gardner" <gardner at sounddomain.com> wrote in message
news:mailman.990747225.12343.python-list at python.org...
    ...
> > Most of the times it isn't necessary to
> > translate it back into C 'for speed', especially if you want or need to
use
> > dicts (hashes.) Python's dicts are just hard to beat.
>
> I know C/C++ is poorly suited for hashes/dicts/maps, BUT the STL's map is
> AFAIK very similar to a hash/dict. I use it frequently, along with stacks,
> lists, arrays, and strings from the STL. Besides, the problem in this
aspect

std::map<> has very different performance characteristics from a
hash table -- the performance characteristics are specified in
the C++ Standard (in terms of O(N) behavior, at least), so it
would make little sense for anybody to implement a std::map with
anything else than a red-black tree.  Basically, std::map hinges
on an *order* relationship between the keys.  This makes access
O(log N).  The plus is that scanning a part or all of the map in
sorted order is VERY fast indeed (as fast as can be).  A hash
table requires no ordering, but rather a hash-function on the
keys.  If the hash function is excellent, hash table performance
can come deucedly close to O(1) for access.  *HOWEVER*, hashing
gives NO support for "ordered" scanning of some part (or all)
of the table -- you have to get all the keys, sort them -- and
this is O(N log N), generally -- and work on the sorted keys.

You can get hash-table implementations that tend to interoperate
well with the C++ Standard Library, of course.  SGI's STL, for
example, http://www.sgi.com/tech/stl/HashedAssociativeContainer.html,
defines a whole category of "hashed associative containers" as
opposed to the "Sorted associative containers" that are also
supplied by the C++ Standard Library.  As SGI's page says,
"for applications where values are simply stored and retrieved,
and where ordering is unimportant, Hashed Associative Containers
are usually much faster than Sorted Associative Containers".

[Note: *MANY* people confuse STL with the C++ Standard Library --
you'll even find lots of otherwise-decent *BOOKS* showing this
confusion -- maybe because the C++ Standard Library was originally
evolved from a then-current version of STL, or because "STL" for
"Standard Template Library" has such a nice ring.  STL is an
experimental, still-evolving, freely downloadable library for
C++, currently proprietary to SGI and formerly to HP (which
still retains some copyrights).  The C++ Standard Library is
a stable, non-proprietary SPECIFICATION, part of the ISO Standard
for the C++ Language, for which you can get several (more or
less correct and complete) implementations free and commercial].

> of C/C++ is not that you can't do it, it's just that everyone keeps
> reinventing the wheel. Once you program a hash or a dict in C once, you
> should never have to do it again, right?

Such reuse is indeed well supported by C++ (which is why many
excellent libraries of components exist for that language,
including the standard library, STL, Boost, and so on), but
not by C.  Even something as plain as qsort, in C, needs to
have layers of indirections by working with "void*"s to
represent the data, pointer to functions, &c.


Alex (Brainbench MVP for C++)