Experience != Knowledge

By Shamus Posted Friday Sep 29, 2006

Filed under: Personal 23 comments

Steven was talking about computer-science education and computer sorting systems yesterday. This subject made my brain tingle for a number of reasons, not the least of which is that he likened the game of solitaire to a sort algorithm with very specific restrictions. I must resist the urge to turn my blog into a morass of code theory and C++ snippets that would interest only me, but this is a very interesting idea

On the subject of Computer Science education, he says:

The first volume of that series was a textbook for one of my classes; I think it was my “Data Structures” course. (Which was the single most useful CS course I took in my entire college experience, since it taught me about linked lists, stacks, queues, and also, it turns out, about recursive descent parsers. All of which I’ve used heavily ever since.)

I’ve mentioned before that I program for a living, but I have no formal education. Steven mentions “linked lists”, which is a programming technique for dealing with lists of things where you don’t know ahead of time how many things you’ll be dealing with. You may need three, or three thousand. Linked lists are easy to implement, although they have several drawbacks I won’t list here because of the damage your face would sustain when it hit the keyboard at the onset of deep-REM sleep.

Since I was not formally educated, I was never taught linked lists. I was a programmer for several years before I even saw one. When I did, I told my boss (who had written the bit of code I was reading) that I thought it was pretty slick; I thought it was his idea. Then he explained linked lists to me, and I learned that they were a very common technique. Oops. Heh. I still have odd gaps like this in my knowledge.

For contrast, I have a cousin who took the other route. He was educated at CMU. He stayed with our family for a time after graduation, and we talked programming quite a bit. It was obvious that he was the better coder by far. I was still cutting my teeth on vanilla C, and he had several languages under his belt. He was faster at coding, better at debugging, better at understanding the limits of the hardware he was working with, and better at designing software in his head. I started to get pretty scared – if this is what all programmers were like coming out of college, then the chances of me landing a job were pretty slim.

(This was both true and false. All programmers were not like my cousin, who was naturally talented and had a passion for coding, and who went to a fairly impressive college. However, is was true that my chances of getting a job were slim. Not because of the knowledge deficit on my part, but because people want to hire coders with degrees. I assumed employers knew how to tell a good coder from a bad one. They don’t. But they can tell someone who has a degree from someone who doesn’t. Even when comparing two candidates with degrees, they can usually tell who has the most expensive education.)

At one point we were talking about sorting techniques. Suddenly my cousin blurted out that bubble sort was a stupid sorting system and there was no justification for using it, ever. I wasn’t holding a CS degree, but I was smart enough to identify dogma when I saw it. I pressed him on this point, which he believed with great conviction but little evidence.

“Bubble sort” is a technique of sorting stuff – any kind of data in the computer – that is easy to understand, but quite slow in implementation. It’s a sort of brute-force approach. I’ve heard it said that it is the slowest, although I’ve never sat down and tried to prove that for myself.

Anyway, my cousin was obviously just repeating some nonsense that an instructor had pounded into his head. “Bubble sort was the slowest, therefore it was the worst and should never be used.” I pointed out the Tetris clone I was working on (which floated around on various BBS systems for a number of years) and that bubble sort was a perfectly acceptable way of dealing with the high score list. He countered, saying that it was very slow, and I could speed up performance of the sorting algorithm many, many times by simply using a less stone-age method of sorting. I pointed out that I was sorting a list of 10 names. Even on the decrepit 8mhz machine I was using, the sort was instant. If I made it a list of the top 100 names, I’m sure it would still have been instant. If I made the sort ten times faster, the user would not be able to tell the difference. There was simply no justification for optimizing the thing.

This was a heartening moment for me. It showed me that while formal education was valuable, it could never take the place of experience. A seasoned programmer would not go around spouting absolutes like this. They would know better. Idealogical purity is one of the first things out of the window when trying to accomplish something instead of learning to accomplish something.

Classroom assignments almost never capture the chaos and uncertainty of the real world. If it did, students would go crazy. Imagine an instructor that gave a lengthy coding assignment, and then every day for the next week he would change some of the goals of the assignment. Once he saw a working prototype, he would inform them that while they gave him what he asked for, it still wasn’t what he really wanted, and he would change the requirements again. Let’s also assume that even though the students had to start over many times, the instructor never altered the original due date. This is the world of professional coding, and no professor could teach it without getting lynched.

It’s a shame that higher education works the way it does. Colleges are great at taking an established body of knowledge and distilling it into courses and curriculum. This works well as long as the body of knowledge isn’t changing too fast. CS changes at a shocking pace, and it’s hard for educators to keep up. Heck, it’s hard for those of us working in the field to keep up. How much harder is it for teachers who are trying to teach what they know, instead of fighting to learn new things! College is a very expensive way to gain knowledge, although there are clearly gems of learning in there that are difficult to learn by other means. The most difficult part of filling in the gaps in my self-taught knowledge is that I don’t know where the gaps are.

 


From The Archives:
 

23 thoughts on “Experience != Knowledge

  1. the funny thing is that when i read steven’s post, immediately what went through my mind was “Bubble Sort!”

    This is because my dorm friends who majored in CS at University of Wisconsin Madison were all – to put it mildly – sort-fiends. The relative merits of bubble sort were debated hotly. There were bubble sort partisans. There were absolute foes of bubble sort. The arguments for and against bubble sort included speed, but also aesthetics, logic, math, and The Right Way to Do It-ism. (Kind of rmeinded me of the Apple vs PC wars, but thats another matter). In fact I was so indoctrinated about bubble sort that to be honest I couldn’t name another type of sort to save my life. I am bubble sort scarred. There is no sort but Bubble Sort and I am its prophet. Bubble Sort Akhbar! Stop me before I bubble sort again.

  2. I kid you not but on a private forum run by my college friends we actually had a whole thread and debate on bubble sort. Here was my humble contribution to the debate.

    I am a new convert to Bubble Sort. Bubble Sort is the greatest sorting algorithm known to man. I love Bubble Sort. When Howard Dean is elected president, Bubble Sort shall be the only sort approved for government use.

    Bubble Sort has many real-life applications. For example, in Homeland Security. You can use Bubble Sort to rank security threats, by sorting on the beard length of travelers standing in line (the benefits of an in-place sort are obvious in this context). Given what we know from the 911 hijackers, those with the shortest/nonexistent beards are clearly the highest risk.

    But Bubble Sort can be justified on the merits – for example, we know that in computing, these three laws hold:

    Moore’s Law: CPUs get faster.
    Some Other Law: RAM gets faster too, but not as quickly.
    Yet Another Law: Disk I/O is always a bottleneck.

    From these three laws, it is clear that any sorting method that requires large amounts of RAM beyond the array holding the data to be sorted is at a disadvantage. Bubble Sort is clearly aligned with these fundamental laws and therefore is best-positioned to serve our robot overlord masters.

    Bubble Sort has been accused of being sub-optimal for data that is sorted backwards from the desired order. This is vile un-American slander. In such cases, running Bubble Sort backwards solves the problem! Running two instances of Bubble Sort, one forwards, one backwards, on the data minimizes the extra RAM needed to sort and then you simply take the output of whichever sort finishes first.

    Any argument against Bubble Sort based solely on speed is perilously and treasonously flawed. With Moore’s Law, CPU speeds will increase. The statistical likelihood is that there someday will be CPUs that can run your Bubble Sort faster than the radix sort on current hardware. Therefore, there is no reason not to use Bubble Sort.

    I may be rightly accused of threadjacking your point awya from “experience vs education” and towards explict dogma of precisely the kind (though of opposite polarity) which you decried. But I cant help it. This is because Bubble Sort will run for president in 2008 and bring peace to the middle east.

    Though, Bubble Sort does pale to Trash Sort (rm -fr). And Random Sort is kind of sexy, but how do you know when to stop?

  3. Skeeve the Impossible says:

    You know I started to read your post, but then I past out from being so damn bored. and then I woke up in a pile of my own fecies…..so from this
    “experiance” I gained the “knowledge” that you suck much like human excrement

    Impossible out

  4. Shamus says:

    Fledge: That is great stuff. I guess this is another thing I missed out on when I didn’t go to college. I missed out on joining a faction and trying to convert the heathens to my cause.

    Yea, once I have brought the wayward into the fold, and we agree on bubble sort, then the elect will sit down and write some bubble sort code:

    bubble_sort ()

    Then some freshman will come in and nail his thesis to the door of the room where we keep the server, pointing out that clearly we should name our functions:

    BubbleSort ()

    There will be fighting, and perhaps some bloodshed. Pretty soon the freashman and his followers will suffer another division: Some of them think it should be implemented as a class:

    CBubble::Sort ()

    And THEN the fighting begins in earnest.

  5. Shamus says:

    Also: The “sorting threats by beard length” is hilarious. :)

  6. hank says:

    I feel like I just walked into the room in the middle of a very awkward pause.

    I’m not a programmer by training, so there are huge gaps in what I know. (But I, too, have been warned of the perils of bubble-sort.) I love programming waaaay too much to mess everything up by going to school to study it. University trained me to be an electrical engineer, gave me the paper that said I could do the job, and I *can* do the job… but I don’t want to anymore. I don’t want the same thing to happen with programming.

  7. Mark says:

    Data structures was the second programming class I ever took, and it nearly drove me mad. A friend and I used to joke that the class used to make us feel like the apes in 2001. Much humorous mimicking of apes ensued. By the end of the semester, I pretty much had a handle on it, but it was rough.

    As for education vs experience, you are, of course, right. However, formal education does attempt to simulate the frustration of professional coding. In my first programming class, the teacher would grade us according to standards we did not know about (for example, he would take points off for algorithm efficiency, something we didn’t know even existed – or how to measure). This was frustrating to no end, but we ended up being better programmers because of the experience. Another formal education experience was writing an Operating System. Of course, we started small and built it up slowly during the entire semester. Naturally, the elegant recursive solution I came up with during the first few revisions was obliterated by cruft as the semester wore on and the prof kept assigning new functionality – I later learned that the class was designed to do this to us.

    Neither of these examples is a substitute for real experience, but they certainly were frustrating. Perhaps not as frustrating as a real life project, but hey, I was in college:P

  8. MOM says:

    one of my favorite posts ever. Your readers are histerical. And funny.

  9. BeckoningChasm says:

    This is an excellent post. I have a degree in fine art, but have never worked in that capacity (a fine arts degree is a gateway to the busboy job market). But the creativity I was able to develope in art has served me very well in the jobs I’ve had, since I was able to see past the “this is how I learned it” bit.

  10. Bogan the Mighty says:

    Oh god. Too much stuff for my brain to compute yet because college has yet to allow me to move on to the point of bubble sort. Actually I just got yelled at for doing the next step in my C++ class of making a while loop…even for me that’s simple. So be glad Shamus that you got to teach yourself and realize most of what a teacher says is crap and you didn’t have to worry about it. By the way know anything about assembly?

  11. Will says:

    It’s times like this when I wish I knew more about the coding world beyond MATLAB scripts and basic LISP functions.

    (setq understanding 0)

  12. Will:

    function [R] = bubblesort(R)
    % bubblesort.m
    % Exchange selection sort of array R
    %
    % B1. Initialize BOUND
    BOUND = length(R);
    %
    % B2. Loop on j
    while (BOUND>1)
    t = 0;
    for j = 1:BOUND-1
    %
    % B3. Compare/exchange R(j):R(j+1)
    if (R(j)>R(j+1))
    temp = R(j);
    R(j) = R(j+1);
    R(j+1) = temp;
    t = j;
    end
    end
    %
    % B4. Reset BOUND
    BOUND = t;
    end

    (via MIT. I could have written it myself, but I’m lazy. And don’t get me started on a MATLAB vs IDL thing either.)

  13. Shamus says:

    And another link to myself, from myself. Nice one, WordPress.

  14. Will says:

    I can see where that would be time consuming for very long lists. Just thinking about implementing such a thing in AutoLISP gives me a headache.

  15. Pete Zaitcev says:

    I knew a guy who wrote an multi-user, multi-task OS (kernel, libraries, utilities, including assembler and linker), Fortran 77 toolchain with IDE, and SQL database (full SQL, not a subset). He said that Knuth was a “silly guy” who “wrote trivialities in thick volumes”.

    I got my data structure education from Wirth, who neatly compressed all that a person needs to know into a handy volume, with algorithms in pseudo-pascal. I also happen to think that Wirth retarded the development of computer programming as an engineering discipline possibly by decates, just because a whole generation was corrupt by arrays as part of type, wrong indirection of pointer type, nested procedures, and other retarded concepts which he invented and promoted.

    On the subject of hive mind in blog comments, my first thoughts when I saw SDB’s post (and now yours) was, “But qsort is not stable! It totally sucks for all practical applications!” Programmers who use qsort to sort columns in iTunes-like application are in a dire need of orange-hot branding iron applied to their bellies.

  16. Heather says:

    I feel like I just walked in on a /. post discussion, except there are no trolls telling everyone they should get Macs/Linux because if you did then Python would solve everything…or something like. Bubblesort, anything like bubblewrap? Pop, pop-pop, takes plenty of time to pop all those bubbles. I shall now wander back over to the homeschool sites where they discuss things I get, like Charlotte Mason vs. Classical education.

  17. AndrewNZachsDad says:

    “…the damage your face would sustain when it hit the keyboard at the onset of deep-REM sleep.”
    OMG, the fact that you can make me laugh like that in a blog about programming (which I love as a hobby but still can be put to sleep by) is why I love this cotton-pickin’ site so much.
    Keep it up, Shamus.

  18. Miako says:

    … I had that professor.

    Bubble sort rocks for the same reason that Java does. Easy to implement.

    I pity the fool who doesn’t use STL

  19. Sewerman says:

    And actually, Bubble sort isn’t the worst sorting algorithm in terms of speed..

    Chalk this up as a case of Ideology vs. Actual working experience…

    I had a professor who claimed Radix Sort was worse (sparing technical details unless asked). Rather than leave it at that, he designed an experiment: Bubble sort vs Radix sort- a timed trial over similar (and similarly arranged) data sets.

    Radix sort performed worse over his set. Now granted, it was designed that way, but given our Universe of data, who is to say how frequent such data sets were.

    Moral upshot: Take what you hear and try it out. Most profs are heavy on theory and light on experience. And, its fun to throw their wrong assumptions back into their smug, overly paid faces.

  20. John says:

    OK, I’m weighing in on the holy war, with the caveat that I’m still a first year undergrad and so nothing I say matters. As you may have predicted, I am a rabid bubble sort hater.

    First off, I’m pretty sure bubble sort /would/ outperform radix sort on the right (wrong) data sets. Radix sort is an algorithm designed for a very specific situation – it sorts in linear time, but the coefficients involved are very large. In practice, that means for sufficiently large lists it’s going to beat out more or less every other sorting algorithm, but if the array is small enough that bubble sort works in a reasonably short time then things are going to go very wrong. So I think it’s inaccurate to call radix sort worse than bubble sort in general in terms of speed.

    As for the high-score list, if I was doing it I’d probably have used insertion sort. It’s easier to implement than bubble sort because it’s a more intuitive algorithm, and the code is easier to understand at a glance. Plus it’s faster and more elegant, which – despite being irrelevant in practical terms – would give me a warm fuzzy feeling deep down inside.

    (Also, insertion sort is (AFAIK) the fastest known sorting algorithm for really small input sizes, so it’s useful as a base case for highly optimised implementations of recursive sorts like quicksort/merge sort. So it’s actually useful in other contexts, while bubble sort isn’t – in terms of learning a simple sorting algorithm, it makes more sense to learn insertion sort than bubble sort.)

    But bubble-sort isn’t really the /worst/ sorting algorithm either. I think that title goes to bogo-sort. What you do is, you randomly permute the array, then you check whether it’s in order. If it’s not, you do it again. And again. And again… (The irony is that coding a decent RNG is far harder than bashing out a sorting algorithm!)

    Also, Python is awesome. And it will solve all your problems. :-)

  21. Michael Church says:

    Bubble sort is O(n^2), compared to the “good” O(n*log n) sorts like merge sort. Quick sort is usually O(n*log n) but O(n^2) is the worst case.

    Bubble sort is the most “obvious” sort if you’re sorting a mutable array in a C-style imperative language. It’s bashed because it’s the sort that noobs usually implement when they need a sorting algorithm, but it’s inappropriate for large data sets. (If n = 10 and won’t change, who cares?) If you’re using a functional language like Haskell or Lisp, recursive sorts like merge sort and quick sort are a lot more intuitive, and easier to implement.

  22. Steve says:

    I can’t believe I’m posting this late, but WTF… If no one reads it I haven’t made a fool of myself, if they do I’m justified.

    I found this fascinating. Despite being a (fairly successful, I think) professional programmer, I have no formal education in computer science. (I have a degree, but in mathematics). Yet oddly enough, I’ve known about linked lists since way before university or work, because my early struggles with learning C were based on a shareware (and surprisingly decent, in hindsight I should find that guy and pay him some money) tutorial which covered it in the advanced module. (I didn’t have a proper compiler at the time. I had a BBC Micro with a port of Small C. If you knew C, I imagine it was a nice if constrained environment. “Wow, it’s better than I expected on such a tiny machine.”. If you didn’t know C and were trying to learn it, the limitations were confusing.)

    I also have a friend X who exemplifies the “bubble sort is bad, period” model. We used to be colleagues and I don’t think I ever wrote a line of code when we worked together without thinking “X will chew my ear off if he sees this code”. I think in practice he is more pragmatic than he would admit, but the attitude described in the article was painfully familiar.

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply

Your email address will not be published.