Sorting and searching

What Hacker News says

1. denton-scratchNov 2023
   Many other commenters apparently take the view that TAOCP isn't much help to a modern, professional programmer.

   That's probably true, in the sense that it deals largely with the kind of functionality modern programmer should be calling from a library, not implementing by hand. But I think it's hugely enriching to read these books. I read 1-3 back in the 70s, and was particularly inspired by Sorting and Searching, and especially the chapter on random numbers. RNGs have intrigued me ever since.

   I find Knuth's writing style very pleasant. He's funny. So is it worth the time and effort? Not if "worth it" means "makes you a better Javascript programmer". But it's worth it in the sense that reading books about the history and geography of a country is "worth it" before visiting; your appreciation of the place is deepened, possibly transformatively. It could even be that you would never have visited had you not read those books.

   I found TAOCP easy to read, much more so than most textbooks. I don't think I tackled many of the exercises; certainly none of the challenging ones. So for me, the "effort" aspect of "is it worth the time and effort" was quite low, so the ROI was quite high. If you find the books hard to read, then don't bother (and perhaps you aren't really interested in low-level algorithms).

   Show morethread
2. lifefeedOct 2022
   Vol 1 is just an intro to math and his language, you don't really need it, but it's kinda fun.

   I read some of Vol 2, Seminumerical Algorithms, to hone my instincts on how random numbers work in practice. I have referred to it on occasion when people say things like, "if we seed the random number generator, take the random number, then feed that into the seed, the result would be more random."

   I read most of Vol 3, Sorting and Searching, when applying for jobs. It was more interesting than leetcode grinding. I don't know if it was more useful, but it was better for my sanity.

   Show morethread
3. bradknowlesFeb 2022
   For math, I would say nothing. What made the difference for me there was the teacher I was working with. A good teacher could help inspire me to get an A+ in College Algebra through Calc III while a bad one could result in me to get a D- in anything from Calc I through Calc III. Yes, I took Calc I and Calc III twice, because I got a D- the first time through both of those classes, and it was the same guy who taught me Calc I and Calc III for my second time through, and in both of his classes I got an A+.

   I barely scraped through with a C for Engineering Math (Differential Equations).

   For me, the teacher made the difference in math.

   For CS, the most influential books for me were Knuth, Sorting and Searching (although I actually bought all three books in the series, unlike most others I knew), as well as the original Kernighan & Ritchie book on the C programming language (before ANSI C was published).

   Show morethread
4. JackFrNov 2021
   Just read his introduction to generating pseudo-random numbers or his sketch of a proof of Benfords law in Seminumerical Algorithms. Excellent stuff.

   For moderately impractical, look at tape sorting in Sorting and Searching.

   thread
5. metagameOct 2021
   TAOCP uses a significantly different methodology of teaching, and it's also very explicitly aimed at a significantly different market of programmer and in a significantly different area of endeavor within computer science.

   It's a great work (I'd be lying if I'd said I'd poured into the entirety of it extensively, but I've spent weeks on certain portions, like the MMIX fascicle and Sorting and Searching), but PAIP has a significantly better claim at "kickstarting" the "read code instead of write it" trend, because in TAOCP the code doesn't take center stage, and it was never the point for it to (hence the creation of MIX & MMIX).

   Show morethread
6. cb321Feb 2021
   Knuth, The Art Of Computer Programming V3, Sorting & Searching covered both multiply & shift and modulo prime integer hashing in some detail in its first edition written in the 1960s, published in 1973. While not "modern", Knuth has always been a bona fide classic, especially as regards hashing, and should really be cited by this survey paper, IMO. (EDIT: people now call this "Fibonacci Hashing" even though, in the source material itself, Knuth mentions many irrational numbers will do, not just his motivating choice of the golden ratio from Fibonacci numbers fame. There are blog posts about it being "the optimization that time forgot", etc.)

   For not entirely clear reasons (maybe multiplier selection?), only Knuth's modulo prime suggestion "propagated" well in the 70s and 80s. This suggestion reception bias also aged poorly over ensuing decades with the CPU cost of modulo vs. multiply evolving from a 2x performance delta to more like 10x.

   Show morethread