Re: More on lists and sets

"vc" <boston103_at_hotmail.com> wrote in message news:1143552759.394751.210300_at_i40g2000cwc.googlegroups.com...
>
> David Cressey wrote:
> > "vc" <boston103_at_hotmail.com> wrote in message
> > news:1143546405.035888.3990_at_u72g2000cwu.googlegroups.com...
> >
> >
> > > intersect is list intersection, e.g.,
> > >
> > > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
> > >
> >
> > Looks like set intersection to me. And I'm going to ask: dontcha have
to
> > sort the two lists to find the common elements?
>
> Conceptually, there is no notion of sorting. You can imagine the
> resulting lis as the first list without the elements not present in the
> second list, i.e. the remaining elements are in their original order.
>
Fair enough.

Let's try a few more cases:

  [4, 3, 2, 1] intersect [2, 4, 6, 8] == [4, 2]   [2, 4, 6, 8] intersect [4, 3, 2, 1] == [2, 4]

Are these right?

Does this mean that list intersection is not commutative?

>
> > And, if you do have to sort, what if the two lists each have 10,000
> > elements? Isn't that going to slow you down?
>
> Fistly, you do not need to sort, secondly it's an implementation
> question. An Oracle join can be implemented in many different ways
> (nested loops, merge join, sort join, antijoin ) while conceptually
> remaining the same relational algebra operation.
>

You are right. It is an implementation question. Just for grins, let's say that I intended to implement something.

Then delay time becomes, at some point, important to me. I agree that an Oracle join can be implemented in many different ways. But they all take time. And they all grow non-linearly with size. And many of them require doing some of the work before receiving the query (like updating an index when a table update is committed).

> >
> > More importanlty, if you have to sort the elements (based on their
value),
> > haven't you basically ignored the fact that they
> > were ordered to begin with?
> >
> > Another way of asking the same question:
> >
> > [1,2,3,4] `intersect` [2,4,6,8] == [4,2]
> >
> > Is this a "wrong" answer?
>
> List intersection, as traditionally defined, cannot produce that
> answer.

Fair enough. See above. Received on Tue Mar 28 2006 - 20:12:47 CEST