home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3418 < prev    next >
Encoding:
Text File  |  1993-01-06  |  2.1 KB  |  57 lines
  1. Path: sparky!uunet!gatech!destroyer!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  2. From: dave@cs.arizona.edu (Dave Schaumann)
  3. Newsgroups: comp.programming
  4. Subject: Re: Locating duplicates
  5. Message-ID: <1993Jan5.224141.21639@organpipe.uug.arizona.edu>
  6. Date: 5 Jan 93 22:41:41 GMT
  7. References: <1993Jan2.041658.21596@organpipe.uug.arizona.edu> <DOUGM.93Jan2014723@titan.cs.rice.edu> <C07z6L.1Aq@world.std.com> <1993Jan5.043456.29130@micor.ocunix.on.ca>
  8. Sender: news@organpipe.uug.arizona.edu
  9. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  10. Organization: University of Arizona
  11. Lines: 43
  12. In-Reply-To: goss@micor.ocunix.on.ca (Timothy D. Goss)
  13.  
  14. In article <1993Jan5.043456.29130@micor.ocunix.on.ca>, goss@micor (Timothy D. Goss) writes:
  15. >You can locate ALL duplicates in a list of integers with a single pass of the
  16. >list which is O(n) in time but it will require an array with 64K elements.  The
  17. >program below should explain...
  18. >
  19. >typedef unsigned char byte;
  20. >
  21. >static byte found[65536];
  22. >int intlist[NUM];        
  23. >
  24. >void main(void) {
  25. >
  26. >   int i; int check;
  27. >
  28. >   /* assume intlist is filled with NUM integers */
  29. >
  30. >   for (i=0; i<NUM; i++) {
  31. >      check = intlist[i];
  32. >      if (found[check] > 0 && found[check] != 0xff) {
  33. >         printf("%d\n", check);
  34. >         found[check] = 0xff; /* don't report same dupe twice */
  35. >      } else {
  36. >         found[check] += 1; /* first time we saw this one */
  37. >      }
  38. >   }
  39. >
  40. >}
  41.  
  42. This is fine if you know all of your values are between 0 and 65536.
  43. A slightly more robust (but still linear time) algorithm could be written
  44. which would only require that the difference between the maximum and minimum
  45. elements is 65536.
  46.  
  47. Also, if you use a bit-vector instead of an array of chars for "found", you
  48. get an 8x space improvement at the cost of a small amound of bit twiddling.
  49.  
  50. Hmmm.  An even more robust algorithm would scan through the array to find
  51. the difference between the largest and smallest elements, and then malloc()
  52. an appropriate sized array.  Of course, if malloc() returns NULL, you'll
  53. have to fall back to some kind of in-place sorting scheme.
  54.  
  55. -- 
  56. Dave Schaumann            dave@cs.arizona.edu
  57.