I assume that when computer science students go through college, they all take a required course in data structures. If I were designing a course like this, I'd make them learn how a variety of useful data structures worked. Certainly if you read a book on data structures you'll learn this sort of thing.
How many programmers actually need this information? In today's world, there are a lot of libraries out there that have a reasonable implementation of AVL tree, hash table, and B tree. Certainly some people need to learn to write these things. Why does your typical student programmer care about different ways to handle collisions when inserting into a hash table?
Okay, I'll admit that programming without this knowledge for me would feel a bit like skiing naked. It'd be a bit too weird to choose an algorithm because someone told me that I should always use AVL trees because their worst case performance and therefore their predictability in the face of ignorance is better. For me, I'd rather be able to use a sorted array to improve locality of reference even if I don't know that there's a problem anywhere. I'm sure that at least 95% of the time that I've used an immutable sorted array it hasn't made a difference. I certainly don't check with a profiler unless a real problem exists.
Every so often performance does matter, though. It sometimes matters a lot. In that case, you might say that you need a programmer who knows to check the hash tables to make sure they aren't behaving horribly. However, a decent profiler is likely to tell you a lot of useful information without having any knowledge of data structures. Since these cases are rare for typical programmers, wouldn't they be just fine if they knew a collection of data structures that they could swap in until they got something that worked better?
I can't remember many times when I've had to swap out a data structure because of performance issues. The last time was inserting into the end of a very large STL vector. The copies were too expensive due to C++'s tendency to copy things too often. (Even this case will be fixed with the next C++ standard.) Anyway, STL has some other data structures that can be used. I was able to replace my data structure and things immediately improved. I can't remember enough details to know what knowledge I needed. It's also possible that I guess correctly more often than an ignorant programmer would. Who knows how many times they might need to swap things randomly?
A C# programmer would have it even easier. The System.Collection namespace in .NET doesn't have a lot of different options. It'd be pretty easy to try all the possibilities pretty quickly. If none of the options solves the problem, it's entirely possible that there's something that could be done elsewhere.
Memory and speed performance are pretty much the only times you might care about the differences between a hash table and an AVL tree. A few years from now, application programmers may just add a bit of concurrency if they want more speed. Few web applications run low on memory. Are data structures classes useful anymore for typical programmers?
I've left a lot of unanswered questions in this post. I'm really curious about the answers. I'd love to hear from you.
[display_podcast]
With all the talk lately of bad iPod and iPhone experiences and iTunes nightmares (See here, here, and here!), I decided to share my system for managing my music and movies to hopefully ease some iTunes pain. I've shunned iTunes management in favor of simplicity. I typically manage music on an album by album basis with play lists tossed aside.
My requirements were simple:
- Keep my music away from iPod and iTunes shackles. I want the ability to buy some other player in the future if I so desire.
- Have the ability to get all my music and movies back on the iPod quickly should iTunes force me to "restore" it.
- Do this without 3rd party software. Floola and Anapod are great for older iPods, but as of this writing, neither support the newer iPod classic that I bought.
Here are the steps:
- Setup iTunes for manual management of your device. I'm using iTunes version 7.4.3.1
- Rip CDs to mp3 using 3rd party software. I like dbPowerAmp.
- Correct mp3 tags and add album art using mp3Tag.
- For movies, I use DVDFab Decrypter to convert DVD direct to mp4. (Yes, other players do support mp4)
- Save these original files to someplace safe. I don't consider the iPod to be a safe place! Use an external USB hard drive that is at least the size of your iPod.
- Now connect the iPod and start iTunes.
- Select the iPod device music or video folder ( depending on what you are planning to drag over) on the left hand menu.
- Drag and drop the files from the external USB drive to iTunes.
You can now take your iPod and external USB hard drive to any machine that you've installed iTunes on. Just follow the steps above to place your original rips on the USB drive and the "iTunes copy" on the iPod.
The best part about this plan is if something bad happens like a SYNC... Gasp!! You can drag over all the original files to get the iPod back the the original state. What do you think? Got better ways to do this?
Posted by ken
in Grab Bag
at
13:31 |
Wednesday, November 14. 2007
This topic seem to come up from time to time at work with strong feelings on both sides. This article in the New York Times discuses the increased prevalence of emoticons. I think judicious use of emoticons make a lot of sense when using low bandwidth, hastily written, prone to miscommunication medium of e-mail. A  or  can say a lot. What are your feelings on this subject?
There have been many ways to describe a common office phenomenon. Some call it a gift, others litter, but I think most apt is "Found Cake." To understand this definition, please refer to the following web comic.
Penny Arcade - It Looks Delicious
Now, coming across "found cake" on the street is one thing. I'm not sure how interested I would be in picking up that treat. In an office though, it's a treat. No one knows exactly where it comes from, they only know they got there just in time.
In fact if I'm not mistaken, there's an economic theory that the utility derived from "found cake" is inversely proportional to the amount left after you have taken your piece. In layman's terms, if you're the last person to get a piece, you ultimately end up enjoying it the most. I find this is true regardless of the size of the piece you do end up getting. Mostly because if you get the last piece, you also get the implied right to gloat to others about your feat. It's just polite.
I wonder if any "found cake" studies have been performed. I bet you they'll find that the first slice is the largest and the last slice lasts the longest. Maybe that's what we were just subjected to, a "Found Cake Study." I think in either case, it is a win / win. Free cake in the name of science. Keep the found cake coming.
I've been reading Beautiful Code. It's a fun book with chapters written by a few well-known programmers about some beautiful code that they've written or seen. They all have wildly different views on what makes code beautiful, so it's pretty entertaining. It's fun seeing what programmers I've heard of think is beautiful. Brian Kernighan, for example, wrote about some string processing code. I found that extremely entertaining and ironic. Yukihiro Matsumoto had an impressively concise description of what it takes to make beautiful code. It was refreshingly in character with the Ruby philosophy.
Most of the authors were completely unknown to me. However, even though the most obscure is more famous than me, I'm still going to tell you about some beautiful code that I run into frequently.
The Model View Controller (MVC) design pattern is, perhaps, one of the oldest out there. It's been used for almost 30 years now, and it is still an extremely clean way to divide up the responsibilities of a user interface. When I see it implemented well, it's extremely satisfying.
For those of you who grew up using Microsoft's GUI frameworks, you may have never seen this done well. .NET Forms and MFC make it difficult to implement it correctly. (In fact, this topic was inspired by me working simultaneously on a Rails and a MFC project.) Ruby on Rails, by the way, revolves around the MVC design pattern.
What's so beautiful about the pattern?
It cleanly separates three different activities. The separation is clean enough that the pattern is relatively easy to use. It's usually easy to figure out whether some functionality should go in the model, the view, or the controller.
Furthermore, even in a highly interactive GUI, the program becomes easily testable. The view is the only part that interacts directly with the user, and, other than interacting with the user, the models and controllers have all of the functionality. (This statement becomes less true if you're writing custom controls such as a text editor.) If you test the models and controllers, then you've tested a large fraction of the code.
I always smile when I see some MVC code that works well.
When I saw a colleague bring up Google Maps on his iPhone and then surf to a few other sites, I was sold. What a beautiful machine! What a beautiful display! I visualized myself never getting lost again, able to keep up with my e-mail and my research any time and any place. As soon as I got home I bought one. I didn�t even consider the 4GB model, although there were a few left � I wanted that extra storage for all the stuff I wanted to take everywhere with me.
I soon discovered that the iPhone isn�t a very good cell phone. I live in an area with marginal coverage. I get only one or (on a very good day) two bars at home. But the iPhone dropped far more calls than my old Nokia, and would drop any call if I put the phone to my ear. I had to use the speakerphone option or the headset, and I found myself contorting into comical (for observers, at least) positions in a vain attempt to catch enough signal to complete a call. I was surprised to find that I got poor voice quality even when I was out and about and showing five strong bars.
My next disappointment came when I accessed Google Maps while on an urban exploration, expecting to resolve a navigational question in a flash. The snappy response my colleague demonstrated was nowhere to be found! Without a WiFi connection, I was already miles outside of the map�s boundaries by the time it appeared on that gorgeous display. I spent so much time dinking with my iPhone and waiting for it to respond that I might as well have stayed home. I saw very little of the countryside.
When I got home, I thought I�d listen to some music. I hadn�t had a chance to load any of my music, so I just typed (slowly and laboriously) the URL of my favorite Internet radio station. All I got was a tiny icon of a box! Nothing else at all. I did some research and discovered that the iPhone does not support Flash. What? The most graphically-oriented mobile device ever introduced ignores the most common way to deliver graphical content on the Web? Unfathomable! My radio station was programmed in Flash, so I got a little box icon and no tunes.
OK, so I�ll load some of my music from my PC. Plug the iPhone into the USB port and drag my favorite songs over, right? Not a chance! You have to use iTunes. That should be quick and easy � Apple is supposed to be the most intuitive stuff out there. Well, maybe to a long-time Mac user, that program is easy to figure out, but I never did find a way to select multiple songs and port them over. If you want to �synch� your entire library, it looks pretty easy, but mine would have exceeded the iPhone�s capacity. And why would Apple assume that I want exactly the same things in both places? After about a half hour of struggling to grasp the arcane logic and puzzle out the meaning of totally uninformative icons, I figured out how to manually load a single song at a time. I had to wait for that song to finish loading before I could select another. I loaded a few favorites and gave up in disgust.
Somebody tell me, please, why the iPhone, a USB device, does not even show up as a device when you plug it into a PC. Why not let me see that drive as a drive and store whatever I want on it? It is, after all, my 8 GB of mobile drive space � why dictate to me that I can use it only for media imported by iTunes? All that space was completely useless to me unless I wanted to fill it with songs, one�.. at�.. a�. time.
There were things I liked about the iPhone. The camera, and the way photos are stored and viewed � outstanding! The way I could start the iPod feature and have my (very few) tunes with me while I worked around the house. The access to YouTube. I enjoyed those. But c�mon, it�s gotta be at least as good a phone as my old one, and it�s gotta access the Web while away from WiFi points fast enough to be useful. I mean, isn�t that when the iPhone would be most useful? When I have WiFi access, I also usually have my PC. And the iPhone should certainly unwrap that little box and display the Flash content hiding inside.
I gave up. I happily paid the restocking fee to return the iPhone and go back to using my ugly, beat-up, three-year old Nokia that hardly ever drops a call and transmits clear, understandable voice. If I want to surf the Web or get navigational help while I�m out and about, I�ll lug my laptop with a Sprint card. Those options are bulky and certainly not as beautiful, but they work! And if I want to take my tunes with me when I�m away from my laptop, I�ll buy an MP3 player� one made by anyone but Apple!
|