home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3394 < prev    next >
Encoding:
Text File  |  1993-01-02  |  1.2 KB  |  25 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!world!jhallen
  3. From: jhallen@world.std.com (Joseph H Allen)
  4. Subject: Re: Locating duplicates
  5. Message-ID: <C07z6L.1Aq@world.std.com>
  6. Organization: The World Public Access UNIX, Brookline, MA
  7. References: <C07FJo.4vq@ux1.cso.uiuc.edu> <1993Jan2.041658.21596@organpipe.uug.arizona.edu> <DOUGM.93Jan2014723@titan.cs.rice.edu>
  8. Date: Sat, 2 Jan 1993 09:18:20 GMT
  9. Lines: 14
  10.  
  11. Another way is to use a clash detection table.  For each integer apply a
  12. hash function which returns an integer of about log2(2*size of array) bits.
  13. Use this as an index into a bit map which is 1/16 the size of the array.  If
  14. the bit is clear, set it.  If it's set, you might have a duplicate.  Store
  15. the potential duplicate in some kind of database.  Make a second pass
  16. through the array to verify the duplicates.
  17.  
  18. This method will approach O(n) if the number of expected duplicates is small
  19. and if the hash function is good.
  20. -- 
  21. /*  jhallen@world.std.com (192.74.137.5) */               /* Joseph H. Allen */
  22. int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
  23. +r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
  24. ]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
  25.