williamkuszmaul

Overall seems like a great book. The hashing chapter is a bit half baked though. It claims without reservation that deletions simply cannot be efficiently implemented with linear probing. But there are at least two two efficient to do this (lazy deletions or just fix up the hash table), and both are worthwhile for students to know.

1/100 is too large of a cutoff imo. If you have a class of 96 students, there's a decent chance that an innocent student gets flagged for no reason. I hope he lets the student on the bubble off the hook.

One thing I'm confused about: Did the author try vectorizing the linear search implementation? (Of course, it is possible that even if they did not, the compiler did.) I would imagine that vectorization is behind the advice to use linear searches on small arrays.

Related recent paper in Science: https://www.science.org/doi/10.1126/science.aam9744

One important caveat: it is widely believed that randomization does make a big difference for data structures problems. For example hash tables (which use random hash functions) take O(1) time per operation, but it is conjectured that no deterministic data structure can match this.

There are also problems in online algorithms where randomization provably changes what is possible, for example the "cup game problem." (https://arxiv.org/abs/1904.02861)

Finally, although randomized primality testing (1970s) is often credited as the start of randomized algorithms as a field, it's worth noting that hash tables (1954) and quick sort (1961) were much earlier.

I think it would be fair to say that it's a kind of funny trie-hash-table hybrid. What's neat though is that it manages to achieve better space bounds than either a trie or a hash table would on their own.

I didn't invent the algorithmic idea --- it's basically a simplification of a data structure that was published in ICALP 2003 [1]. As far as I know, the idea of combining hash tables and tries in this kind of way (despite being incredibly simple!) doesn't appear in either the theoretical or experimental literature prior to that.

I'd be interested in any other earlier sources that people might have.

[1] Raman, Rao. Succinct Dynamic Dictionaries and Trees. https://link.springer.com/chapter/10.1007/3-540-45061-0_30. ICALP, 2003.

But does the question ever say "all"...?

Unless I'm misreading, the question as stated in the blog post never says there is only one duplicate (there might be many!), so in that sense I think his answer may be wrong. A more robust solution is just to have an array of n counters and just count how many times each item appears.

Using 64 bit integers, we can store the square of any 32 bit integer. Not that small...

Impressive!

There are already implementations of sample sorting that are much faster than c++ sort (but I don't recall how much faster). I'd be very interested in a comparison to some of those...

Also, since we are sorting integers, I'd also be interested to know how well a modern implementation of radix sort can be made.

If the coin were unbiased, we could compute the exact probability of getting 10231 or more heads with 20000 flips as:

"sum (20000 choose x)/2^20000 for x from 10231 to 20000",

which Wolfram Alpha evaluates to 0.00056.

The probability of getting a number of flips that differs from 10000 by at least 231 is twice that, so about 0.001.

So, in fact, the probability of this happening by dumb luck is about 1/1000. That's pretty strong evidence.

From what I've heard, Perci Diaconis (one of the authors of the original paper) actually could do this. He was a magician before he became a mathematician, and a lot of his early mathematics work focused on math relating to the magic tricks he used to do

I think that many "software companies" are actually marketing companies that plan to make almost all of their profit from a product that has already been built. They're not necessarily a joke... it's just that software engineering is no longer their main business.

This is neat! Some if the alternative solutions discussed here seem to confuse compilation with evaluation. Fortran is trying to rewrite the computation in such a way that, later on, a machine that knows nothing about precedence can evaluate the expression. It's incredible that such a rewrite can be performed from left to right without recursion and while using only O(1) memory at a time.

In case anyone is wondering, the only role of covid here is that shutdowns prevented technicians from being able to fix the issue in person.

One of the things that's cool about Bzip is that it makes use algorithmic techniques developed by theoretical computer scientists in order to perform the Burrows Wheeler Transform efficiently. It's a great example of theory and practice working symbiotically.

One estimation trick that I've found effective is the following: (1) determine the smallest number that your sure is larger than the true answer. (2) determine the largest number that you are sure is smaller than the true answer. (3) take the geometric average of the two. (i.e., sqrt(a * b))

The reason this does well, is that oftentimes, (1) overestimates the true answer by roughly the same multiplicative factor as (2) underestimates the true answer by. So the geometric mean cancels the over and under estimates in order to get an estimation that does pretty well.

I find that this works remarkably well for estimating the dimensions of buildings, trees, etc.

MIT recently cut all of their relationships with Elsevier journals. Researchers are still allowed to publish in Elsevier, but when they do, even they won't have access to their own articles without going through a paywall.

The widespread emergence of nonprofit open access journals is promising. I am hoping that in twenty years, Elsevier will be a thing if the past.

I'm not sure why they claim that the total time grows quadratically.

If tasks arrive arrive randomly at the same average rate as they can be processed, then the amount of time that the nth task will have to wait is proportional to sqrt(n) in expectation. So one would expect a total waiting time of n^1.5, which incidentally fits much better to their plotted curve than n^2 does.

It's even worse than most people seem to realize. For many years the ISO standard for C included the line:

"If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined"

Fortunately, this was changed at some point between C '99 and C '11, so that now the remainder is consistently defined across all implementations.

Another example of this would be if there are three candidates X,Y,Z. Suppose Alice strongly prefers X and Bob strongly prefers Y. Rather than each of Alice and Bob allocating 100 points to their preferred candidate, they can each allocate 50 points to X and 50 points to Y. The net effect is that they have multiplied each of their voting power by sqrt(2).

I don't like any voting system that incentivizes group collusion. A much fairer system would be some form of random ballot: everyone gets to allocate some number of votes, and then a random vote gets picked to select the winner. This type of system is especially good for situations where there are many winners (eg the Congress), since it allows for even small parties (eg the Green party) to get proportionate representation.

It turns out that if you write down on the list of requirements that you would want from a voting system in order for it to be fair, the no deterministic voting system is fair. This is known as Arrow's theorem (https://en.m.wikipedia.org/wiki/Arrow%27s_impossibility_theo...).

Interestingly Arrow's theorem doesn't apply to randomized voting systems. In particular, the system of picking a random voter to decide the election satisfies (probabilistically) every standard notion of fairness.

In my field, at least, I think the problem is less about the medium, and more about the incentives. Researchers are incentivized to write papers that seem impressive (and intimidating) rather than clear and intuitive.

To make matters worse, this is an evolved trait: researchers whose papers are intimidating are more likely to succeed, which means they're more likely to have future PhD students, which means that the style of writing is more likely to get passed on.

I think the main way to address this is to change the incentives. In particular, by creating publication venues that value simplicity and clarity (one such conference is SOSA, which has had a lot of impact on theoretical computer science in the last few years).

Here is a (semi)recent paper in Science about the end of Moore's law. As I understand it (but I'm not an expert), Figure 2 seems to give pretty compelling evidence that Dennard scaling (i.e, the phenomenon that historically allowed for smaller chips to run at higher clock speeds without an increase in power usage) seems to have stopped around 2005, and that subsequent speed ups have largely come from in-chip parallelism.

https://www.science.org/doi/10.1126/science.aam9744

Interesting post!

Small comment on the argument against anti-aging genes existing: "genes only propagate if selected for, and there’s no selective pressure for longevity after reproductive age" (I know that this was just a very minor aside, but I still think it's worth pointing out the flaw.)

That's not how evolution works. Even after you have reproduced, you have impact on whether your children survive and reproduce. This means that there could very reasonably be evolutionary pressure in either direction (causing people to die younger that way they stop taking resources from their children or causing people to live longer that way they keep providing support for their children).

It seems like you may be jumping to conclusions a bit prematurely. The paper (https://www.cs.unc.edu/~porter/pubs/fast15-final.pdf) is very explicit that they start with a cold cache. They also go into detail for why they do well on grep. As I understand it (but I'm not an expert), betrfs's advantage here comes from the fact that it stores files lexicographically by their full names (and metadata), meaning that related files are stored nearby each other on disk. This gives better locality than what you would get with a standard inode structure.

Based on that, it seems like the outcomes of the tests are pretty reasonable.

I'm not super familiar with bcachefs, but from what I can find it seems like it is based mostly on a standard (but I guess very well implemented) B-tree. Am I missing something?

The website doesn't seem to mention that several of the papers on the filesystem won best-paper awards at major conferences. The paper, Optimizing Every Operation in a Write-Optimized File System, in particular, won best-paper award at FAST '16.

Also, if you're interested in learning more about B^\epsilon trees, here's a talk given by Rob Johnson a few years ago at Microsoft Research: BetrFS: A Right-Optimized Write-Optimized File System https://www.youtube.com/watch?v=fBt5NuNsoII

In general, I think it's really cool that there is a file system that exists today (i.e., BetrFS) that uses data structures which didn't exist 25 years ago. It's a great example of theoreticians and systems researchers working together.

Very nice post!

Small comment: Ideally, big-O notation is for upper bounds. If you are doing lower bounds, you should ideally use big-Omega notation. But Omegas are harder to format in plain text, so it may be better to abuse notation and use big-O...

This is a link to the paper that the article is about: https://arxiv.org/abs/2107.01250