3 ms·
Algorithm analysis. Similar to my other post, I've gotten speed ups on the order of 100x or more by changing the algorithms used to accomplish the same work. On
by Jtsummers 8y ago
Algorithm analysis. Similar to my other post, I've gotten speed ups on the order of 100x or more by changing the algorithms used to accomplish the same work. One example was a data analysis tool, the original author wrote a correct (produced the right stuff) but naive implementation. It took about 3 minutes to perform its work, I got it below 5 seconds without being clever (read: hard to read/write, but fast). I changed the order of some of the data processing, and switched to a smarter data structure (built-in hashmap versus whatever he'd chosen). The final version was readable and maintainable by non-CS folks (it was used by engineers, mostly).
I knew of optimal sorting networks which let me optimize a hotspot in an embedded system and improve throughput in a real-time system. It seems like a miniscule savings (versus whatever sort they'd used before, insertion I think) since it was only a handful of items. But its execution time was one of the dominating factors in the system, and reducing the number of comparisons and branches to a minimum was a significant improvement.
Familiarity with declarative languages like Prolog informed the design of data analysis tools (that could've been done better in Prolog but that wasn't an option). So I wrote a specialized program that, internally, was halfway to being a Prolog implementation.
Parsing. I've not written any compilers, but I have needed custom parsers over the years. Understanding the difference between different types of languages (regular versus context-free in particular) meant I could choose the right tools for the job. Additionally, understanding what needs to be done in a parser leads to better structuring of the code.
Programming language theory. You don't need real, formal theory here, but if you understand how ideas map between languages and what some languages excel at (compared to others), you can write idiomatic code in more languages. Versus my predecessors, who could "write Fortran in any language". You can also understand the tradeoffs between the different kinds of languages (why do people support OO, FP, and others; why do they choose each). Additionally, you can borrow ideas from some languages and import them into others, with some care.
Understanding abstraction, which I'll admit was generally not taught well in my program, I got it more from my math background. This can lead to generic code and programs that operate on a wider variety of problems and data types.