Algorithms to Live By

by Brian Christian

  their preferences became indistinguishable: Fung, Carstensen, and Lutz, “Influence of Time on Social Preferences.”

  older people are generally more satisfied: Evidence of improvements in emotional well-being with aging are discussed in Charles and Carstensen, “Social and Emotional Aging.”

  3. SORTING

  “Nowe if the word”: Cawdrey, A Table Alphabeticall, is the first monolingual dictionary of English. For more on the history of sorting vis-à-vis searching, see Knuth, The Art of Computer Programming, §6.2.1. For more on the invention of alphabetical order, see Daly, Contributions to a History of Alphabetization.

  The roommate pulled a sock out: Hillis, The Pattern on the Stone.

  posted to the programming website Stack Overflow: “Pair socks from a pile efficiently?” Submitted by user “amit” to Stack Overflow on January 19, 2013, http://stackoverflow.com/questions/14415881/pair-socks-from-a-pile-efficiently.

  As “amit” (real name Amit Gross, a graduate student at the Technion) writes: “Yesterday I was pairing the socks from the clean laundry, and figured out the way I was doing it is not very efficient. I was doing a naive search—picking one sock and ‘iterating’ the pile in order to find its pair. This requires iterating over n/2 × n/4 = n2/8 socks on average. As a computer scientist I was thinking what I could do?”

  Amit’s question generated a number of answers, but the one that received the most support from his fellow programmers was to do a Radix Sort: identify the dimensions along which the socks vary (e.g., color, pattern) and sort them into piles on each of these dimensions. Each sort requires only one pass through all the socks, and the result is a set of smaller piles. Even if you have to go through all the socks in those piles to find matches, the amount of time this takes is proportional to the square of the size of the largest pile rather than the square of the total number of socks. (See the endnote below about sorting a deck of cards for more on Radix Sort.)

  But if the reason we are pairing socks is to make it easier to find a pair of socks when we need them, we can reduce the need for sorting by adopting a better procedure for searching.

  Let’s say your socks differ along only one dimension—color—and you have three different colors of loose, unpaired socks in your sock drawer. Then you are guaranteed to find a matching pair if you take four socks out of the drawer at random. (To see why, imagine the worst-case scenario: each of the first three socks that have been pulled out are a different color. When you go back for a fourth, it has to match one of the three you have pulled out already.) No matter how many colors you have, taking out one more sock than the number of colors always guarantees you a matching pair. So don’t bother pairing them if you’re willing to have your morning run a little slower.

  This neat solution to the problem of pairing socks comes courtesy of the Pigeonhole Principle, a simple but powerful mathematical idea attributed to the nineteenth-century German mathematician Peter Gustave Lejeune Dirichlet. (Rittaud and Heeffer, “The Pigeonhole Principle,” traces the history of the Pigeonhole Principle, including Dirichlet as well as what appear to be even earlier references.) The idea is simple: if a group of pigeons lands in a set of nesting holes, and there are more pigeons than holes, then at least one hole must contain more than one pigeon. In computer science, the Pigeonhole Principle is used to establish basic facts about the theoretical properties of algorithms. For example, it is impossible to make an algorithm that will compress any possible file without loss of information, because there are more long files than there are short files.

  Applying the Pigeonhole Principle suggests a permanent solution to the problem of sock pairing: only buy one kind of sock. If all your socks are the same, you never need to pair them, because you can always get a pair by taking two socks out of the drawer. For many computer scientists (including some of the programmers who responded to Amit’s question) this is the most elegant approach—redefining the problem so it can be solved efficiently.

  One last word of warning, though: when you buy that one kind of sock, be careful what kind of socks you buy. The reason why Ron Rivest has particular problems with socks is that he wears socks that are different for left and right feet. This thwarts the Pigeonhole Principle—to guarantee a match with socks like that, you’ll need to pull out one more sock than the total number of pairs.

  “Socks confound me!”: Ronald Rivest, personal interview, July 25, 2013.

  “go blind and crazy”: Martin, “Counting a Nation by Electricity.”

  “unerringly as the mills of the Gods”: Ibid.

  “no one will ever use it but governments”: Quoted in Austrian, Herman Hollerith.

  Hollerith’s firm merged with several others: Austrian, Herman Hollerith.

  first code ever written for a “stored program” computer: “Written,” here, means literally written out by hand: when the renowned mathematician John von Neumann jotted down the sorting program in 1945, the computer it was meant for was still several years away from completion. Although computer programs in general date back to Ada Lovelace’s writing in 1843 on the proposed “Analytical Engine” of Charles Babbage, von Neumann’s program was the first one designed to be stored in the memory of the computer itself; earlier computing machines were meant to be guided by punch cards fed into them, or wired for specific calculations. See Knuth, “Von Neumann’s First Computer Program.”

  outsort IBM’s dedicated card-sorting machines: Ibid.

  a quarter of the computing resources of the world: Knuth, The Art of Computer Programming, p. 3.

  “unit cost of sorting, instead of falling, rises”: Hosken, “Evaluation of Sorting Methods.”

  the record for sorting a deck of cards: While we couldn’t find a video of Bradáč’s performance, there are plenty of videos online of people trying to beat it. They tend to sort cards into the four suits, and then sort the numbers within each suit. “But there is a faster way to do the trick!” urges Donald Knuth in The Art of Computer Programming: First, deal out the cards into 13 piles based on their face value (with one pile containing all the 2s, the next all the 3s, etc.). Then, after gathering up all the piles, deal the cards out into the four suits. The result will be one pile for each suit, with the cards ordered within each. This is a Radix Sort, and is related to the Bucket Sort algorithm we discuss later in the chapter. See Knuth, The Art of Computer Programming, §5.2.5.

  completely sorted by chance: Sorting things by randomizing them and hoping for the best is actually an algorithm with a name: Bogosort, part of computer science’s only partly tongue-in-cheek subfield of “pessimal algorithm design.” Pessimality is to optimality what pessimism is to optimism; pessimal algorithm designers compete to outdo each other for the worst possible computing performance.

  Looking into the matter further, pessimal algorithm designers have concluded that Bogosort is actually far too lean and efficient. Hence their “improvement” Bogobogosort, which starts by incrementally Bogosorting the first two elements, then the first three, and so forth. If at any point in time the list gets out of order, Bogobogosort starts over. So the algorithm won’t complete a sort of four cards, for instance, until it throws the first two up in the air, sees that they’ve landed correctly, then throws the first three in the air, sees that they’ve landed correctly, and at last throws the first four in the air and finds them in the correct order too. All in a row. Otherwise it starts over. One of the engineers to first write about Bogobogosort reports running it on his computer overnight and being unable to sort a list of seven items, before he finally turned off the electricity out of mercy.

  Subsequent engineers have suggested that Bogobogosort isn’t even the bottom of the well, and have proposed getting even more meta and Bogosorting the program rather than the data: randomly flipping bits in the computer memory until it just so happens to take the form of a sorting program that sorts the items. The time bounds of such a monstrosity are still being explored. The quest for pessimality continues.

  Computer s
cience has developed a shorthand: Big-O notation originated in the 1894 book Die analytische zahlentheorie by Paul Bachmann. See also Donald Knuth, The Art of Computer Programming, §1.2.11.1. Formally, we say that the runtime of an algorithm is O(f(n)) if it is less than or equal to a multiple (with a coefficient that is a positive constant) of f(n). There is also the kindred “Big-Omega” notation, with Ω(f(n)) indicating that the runtime is greater than or equal to a multiple of f(n), and “Big-Theta” notation, with Θ(f(n)) meaning the runtime is both O(f(n)) and Ω(f(n)).

  “He had me at Bubble Sort”: This engineer is Dan Siroker, whom we met earlier in chapter 2. See, e.g., “The A/B Test: Inside the Technology That’s Changing the Rules of Business,” Wired, May 2012.

  information processing began in the US censuses: For more details, see Knuth, The Art of Computer Programming, §5.5.

  to demonstrate the power of the stored-program computer: The computer was the EDVAC machine, and at the time von Neumann’s program was classified as top-secret military intelligence. See Knuth, “Von Neumann’s First Computer Program.”

  “Mergesort is as important in the history of sorting”: Katajainen and Träff, “A Meticulous Analysis of Mergesort Programs.”

  large-scale industrial sorting problems: The current records for sorting are hosted at http://sortbenchmark.org/. As of 2014, a group from Samsung holds the record for sorting the most data in a minute—a whopping 3.7 terabytes of data. That’s the equivalent of almost 37 billion playing cards, enough to fill five hundred Boeing 747s to capacity, putting Zdeněk Bradáč’s human record for sorting cards in perspective.

  167 books a minute: Says shipping manager Tony Miranda, “We will process—I think our highest is—250 totes in one hour. Our average is about 180 totes in one hour. Keep in mind, each tote has about 40-plus items inside of it.” From “KCLS AMH Tour,” November 6, 2007, https://www.youtube.com/watch?v=4fq3CWsyde4.

  85,000 a day: “Reducing operating costs,” American Libraries Magazine, August 31, 2010, http://www.americanlibrariesmagazine.org/aldirect/al-direct-september-1-2010.

  “Fuhgeddaboutit”: See Matthew Taub, “Brooklyn & Manhattan Beat Washington State in 4th Annual ‘Battle of the Book Sorters,’” Brooklyn Brief, October 29, 2014, http://brooklynbrief.com/4th-annual-battle-book-sorters-pits-brooklyn-washington-state/.

  the best we can hope to achieve: A set of n items can have precisely n! distinct orderings, so a sort produces exactly log n! bits of information, which is approximately n log n bits. Recall that n! is n × (n − 1) × … × 2 × 1, which is the product of n numbers, of which n is the largest. Consequently, n! < nn, so log n! < log nn, which then gives us log n! < n log n. This approximation of n log n for log n! is called “Stirling’s approximation,” named for eighteenth-century Scottish mathematician James Stirling. Because a single pairwise comparison yields at most one bit of information, n log n comparisons are needed to fully resolve our uncertainty about which of the n! possible orders of our n things is the right one. For more detail, see Knuth, The Art of Computer Programming, §5.3.1.

  “I know from experience”: Jordan Ho, personal interview, October 15, 2013.

  a paper on “email overload”: Whittaker and Sidner, “Email Overload.”

  “sort of wasted a part of their life”: Steve Whittaker, personal interview, November 14, 2013.

  “At a Lawn Tennis Tournament”: Dodgson, “Lawn Tennis Tournaments.”

  an awkward take on triple elimination: For a computer-scientific critique of Dodgson’s tournament proposal, see Donald Knuth’s discussion of “minimum-comparison selection” in The Art of Computer Programming, §5.3.3.

  doesn’t produce a full ordering: An algorithm that, rather than ranking all of the items, identifies one of them as the largest or second-largest or median, etc., is known as a “selection” algorithm, rather than a sorting algorithm.

  schedulers for Major League Baseball: Trick works as part of the Sports Scheduling Group, which he co-founded. From 1981 to 2004, the schedule for Major League Baseball was constructed by hand, by the remarkable husband-and-wife team of Henry and Holly Stephenson. ESPN chronicled the story of the Stephensons in a short film directed by Joseph Garner titled The Schedule Makers.

  “uncertainty is delayed in its resolution”: Michael Trick, personal interview, November 26, 2013.

  “practically no matter who they are”: Ibid.

  “A 3:2 score gives the winning team”: Tom Murphy, “Tuning in on Noise?” Published June 22, 2014 on the “Do the Math” blog: http://physics.ucsd.edu/do-the-math/2014/06/tuning-in-on-noise/

  recognizing the virtues of robustness in algorithms: Ackley, “Beyond Efficiency.”

  “bubble sort has no apparent redeeming features”: Knuth, The Art of Computer Programming, §5.5.

  The winner of that particular honor: Dave Ackley, personal interview, November 26, 2013. See Jones and Ackley, “Comparison Criticality in Sorting Algorithms,” and Ackley, “Beyond Efficiency.” For more about Comparison Counting Sort (also sometimes known as Round-Robin Sort) see Knuth, The Art of Computer Programming, §5.2.

  “most important skill as a professional poker player”: Isaac Haxton, personal interview, February 20, 2014.

  “Imagine two monkeys”: Christof Neumann, personal interview, January 29, 2014.

  “aggressive acts per hen increased”: Craig, Aggressive Behavior of Chickens.

  There’s a significant computational burden: Jessica Flack, personal interview, September 10, 2014. See also DeDeo, Krakauer, and Flack, “Evidence of Strategic Periodicities in Collective Conflict Dynamics”; Daniels, Krakauer, and Flack, “Sparse Code of Conflict in a Primate Society”; Brush, Krakauer, and Flack, “A Family of Algorithms for Computing Consensus About Node State from Network Data.” For a broader overview of Flack’s work, see Flack, “Life’s Information Hierarchy.”

  This sporting contest is the marathon: The marathon has an analogue in the world of sorting algorithms. One of the more intriguing (Wikipedia used the word “esoteric” before the article was removed entirely) developments in beyond-comparison sorting theory arose from one of the most unlikely places: the notorious Internet message board 4chan. In early 2011, an anonymous post there proclaimed: “Man, am I a genius. Check out this sorting algorithm I just invented.” The poster’s “sorting algorithm”—Sleep Sort—creates a processing thread for each unsorted item, telling each thread to “sleep” the number of seconds of its value, and then “wake up” and output itself. The final output should, indeed, be sorted. Leaving aside the implementation details that reveal the cracks in Sleep Sort’s logic and just taking Sleep Sort on face value, it does seem to promise something rather intoxicating: a sort whose runtime doesn’t depend on the number of elements at all, but rather on their size. (Thus it’s still not quite as good as a straight-up O(1) constant-time sort.)

  “You go to the money”: This is articulated by British entrepreneur Alexander Dean at https://news.ycombinator.com/item?id=8871524.

  “the bigger one is the dominant one”: The Law of Gross Tonnage, it seems, really does rule the ocean. This is not to say fish are entirely pacifistic. It’s worth noting that they will fight—aggressively—when their sizes are similar.

  4. CACHING

  “In the practical use of our intellect”: James, Psychology.

  Now you have two problems: This construction nods to a famous programming joke first coined by Netscape engineer Jamie Zawinski in a Usenet post on August 12, 1997: “Some people, when confronted with a problem, think ‘I know, I’ll use regular expressions.’ Now they have two problems.”

  “How long have I had it?”: Stewart, Martha Stewart’s Homekeeping Handbook.

  “Hang all your skirts together”: Jay, The Joy of Less.

  “Items will be sorted by type”: Mellen, Unstuff Your Life!

  “a very sharp consciousness but almost no memory”: Davis, Almost No Memory.

  one of the fundamental principles of computing: Our histo
ry of caching is based on that provided by Hennessy and Patterson, Computer Architecture, which also has a great treatment of modern caching methods in computer design.

  an electrical “memory organ”: Burks, Goldstine, and von Neumann, Preliminary Discussion of the Logical Design of an Electronic Computing Instrument.

  a supercomputer in Manchester, England, called Atlas: Kilburn et al., “One-Level Storage System.”

  “automatically accumulates to itself words”: Wilkes, “Slave Memories and Dynamic Storage Allocation.”

  implemented in the IBM 360/85 supercomputer: Conti, Gibson, and Pitkowsky, “Structural Aspects of the System/360 Model 85.”

  number of transistors in CPUs would double every two years: Moore’s initial 1965 prediction in “Cramming More Components onto Integrated Circuits” was for a doubling every year; in 1975 he then revised this in “Progress in Digital Integrated Electronics” to be a doubling every two years.

  six-layer memory hierarchy: Registers; L1, L2, and L3 caches; RAM; and disk. For more on the “memory wall,” see, for instance, Wulf and McKee, “Hitting the Memory Wall.”

  “not to have useless facts elbowing out the useful ones”: Conan Doyle, “A Study in Scarlet: The Reminiscences of John H. Watson.”

  “words cannot be preserved in it indefinitely”: Wilkes, “Slave Memories and Dynamic Storage Allocation.”

  Bélády was born in 1928 in Hungary: Bélády’s personal history is based on an oral history interview he conducted with Philip L. Frana in 2002 (available at https://conservancy.umn.edu/bitstream/107110/1/oh352lab.pdf). His analysis of caching algorithms and results are presented in Bélády, “A Study of Replacement Algorithms for a Virtual-Storage Computer.”

  the most cited piece of computer science research for fifteen years: From Bélády himself: “My paper written in 1965 became the Citation Index most-referenced paper in the field of software over a 15-year period.” J. A. N. Lee, “Laszlo A. Belady,” in Computer Pioneers, http://history.computer.org/pioneers/belady.html.