home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3393 < prev    next >
Encoding:
Text File  |  1993-01-02  |  3.0 KB  |  79 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!gatech!destroyer!cs.ubc.ca!uw-beaver!newsfeed.rice.edu!rice!news.rice.edu!dougm
  3. From: dougm@titan.cs.rice.edu (Doug Moore)
  4. Subject: Re: Locating duplicates
  5. In-Reply-To: dave@cs.arizona.edu's message of 2 Jan 93 04:16:58 GMT
  6. Message-ID: <DOUGM.93Jan2014723@titan.cs.rice.edu>
  7. Sender: news@rice.edu (News)
  8. Organization: Rice University Computer Science, Houston, Texas
  9. References: <C07FJo.4vq@ux1.cso.uiuc.edu>
  10.     <1993Jan2.041658.21596@organpipe.uug.arizona.edu>
  11. Date: Sat, 2 Jan 1993 07:47:23 GMT
  12. Lines: 65
  13.  
  14. >>>>> On 2 Jan 93 04:16:58 GMT, dave@cs.arizona.edu (Dave Schaumann) said:
  15.  
  16.     Dave> In article <C07FJo.4vq@ux1.cso.uiuc.edu>, ceblair@ux1 (Charles Blair) writes:
  17. >   Given a large array of integers.  Is there a way to identify duplicates
  18. >which is substantially less work than sorting the array?
  19.  
  20.     Dave> Hmm... imagine we have an array with just two elements that are equal.
  21.     Dave> Now assume we have some duplicate finder which does not sort the array.
  22.     Dave> Assuming that the values and positions of the data are not related in
  23.     Dave> some way, it seems reasonable to assume that we can arrange the values
  24.     Dave> so that that the algorithm must try every possible combination before
  25.     Dave> it finds the duplicate pair.
  26.  
  27.     Dave> Not an air-tight proof
  28.  
  29. Right.  So try this:
  30.  
  31. Assume that our duplicate checker must compare elements to do its
  32. work.  And assume that we wish only to check whether or not any
  33. duplicates exist.  Let the array have, besides data entries containing
  34. the numbers to be checked, pointer entries.  When we compare two array
  35. data entries, we make the pointer paired with the lesser element point
  36. to the pair containing the greater element (or quit if the elements
  37. are equal).  To confidently report 'no duplicates', the pointers must,
  38. in the end, form a sorted linked list.  Consider two items that are
  39. consecutive in a sorted sequence; if we haven't compared those two in
  40. particular, we can't tell whether they're duplicates or not.  So we
  41. must have compared all such pairs to report 'no duplicates'.  So
  42. anything that let's us report 'no dups' is essentially a sorting
  43. algorithm, and comparison based sorting requires O(n lg n) time.
  44.  
  45. But if these are fixed size integers (like C ints), you can radix sort
  46. in linear time anyway, which is as fast as you can reasonably expect.
  47.  
  48. For example:
  49.  
  50. rsort(unsigned arr[], unsigned n)
  51. {
  52.   int j;
  53.   unsigned* stacks = (unsigned*) malloc(n*sizeof(unsigned));
  54.   unsigned mask = 1;
  55.   unsigned max = 0;
  56.   for (j = 0; j < n; ++j)
  57.     if (max < arr[j])
  58.       max = arr[j];
  59.   while (mask <= max && mask) /* <= 32 times on my machine */
  60.     {
  61.       int top = n;
  62.       int bottom = 0;
  63.       for (j = 0; j < n; ++j)
  64.         if (arr[j] & mask)
  65.           stacks[--top] = arr[j];
  66.         else
  67.           stacks[bottom++] = arr[j];
  68.       for (j = 0; j < bottom; ++j)
  69.         arr[j] = stacks[j];
  70.       for (j = top; j < n; ++j)
  71.         arr[j] = stacks[n-1-j+top];
  72.       mask <<= 1;
  73.     }
  74.   free((char*) stacks);
  75. }
  76.  
  77. Doug Moore
  78. (dougm@cs.rice.edu)
  79.