[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

# find-links-from-to-three

• To: <tribble>
• Subject: find-links-from-to-three
• From: Mark S. Miller <mark>
• Date: Thu, 24 Aug 89 16:20:35 PDT
• Cc: <us>
• In-reply-to: <Eric>,11 PDT <8908231818.AA06289@xxxxxxxxxx>

```Date: Wed, 23 Aug 89 11:18:11 PDT
From: tribble (Eric Dean Tribble)

I just realized while talking to marcs that we can now support
find-links-from-to-three-home reasonably efficiently.  The current
link operation corresponds to find-links-from-three-home or
find-links-to-three-home.  The combination of two operations (one on
the from set, one on the to-set) does the full flftt operations.  All
that's required is a hash set to find the intersection of the two
results.

Well, it depends what you mean by efficiently.  Your solution is
O(N log N) in the maximum count of the two sets being intersected
(since the sets need to be generated first).  Alternatively, if you
can estimate cheaply which will be the smaller of the two sets, you
could do this in O(N log N) in the minimum count of the two sets being
intersected.  However, this would require widding southward some kind
of info of what stuff more northward points at, so I think we are
stuck with O(N log N) in the maximum.  I would not define this as an
efficient flftth operation.  I would also not define the one
proportional to the minimum as efficient.  I like defining efficient
as O(N (log N)^k) in the count of the *answer* (for some constant k).
If N can be arbitrarily larger then the answer (which it can with the
above algorithm), then you can spend a long time to get nothing back.

```