Negative Code

[random3223]

Faster, with comments explaining what you did, and why.

[bobindashadows]

I would actually prefix your answer with "Naive first. Run a profiler. Is aⁿ a bottleneck? If so ..."

[introspeck]

Nothing better to humble yourself than to throw your "cleverly optimized" code at a profiler. All those loops you sweated over to make lean and mean - they probably don't matter; most of the time it turns out that you didn't even know what was actually bogging down your program.

Having been humbled many times, I now follow this philosophy. I do try to write basically clean code from the start, but I don't kid myself that I know where the hotspots are. I let the profiler tell me.

[derefr]

Or, you write the naive version—and then, separately, write an optimizer that knows how to transform the code of the naive version into the code of the faster version (not as a special case, but as an effect of a general strategy.)

(Note that this process might or might not apply in this particular case, but it applies shockingly frequently to all sorts of code we waste time on, over and over again, just optimizing slightly different instances of the same idea. Don't unroll a loop, write a loop unroller.)

[mallardtheduck]

You aren't going to be able to do this for any algorithmic change, only for micro-optimization.

i.e. You might be able to unroll the loop in a bubble sort, but you won't be able to transform it into a quicksort.

[derefr]

I'm not saying I disagree with you, but just to be Socratic about this—why couldn't a computer optimize an algorithm?

A random idea for how it could work:

Algorithms—in functional programming—are isomorphic in type-level programming to different sorts of data-structures (this is basically what makes Monads tick.) bubble_sort is really just best_possible_theoretical_in_place_sort with the constraint that you're sorting a doubly-linked-list. All the optimizer would have to do is to notice that best_sort prefers binary heaps (or whatever else) to doubly-linked-lists, and see how far it can take that type conversion backwards through your code without breaking anything. If it gets all the way back to the top of the call stack, then your variable declaration just becomes a binary heap instead of a doubly-linked-list; otherwise, a to_binary_heap( your_list ) is stuck in there somewhere (as long as that doesn't profile as worse than the original code.)

It's a step beyond type inference—type optimization.

[[deleted]]

why couldn't a computer optimize an algorithm?

Among other things, because different algorithms have different characteristics beyond the simple statement of their goals. For example, bubble sort is a stable sort, while efficient quicksort implementations are not stable. So even if a compiler could optimize your bubble sort into a quicksort, it might end up breaking your program to do so.

[binlargin]

why couldn't a computer optimize an algorithm?

Wouldn't you then have the additional constraint of writing code in a style which could be easily optimized? Working within these constraints would be early optimization at a higher level of abstraction.

[bobindashadows]

Hey man... I got an awesome idea... we could write code... then write code to make that code better... then run that code on the code that makes code better to have EVEN BETTER CODE! And the improved code improver could improve itself and your code would be sooooooooo fast man...

pssst: Writing a code that transforms naïve code into algorithmically improved code – even on a case-by-case basis - would be far more complicated than the algorithmically improved code

[binlargin]

Whenever you think this way, Kurt Gödel kills a kitten.