> "write stupid code that uses smart objects".
Writing stupid code is actually really difficult.
For me, it takes a little bit of iterating before I know just the right place to insert stupid.
Rob Pike’s Rules of Programming (1989)
11–20 of 332 posts
Re: Rob Pike’s Rules of Programming (1989)
#12Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
I would not read these rules as anything like suggesting to write O(n^2) code. I think at best I'd read them as favoring O(n) instead of (1) for small n, but I really think that "fancy" algorithms in this case doesn't mean obvious optimizations like this.
If you can't guarantee n is small, I think it is entirely sensible to use a dictionary/hash table instead of looping over an array or list. As long as n is small the overhead is probably irrelevant, and it'll prevent surprises if n gets large as you said. And if the difference actually matters, you get back to rule 1 and 2 and measure first anyway.
Re: Rob Pike’s Rules of Programming (1989)
#13"Write stupid code that uses smart objects" That's a good one. It's amazing how much complexity can be created by using the wrong abstractions.
FWIW I find this is especially important for compilers and interpreters.
It's not an exaggeration to say that such programs are basically big data structures, full of compromises to accomodate the algorithms you need to run on them.
For example LLVM IR is just a big data structure. Lattner has been saying for awhile that a major design mistake in Clang is not to have its own IR (in the talks on the new MLIR project).
SSA is data structure with some invariants that make a bunch of algorithms easier to write (and I think it improves their computational complexity over naive algorithms in several cases)
----
In Oil I used a DSL to describe an elaborate data structure that describes all of shell:
What is Zephyr ASDL? http://www.oilshell.org/blog/2016/12/11.html
https://www.oilshell.org/release/0.8.pre9/source-code.wwz/fr...
I added some nice properties that algebraic data types in some language don't have, e.g. variants are "first class" unlike in Rust.
Related: I noticed recently that Rust IDE support has a related DSL for its data structure representation: https://internals.rust-lang.org/t/announcement-simple-produc...
Re: Rob Pike’s Rules of Programming (1989)
#14Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
Using array based data structures also get you more cache hits. For smaller data sets, this may well be faster than a fancy algorithm.
Re: Rob Pike’s Rules of Programming (1989)
#15Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
It depends. If you don't need to worry about performance, then it will work. But in some performance-dependent situations, the brute force algorithm will win over the hash table, and the only way to know is measuring which one is better.
Re: Rob Pike’s Rules of Programming (1989)
#16Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
If it's fairly easy, then I think it still fits the spirit of the rules. KISS and all.
On the other hand, the idea that one might be setting traps is slightly weird... if you _know_ 90% that n will be large then pick an algorithm that's efficient (and since it's easy to implement, it's a win-win). If n is always going to be small, then does the choice really matter?
Re: Rob Pike’s Rules of Programming (1989)
#17In The Mythical Man Month Fred Brooks said "Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowchart; it'll be obvious." I first read that on Guy Steele's site: http://www.dreamsongs.com/ObjectsHaveNotFailedNarr.html
>I first read that on Guy Steele's site.
It isn't Guy Steele's website. That page was written by him but the website is owned by Richard P Gabriel.
Re: Rob Pike’s Rules of Programming (1989)
#18Am I wrong to avoid writing O(n^2) code if at all possible when it is fairly easy to use hash tables for a better time complexity? Sure when n is small the O(n^2) one will be faster but when n is small /anything/ you do is fast in absolute terms so I'm trying to not leave traps in my code just waiting for n to get bigger than initially expected.
Yes. If you don't measure, you will never know when the time complexity moves in your favor due to the constant, and other factors. For example, quicksort moves to a O(n^2) algorithm (insertion sort) for the last few iterations of a branch of work(typically n=1000) because this reduces the total sort time.
Re: Rob Pike’s Rules of Programming (1989)
#19A quote from one of our founders that I've always liked:
If you make an optimization that was not at a bottleneck, you did not make an optimization.
Re: Rob Pike’s Rules of Programming (1989)
#20In The Mythical Man Month Fred Brooks said "Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowchart; it'll be obvious." I first read that on Guy Steele's site: http://www.dreamsongs.com/ObjectsHaveNotFailedNarr.html
[deleted]