home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3427 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  1.3 KB
  1. Path: sparky!uunet!cs.utexas.edu!swrinde!sdd.hp.com!spool.mu.edu!wupost!usc!enterpoop.mit.edu!eru.mt.luth.se!lunic!sunic!corax.udac.uu.se!corax.udac.uu.se!perm
  2. From: perm@csd.uu.se (Per Mildner)
  3. Newsgroups: comp.programming
  4. Subject: Re: Locating duplicates
  5. Message-ID: <PERM.93Jan5210346@groucho.csd.uu.se>
  6. Date: 5 Jan 93 20:03:46 GMT
  7. References: <C07FJo.4vq@ux1.cso.uiuc.edu>
  8. Organization: Computing Science Dept.,Uppsala University, Sweden
  9. Lines: 20
  10. NNTP-Posting-Host: groucho.csd.uu.se
  11. In-reply-to: ceblair@ux1.cso.uiuc.edu's message of 2 Jan 93 02:13:58 GMT
  12.  
  13.  
  14. A general solution to this problem (ie not dependent on the values
  15. being integers) can be found in an fairly recent CACM article (I don't
  16. have it handy, probably first half of 1992, you probably could use
  17. WAIS to find it... ).
  18.  
  19. From memory:
  20.  
  21. It uses hashing to compute a 'home' for a particular key in the
  22. vector. It scans the vector while moving keys to their 'home' location
  23. (and checking if the value at the 'home' is a duplicate or else do
  24. some clash handling). I don't remember the various performance
  25. characteristics for the algorithm but I think one of the good things
  26. was that it was useful on disk based vectors (ie to large to be sorted
  27. in memory).
  28.  
  29. --
  30. Per Mildner            perm@CSD.UU.SE
  31. Computing Science Dept.        tel: +46 18181049
  32. Uppsala University, Sweden    fax: +46 18521270
  33.