# Re: More on lists and sets

Date: 28 Mar 2006 05:32:39 -0800

Message-ID: <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.

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

*>
*

> 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. Received on Tue Mar 28 2006 - 15:32:39 CEST