4 ms·
Not sure which Knuth paper you're referring to but skimming through the article my understanding is this algorithm works /only/ if the values are hashable. IOW
by devnonymous 2y ago
Not sure which Knuth paper you're referring to but skimming through the article my understanding is this algorithm works /only/ if the values are hashable. IOW how else does one define unique/distinct values ?
- 112233 2y agohttps://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf note how "u"s are selected every time value is not in a list. I don't read it as being a hash.
- hcs 2y agoI think the analysis relies on independent random "u"s, even for the same key.
- hcs 2y agohttps://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf Looks like it was posted at the time https://news.ycombinator.com/item?id=36079213 https://news.ycombinator.com/item?id=36079213 but not much discussed. I found it over here https://news.ycombinator.com/item?id=40387594 https://news.ycombinator.com/item?id=40387594