Stefan wrote:
[snip]
> > Isn't it O(min(m,n))? You don't have to look at all
> elements for the
> > intersection. Eg:
> >
> > {0,1,10}
> > {0,3,98,183,398,1038,5319,7642,9811,13893,93123}
>
> O(f) describes the worst case of the algorithm. It is O((m,n)->m+n).
> The average cost may be
Dear Nicholas,
Nicholas Nethercote (Wed, Nov 12, 2003 at 11:32:54AM +):
> On Wed, 12 Nov 2003, Tom Pledger wrote:
>
> > Hal Daume III writes:
> > :
> > | *all* i care about is being able to quickly calculate the size of
> > | the intersection of two sets. these sets are, in general, very
John Meacham wrote:
my intuition says something like binary trees annotated with the minimum
and maximum value contained beneath each node so you may prune whole
subtrees in constant time...
Yes. This may be one dimension too high,
but check out "segment trees" from Computational Geometry.
See Ben
On Wed, Nov 12, 2003 at 11:32:54AM +, Nicholas Nethercote wrote:
> > Hal Daume III writes:
> > :
> > | *all* i care about is being able to quickly calculate the size of
> > | the intersection of two sets. these sets are, in general, very
> > | sparse, which means that the intersections ten
Hi Hal,
On Tue, 11 Nov 2003 16:45:56 -0800 (PST), Hal Daume III <[EMAIL PROTECTED]>
wrote:
i'm looking for a representation for a set of natural numbers. right
now, my representation is sorted array, which works well. *all* i care
about
is being able to quickly calculate the size of the inte
On Wed, Nov 12, 2003 at 03:00:38PM +1300, Tom Pledger wrote:
> The total time (including the up front time for building the data
> structure) can't go below O(n+m), because if it did, you'd be
> neglecting to look at some of the elements at all.
that would be true if there wern't a total ordering
On Wed, 12 Nov 2003, Tom Pledger wrote:
> Hal Daume III writes:
> :
> | *all* i care about is being able to quickly calculate the size of
> | the intersection of two sets. these sets are, in general, very
> | sparse, which means that the intersections tend to be small.
> |
> | for example,
Hal Daume III writes:
:
| *all* i care about is being able to quickly calculate the size of
| the intersection of two sets. these sets are, in general, very
| sparse, which means that the intersections tend to be small.
|
| for example, i might have two sets reprsented by the arrays:
|
|
G'day all.
Quoting Hal Daume III <[EMAIL PROTECTED]>:
> i'm looking for a representation for a set of natural numbers. right now,
> my representation is sorted array, which works well. *all* i care about
> is being able to quickly calculate the size of the intersection of two
> sets. these set
this is somewhat off topic, but i'll add "does anyone have a haskell
implementation of..." to the beginning to make it more on topic :).
anyway there are a lot of smart people here...
i'm looking for a representation for a set of natural numbers. right now,
my representation is sorted array,
10 matches
Mail list logo
