[PRL] Re: [plt-internal] cisco router problem

[Matthias Felleisen]

Close. The reason I am pushing him is to get a cute little example for 
212 students. Here is something you can design.  Let's stress. Hah, 
it's too slow, and it's not Java's fault. How can we do better?

If we can find four or five more things like this, 212's O stuff 
becomes more interesting and accessible to students.

-- Matthias


On Wednesday, January 14, 2004, at 03:27 PM, Mitchell Wand wrote:

> I'm assuming the following is a reasonable abstraction of the problem:
>
> Given two long lists of integers (possibly with duplicates), one much
> longer than the other, find their intersection.
>
> Doing intersection (or DB join) is usually a n^2 problem.
>
> Some standard solutions:
>
> 1.  Read the big list once and the smaller list many times.  I'm
>     guessing he's already thought of this.
>
> 2.  Keep the lists sorted.  That way it turns into a O(n) problem.  If
>     you have to sort the lists, that makes it O(n log n).
>
> 3.  Preprocess the smaller list once to get a hashtable of possible
>     hits.  That way you only scan through the small list for big-list
>     elements
>
> 4.  Indices are Good Things. (Generalization of #3).
>
> --Mitch