And to not store the lists explicitly (storing some smallish number of bits instead) you can use a Bloom filter or store a prefix of a good hash for one list, find the hits from the second list and store them explicitly and then redo the first list. And yes, these days even a billion (1E9) is considered pretty small; with multicore and GPU 1E12 is easy to reach. You can get to 1E15 in about a day for many things. On Fri, Apr 12, 2019 at 10:35 AM Marc LeBrun <mlb@well.com> wrote:
= James Propp <jamespropp@gmail.com> I don't see how to do it in amortized time O(n). (For that matter, I don't see how to do O(n log n) either.) Hints? Answers? References?
For O(n log n) you can sort the two lists, then scan them in tandem.
For O(n) you can put one of the lists in a hash table, then scan through the other.
These days a million really isn't considered a large number, for some value of a million.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --