Schwartzian Transform

I like the Arc idiom for this. Here's how to sort a list (say of stories) by some computed value (say a function called score):

  (sort (compute > score) stories)

If score is expensive, you just wrap it in memo:

  (sort (compare > (memo score)) stories)

Now it will compute each score once, save them in a table, and throw the table away when done.

A possibly counterintuitive case where "the key...is expensive to compute" can be when accessing the key just requires following a pointer to something not in cache. It's not the same thing syntactically, but, for example, Postgres sped up collation by packing bytes into integers:

http://pgeoghegan.blogspot.com/2015/01/abbreviated-keys-expl...

I've also seen speedups sorting strings by first sorting prefixes of them packed into uint64s (rather than sorting pointer/length references to string data), and in an application where a friend needed to sort a lot of indices into an array, it turned out to greatly speed the sort (by avoiding indirections) to copy the whole array, sort the indices and the copy of the array together, then toss out the copy.

tl/dr, a sort optimization: avoid recomputing the sort keys by temporarily associating them with the input items.

Wouldn't it be embarrassing to have one's name in the title of a long winded Wikipedia article for a super simple and obvious optimization.