# Re: More on lists and sets

Date: Tue, 28 Mar 2006 18:12:47 GMT

Message-ID: <z0fWf.1921$Q9.977_at_trndny07>

"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.

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

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