Re: efficient comparison
- From: cri@xxxxxxxx (Richard Harter)
- Date: Tue, 28 Aug 2007 04:45:51 GMT
On Mon, 27 Aug 2007 21:20:31 -0700, "Jim Langston"
<tazmaster@xxxxxxxxxxxxxx> wrote:
<bob@xxxxxxxxxxxxxx> wrote in message
news:1188266948.054544.252730@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Let's say you have a set of names called set A. You also have a
different
set of names called set B. What is the most efficient way of
comparing the sets?
By comparison, I mean finding the names that need to be added to set B
and
deleted from set B to form set A.
It seems like a simple sort of each list then going through and comparing.
Rather trivial actually.
It's not that simple, nor that trivial. The "most efficient" way
depends on the structure of the names, the emphasis given on
storage cost vs computation cost and even on the relative sizes
of the sets A and B.
The trivial answer is to use hash tables, i.e., enter one set
into a hash table and then check the occurences of the other in
the table. It's the O(n) solution...
.... but there are complications. Hash tables are not cache
friendly. Moreover they are not as efficient as radix based
trees (e.g., Patricia trees, ternary tree, and UR trees) if the
names are strings. If the names are integers there are really
efficient sorts available, except that most O(n) and
O(n*log log n) integer sorts aren't cache friendly for large n.
.
- References:
- efficient comparison
- From: bob
- Re: efficient comparison
- From: Jim Langston
- efficient comparison
- Prev by Date: Re: efficient comparison
- Next by Date: (Source Code Download) Re: Fast pi program?
- Previous by thread: Re: efficient comparison
- Next by thread: Re: efficient comparison
- Index(es):
Relevant Pages
|
