home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3412 < prev    next >
Encoding:
Text File  |  1993-01-05  |  2.4 KB  |  63 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!elroy.jpl.nasa.gov!usc!cs.utexas.edu!torn!nott!cunews!revcan!micor!goss
  3. From: goss@micor.ocunix.on.ca (Timothy D. Goss)
  4. Subject: Re: Locating duplicates
  5. Organization: M.B. Cormier INC., Orleans (Ont)
  6. Date: Tue, 5 Jan 1993 04:34:56 GMT
  7. Message-ID: <1993Jan5.043456.29130@micor.ocunix.on.ca>
  8. References: <1993Jan2.041658.21596@organpipe.uug.arizona.edu> <DOUGM.93Jan2014723@titan.cs.rice.edu> <C07z6L.1Aq@world.std.com>
  9. Lines: 52
  10.  
  11. You can locate ALL duplicates in a list of integers with a single pass of the
  12. list which is O(n) in time but it will require an array with 64K elements.  The
  13. program below should explain...
  14.  
  15. typedef unsigned char byte;
  16.  
  17. static byte found[65536];
  18. int intlist[NUM];        
  19.  
  20. void main(void) 
  21. {
  22.  
  23.    int i;
  24.    int check;
  25.  
  26.    /* assume intlist is filled with NUM integers */
  27.  
  28.    for (i=0; i<NUM; i++) {
  29.       check = intlist[i];
  30.       if (found[check] > 0 && found[check] != 0xff) {
  31.          printf("%d\n", check);
  32.          found[check] = 0xff; /* don't report same dupe twice */
  33.       } else {
  34.          found[check] += 1; /* first time we saw this one */
  35.       }
  36.    }
  37.  
  38. }
  39.  
  40. Of course this program could be modified to use a hash table to store the found
  41. integers at a slight performance penalty.  If memory is not a problem the 64K
  42. found array could be malloc'ed then free'd after. 
  43.  
  44. I haven't actuall run this program but the idea is what I want to get across.
  45. Sorting the list isn't really necessary, that's a very awkward way to solve
  46. that particular problem.
  47.  
  48. For the really memory stingy you could you a bitmap for the found array but
  49. it would require 2 bits for each integer to avoid reporting more than 2
  50. occurrences of the same integer.
  51.  
  52. I can't really see a faster way to do this with an unordered list, O(n) is the
  53. best you can hope for.
  54.  
  55.  +----------------------------------------------------------------------------+
  56.  |         _   /|                                                             |
  57.  |         \'o.O'        We the unwilling, led by the unknowning,          |
  58.  |         =(___)=          are doing the impossible for the ungrateful.      |
  59.  |            U             We have done so much, for so long, with so little |
  60.  |     Timothy D. Goss      we are now qualified to do anything with nothing. |
  61.  | goss@micor.ocunix.on.ca                                                    |
  62.  +----------------------------------------------------------------------------+
  63.