Article 56278 of comp.unix.solaris: Path: mri.com!newsfeed1.aimnet.com!news1.aplatform.com!nntp.mainstreet.net!news.pbi.net!su-news-hub1.bbnplanet.com!cam-news-hub1.bbnplanet.com!news.bbnplanet.com!news.idt.net!enews.sgi.com!fido.asd.sgi.com!news.neu.sgi.com!news From: "Elizabeth D. Zwicky" Newsgroups: comp.unix.admin,comp.unix.questions,comp.unix.solaris,comp.misc,comp.org.usenix Subject: Re: UNIX SYSTEM ADMINISTRATORS Date: Wed, 05 Mar 1997 13:47:48 +0100 Organization: Silicon Graphics Manufacturing Lines: 58 Distribution: inet Message-ID: <331D6B74.15FB@neu.sgi.com> References: <33046F39.4BDA@escmail.orl.lmco.com> <01bc1a91$4721aa60$9958f8cc@mwalsh> <330e34e3.15854334@news.airmail.net> <5efn04$on5@panix2.panix.com> <330d9e47.108384708@news.airmail.net> <5ff9us$4s1$1@tecsun3.tec.army.mil> <331c9905.261460678@news.airmail.net> NNTP-Posting-Host: pterodactyl.neu.sgi.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.01C-SGI (X11; I; IRIX 5.3 IP22) Xref: mri.com comp.unix.admin:37611 comp.unix.questions:73392 comp.unix.solaris:56278 comp.misc:25451 comp.org.usenix:4679 William A. Yohman wrote: > I simply buy the "netshell" books. They apply directly to what I need > and then also give me lots of advanced information. I will take a book > about DNS and BIND over one that it just programming theory! Long ago and far away I shared a house with two other programmers. One of them was a starving college student, and the other one was a highly-paid computer consultant with no theoretical background. One day, the starving college student bounght a copy of "Algorithms". This is a beautiful hardcover full of comp sci stuff that cost at the time rough $60, which was approximately $59.99 more than the disposable income he had available. The highly-paid computer consultant thought this was the dumbest concept he had ever heard of. 8 different ways to sort things! Why, anybody could sort things! The very next weekend, we went down into the basement where the computers were to ask the highly-paid computer consultant if he'd like to go to a movie. "Well," he said "I can't go right now, maybe in a couple of hours, I need to do something as soon as this finishes. The odd thing is, I thought it would be done by now." "What's it doing?" says the starving college student, and receives the explanation that the pointers have gotten corrupted for the doubly-linked list that makes up the entire customer database for one of the consultant's important clients, and he is traversing the database, sorting it back into order. With an insertion sort. He's traversing them in creation order, which means that they are in fact about 75% in final order. The reason he thought he'd be done by then is that he watched it do the first 20 items, and multiplied the time to do that by the size of the database. The starving college student whipped out a pocket calculator and calculated the time necessary to do the sort, using an algorithm which in this situation approaches O(n!) and that exclamation point is *not* for emphasis boys and girls, and pointed out that indeed we might as well all go to the movie since it was going to finish no sooner than midnight Sunday night and it was then 2:00 on Saturday afternoon, we had plenty of time. The highly-paid computer consultant hung on grimly until the bitter end, which was in fact 4am Monday, before admitting that maybe, just maybe, there was some point in knowing more than one sort algorithm. The truly sad point here, which some of you may have noticed, is that it was a doubly-linked list and the data was mostly in final order; simply reversing the order in which he traversed the already sorted data would have changed it from near O(n!) performance to near O(n) performance without requiring him to learn a new algorithm at all. Increase in programming time: 5 or 10 minutes tops. Decrease in run time: call it 36 hours. As it happens, his resulting loss was not just his Saturday afternoon amusement, but also about 20 billable hours, and very nearly his major client. All because he didn't know that how you sort things matters. Sometimes life *does* imitate morality plays. Elizabeth Zwicky zwicky@neu.sgi.com