Re: More on lists and sets
Date: Tue, 28 Mar 2006 18:12:47 GMT
"vc" <boston103_at_hotmail.com> wrote in message
> 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
> > 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.
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
> > 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
Fair enough. See above. Received on Tue Mar 28 2006 - 20:12:47 CEST