3 ms·
When I was doing my PhD in hydrology modeling, I found a bubble sort in one of our pre-processing programs, which calculated the topographic flow network. This
by avidphantasm 3y ago
When I was doing my PhD in hydrology modeling, I found a bubble sort in one of our pre-processing programs, which calculated the topographic flow network. This worked okay when the watersheds being modeled were small or the grid resolution was coarse. I however, was modeling at much finer resolution (3m^2) resulting in runtimes of more than an hour. I replaced the bubble sort with merge sort from libc and my runtimes fell to less than 5 minutes. Fun times.
- tombert 3y agoTangential, but in my Java class recently I was teaching teaching the students some basic Big O stuff. I wrote a few versions of a program that found the "biggest delta" of two numbers in a list. The first version was O(n^2) time, the next version was just O(n). I showed them how long it took to run the O(n^2) on 100000 elements, about two minutes on my beefy server. Then I showed them the O(n) version running on my comparatively weaker laptop, and it took about ten seconds to run a million elements. The students were genuinely kind of impressed, and I stressed the point to say that "these are the kind of numbers that make it important to take theory seriously."
- saagarjha 3y agoO(n) for 1 million elements taking ten seconds is pretty long. What’s the constant factor?