12 Apr
2009
12 Apr
'09
7:38 a.m.
Fred Cisin <cisin at xenosoft.com> writes
You don't think agree that even the theoretician
should understand that
some algorithms can take advantage of existing order and end early, while
others are a fixed duration?
Example: The library is doing a "retrospective conversion" of its card
catalog to an OPAC ("Online Public Access Catalog"). The cards are
mechanically scanned. They are nominally in order, however, due to being
handled by humans, a lot, there "might be" some errors in sequence.
"Might" - yeah, right. Which sort is "better"?
"Shell-Metzner" or
"shaker"?
In the past couple years Google and Amazon return search results
to not just the title or author, but the text in the book if it has
been OCR'ed or was originally electronic. Obviously Google knows
a lot about efficient free-text searching but other folks know it too.
In the past 15 or 20 or maybe even 30 or 40 years in the right circles
(I do not hang around in database circles! But I was using Rdb a while
back) the catalog would be loaded
straight to an indexed database with several keys arranged for
easy alphabetical sorting. The indexed database might even be
smart enough to allow free-text or associative searching through
some clever trickery. Even if there wasn't an index on the field we
wanted to sort on there's probably the SQL "ORDER BY (whatever)"
keyword. I will admit that databases can do some spectacularly
slow things if you build your indices wrong, and even the most
expensive version of Oracle can suddenly become much slower than
an Apple II running a linear search on a cassette-tape file
in the hands of the clueless.
In the past 10 years or so, I'd just say (in Perl) "sort keys %hash".
Surprisingly until fairly recently this could, worst case, be a quadratic
sort but they recently put some tricks in (preshuffling) so this
will basically never happen.
If I was interviewing a recent CS graduate I would expect him to
not address the problem of a card catalog index by talking only about sorting,
I'd expect him to know some of the newer technologies - databases with
keys; maybe even knowing about hashes if I ask about how a database
implements an index; possibly knowing about the indexing technolgies
allowing free-text searches. If he started talking about
bubble vs shell sort I would go "OK, you got the points for knowing
about sorting, now teach me about this new stuff" about 10 words in.
If I wanted to know what he knew about how algorithmic complexity I'd ask
him about bogosort which probably they didn't teach him about in school,
but would give him a leg up if he had been reading or maybe even
contributing to the Jargon File for the past few decades.
If a candidate agreed with me that buying Oracle got the governor
of California fired, I'd hire him on the spot.
If I had a new hire and I saw him writing any sort algorithm, I'd teach
him how to do it by using one already built into the system.
Tim.