[lug] File modification
Herold at Colorado.EDU
Thu Mar 14 12:33:34 MST 2002
My 2 cents; for the most part I would agree with Bear about some of this
stuff, but the domain difference for Chris's task is somewhat different,
even though all parties mention industry.
The course work assigned at universities *is* a throw-away task; and
rightfully so. Typically those assignments do not deal with a 'real-world'
task, except in the most abstract sense. The goal at the university is to
teach budding programmers a new approach to a particular task, where the new
approach is usally only *part* of the task, not necessarily an entire design
process (how many courses actually teach a debugging/testing methodology
course at the undergraduate level?).
The amount of time it takes to develop serious, real-world solutions is
not appropriate to coursework as a rule, because you are being handed
brand-new material, and given two weeks to get it done, for a grade. This
means 1) learning how the algorithm ought to work, 2) discovering that how
you have been thinking about it is wrong, once you start writing code 3)
fixing all of the code you have already written, once you discover the
difference. Not altogether different from actual paid work, of course, but
keep in mind the average length of a programming assignment is about 20
hours, even for easy ones, for one reason or another (Which is why I usually
allot 40 hours for each assignment :).) Multiply that by 3 courses, all on
*separate* topics, and I can understand why someone might take the brute
force approach if it looks like it will take less time to code it; typically
*professors* don't care about efficiency, so long as the assignment appears
to work correctly.
Industry certainly cares about efficiency, at least to a certain extent,
but many of Bear's examples seem to indicate that even industry is less
worried about the trade-off of efficiency versus getting it done (at least
for initial solutions) than the posts here have indicated (why else would
you put up with processes which ought to be quick and are instead slow, for
any length of time?). And how often have we heard on this list about
supervisor X who isn't interested in investing even the small amount of time
necessary to make things efficient: the product release deadline is coming
up quickly, and the code needs to work; you can always patch it later to
make it fast, once customers have paid for it (whether that's true or not is
another question :) ).
For real-world work, it's usually the case that you understand something
about the domain you are working in; typically in class you don't have a
clue as to what the dataset is really about, or what it looks like, or why
alogrithm X is really a better approach than Y to the dataset, because you
only have foggy notion of what Y does, much less X. It rather quickly
depends on your experience level with the class of algorithms you might need
Really being able to use alogrithms and abstract to new ones is a matter of
experience (Chris's level of experience aside); if you have written
algorithm X 100 times, then you tend to have a rather intimate feel for what
is going on. If algorithm Y is an extension to X, than it's true that
'learning' Y is not altogether difficult, and shouldn't take much time.
But, suppose I asked someone who only understands how decision trees work
for machine learning to write the code for a support-vector machine. These
are *radically* different approaches to machine learning, and the SVM
solution is really quite difficult to understand, except in a very general
sense (even for some AI professors I know). It requires knowing a lot about
the data set, and what parameters might be important, and how to measure
them (common to both), but decision trees use a relatively simple notion for
making decisions about values; SVMs require an advanced mathematical
understanding of the topology of the problem surface. If you happen to know
a lot about math, or a lot about float optimizations, than perhaps its
easier, but if you are in a class in machine learning, and are asked to
implement a SVM, *without* the math background, than learning becomes much
harder. Perhaps it would be better to skip optimizing for speed, and just
'get it done'.
> This is one of my sore spots - the "savings" in using an inefficient
> algorithm are rarely worth it unless you are absolutely certain that
> the problem size is limited. The more efficient algorithms are not
> that much more difficult to learn or use, and learning to use them
> now will serve you well in the future.
Again, I think this is an experience issue. More efficient algorithms are
easier to learn *if* you have experience with the efficient algorithms.
Chris is trying to *learn* new information; is it a good idea in that
setting to try to learn even more, if you are under a time crunch?
> P.S., anyone else interested in a citizen initiative to make
> teaching bubble sorts a capital offense? Quick sorts are easier
> to teach, easier to code, and much more efficient. ("Find a pivot
> value. Walk through the array with two pointers (one from each
> end) and swapping the first value above the pivot value with the
> last point below the pivot value. Stop when the pointers meet,
> repeat on left and right subarray.)
This is easier than:
1. Look at an item in a list.
2. If it's bigger/less than the item above it, move it up.
3. Keep doing that to the end of the list
?!?! It's only easier if recursion makes sense to you, and you are used to
dealing with pointers; quicksort gets taught as the second programming
course, and I am not convinced that someone relatively new to programming is
clear on either of those two issues.
Certainly quicksort is more efficient, but as I recall, qsort gets terrible
actual performance when the data set is small (and when the data is near
sorted already, but I am am not sure about that). In those cases I seem to
recall that one of the other sort algorithms is a better choice. So if the
dataset is small, efficency argues against qsort (and personally, I can
write and test a bubblesort quicker than I can quicksort).
Still, bubblesort on 4000 items seems a bit, well, silly.
> Of course this is always a balancing act. But when you're doing
> initial development the full cost of a decent algorithm is usually
Hmmm, only if the code is being run a lot, right? You examples above are
good because they have to be run frequently. Course assignments are run
once, maybe twice. The initial development cost can't be easily measured
when the 'decent' algorithm only gets used once. I still think that one-off
assignments probably aren't worth investing huge amounts of design time, if
your scheduling algorithm is "get this done, because as soon as it is done,
I have to work on X, and study for Y, and make some money so I can pay my
tuition". If you have hit upon an easy-to-write, brute force approach, than
perhaps it is better to go with that, rather than invest the time on an
elegant approach (although you should probably keep in mind runtimes even
for that one run).
> > It *is* done, though.
> No it's not. Can you use this program to solve problems?
Sure, he can. He just needs 24 hours or so, unless the data set is small,
in which case it runs in a few minutes :). What I think you mean is "can
you use this program to solve problems *efficiently*?" I think Chris would
agree that, no, it couldn't. But, efficiency is secondary for course work,
> If we were in industry and you reported to me, my first question
> would be how you know that the program is making any progress?
> Do you have *ANY* demonstrable reason to believe that your program
> isn't cycling between two states? (e.g., perhaps two values in this
> problem set are equal but your code assumes that a strict ordering
> is defined.)
And his response would be, well, it works on small sets, so it does
something correctly. Does it work on large sets... In any case, how does
that relate to using a better algorithm? What if the more efficent
algorithm simply has a bug? As you say, the literature is littered with...
If I heard about a more efficient algorithm, but didn't know that it was
extremely sensitive to the test size, would I have been better off using it
instead of the brute force solution? What if their performance converges?
Remember: these *are* one off tasks, and if finding the more elegant
solution means stepping into a library and doing a whole bunch of research,
well, I have suspicion that maybe it isn't usually worth it.
> There's countless
> production code with pointer errors or bad calls to free() that
> still manage to work with small data sets, but break when you have
> more data.
Just as there are lots of examples where the elegant solution has bugs,
which break, etc. .
> If your program is still running after 15 hours, my gut reaction is
> that it's probably due to a coding error. It *might* be due to
> an inefficient algorithm, but that's not the first place I look unless
> the code has been rigorously tested. (Think white-box coding that
> you can prove exercises every code branch, not a couple small data
Hmmm... Who has time in a course to test *every* possible code branch?
Obscure bugs are probably not going to be tested by the professor, either.
Coursework is about getting the general idea, not necessarily getting the
*best* solution. You tend to error check what you *need* to, not what you
*ought* to, and how many times does actual performance nearly require that
very little actual testing goes on? I work with a speech recognition system
that the author admits has very little error code. His explanation is that
the system already runs 7 times real time; if there is an error, he would
*rather* it seg fault and quit, rather than keep running, or print error
messages; error-checking becomes an expensive overhead problem (of course,
this is probably not true for many systems, but it is a useful example).
> How will you learn? Your professor or TA can make a few comments
> on your code, but how much industry experience do they have? Post
> your code here and you could learn what we care about in the real
Chris, play fair here. You can't call for help, even on only a related
question, and not expect a bunch of programmers to want to see. Besides, if
you ever *do* need to use the algorithm again, you will have learned how to
fix it. And I wouldn't mind seeing it because frankly, I suck, you are a
generally better programmer than I am, and I would like to see other
mistakes, so that I don't make them.
> And what lesson(s) did you learn? Seriously. The lesson you learned
> may not be the lesson we think you should have learned! >:-)
The only one that really matters here, which is try to allocate time better
(if possible) in case things blow up. Do we truely (sp?) believe that Chris
*can't* figure out when to use a better algorithm? I don't. Was he being
lazy? Maybe, but again, coursework is about doing what works, not
necessarily the optimal solution.
By way of illustration I just wrote some networking code for a class that
takes upwards of 40 minutes to transfer a 2 MB file. Is that reasonable?
No. Do I have any idea why it takes so long? No. Have I looked at the
code since turning it in to find out why? No, because I am overloaded. Do
I intend to? Yes, because it irritates me. Does the code accomplish the
transfer? Yes, even under severe packet loss conditions (upwards of 90%
loss, induced by deliberate packet dropping to simulate the conditions).
Are there better ways of doing it? Yes, I am sure there are, but I *don't*
have the time to find out about them. Does it correctly implement 3
reliable protocols over UDP (don't ask, it was part of the assingment), to
specification? Yes. Should I have considered better algorithms, when they
are not readily available, when doing so might mean 1) failing a database
test, which I *need* to graduate; not accomplishing group work in User
Interfaces, thus screwing my partners; blow off reading and homework in a
linguistics grammar course that details a linguistic grammar formalism that
happens to be one of the major natural language parsing approaches in the
industry; not complete the 20 hours of research work that is paying my way
through graduate school? My answer to this last is obvious; I think that
Chris, like me, is pursuing dual degrees in two separate, unrelated fields,
and struggling to integrate them in a meaningful way, more or less without
help. Do I believe that he does not understand the value of a good design
I guess my point here is that some of the responses seem to berate Chris for
poor design decisions, without paying attention to the fact that he is not
in an industry job, where efficiency really is a concern, and that (as most
of you probably remember), the academic world really does pull you in
multiple directions, in a way that an industry job generally doesn't (except
for some of the consultants, I would imagine).
So, give him a break. BTW, does anyone want to look at my code, and tell my
where it sucks? :)
More information about the LUG