so becausse the 1978 pohlig-hellman paper mentioned that one of knuth's taocp books had the sunzi remainder theorem they used, i finally cracked and opened up the knuth 1998 sorting and searching text
46
Replies
0
Boosts
immediately i can see that knuth's style must have inspired the lovely approach in DH 1976 where they spend the entire time shouting out papers they love and giving deep, thorough citations to people who have solved some problem or other. so that's kind of nice, even though knuth (in the 1998 book especially) spends a great deal of time thinking about how to perform large-scale surveillance, and also daps up ron rivest way too frequently
there are a lot of ways he introduces to describe hashing that are thoroughly aligned with the ways i have been thinking about it in my head. so i feel pretty confident now just doing my own bullshit data structures. [recall that i define "hash" to mean "hash table" and not "checksum"]
however, there is an immense reliance on "expected-time" analysis, which i can immediately see led to linux's i/o bullshit directly:
Perhaps the reader has been skeptical of B-trees because the degree of the root can be as low as 2. Why should we waste a whole disk access on merely a 2-way decision?! A simple buffering scheme, called least-recently-used page replacement, overcomes this objection; we can keep several bufferloads of information in the internal memory, so that input commands can be avoided when the corresponding page is already present. Under this scheme, the algorithms for searching or insertion issue “virtual read” commands that are translated into actual input instructions only when the necessary page is not in memory; a subsequent “release” command is issued when the buffer has been read and possibly modified by the algorithm. When an actual read is required, the buffer that has least recently been released is chosen; we write out that buffer, if its
contents have changed since they were read in, then we read the desired page into the chosen buffer.
literally EVERY SINGLE OS JUST DOES THIS EXACT SHIT TO THE LETTER AND DOESN'T THINK TWICE! it's FUCKED!
