home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3447 < prev    next >
Encoding:
Text File  |  1993-01-12  |  1.8 KB  |  40 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!pipex!harlqn.co.uk!harlqn!markt
  3. From: markt@harlqn.co.uk (Mark Tillotson)
  4. Subject: Re: Locating duplicates
  5. In-Reply-To: dave@cs.arizona.edu's message of 8 Jan 93 05:10:51 GMT
  6. Message-ID: <MARKT.93Jan12174830@wundt.harlqn.co.uk>
  7. Lines: 24
  8. Sender: news@harlqn.co.uk (Usenet News Account)
  9. Organization: Harlequin Limited, Cambridge, England
  10. References: <C07FJo.4vq@ux1.cso.uiuc.edu> <1993Jan2.041658.21596@organpipe.uug.arizona.edu>
  11.     <1993Jan5.150010.27104@ulysses.att.com>
  12.     <MARKT.93Jan7122729@wundt.harlqn.co.uk>
  13.     <1993Jan8.051051.18788@organpipe.uug.arizona.edu>
  14. Date: Tue, 12 Jan 1993 17:48:30 GMT
  15.  
  16. dave@cs.arizona.edu (Dave Schaumann) mentions (when talking of my
  17. hashing method for duplicate-detection):
  18. > If you choose the number of buckets at run-time based on the number
  19. > of elements, you might as well just use the "radix sort" solution
  20. > already posted.
  21.  
  22. But a radix sort needs buckets proportional to the _range_ of integers
  23. involved, or else will require multiple passes over the data, for
  24. instance 100 buckets and input with a range of 1 million means 3
  25. passes are required, and 3 sets of buckets.  In practice with 32 bit
  26. (or even 64 bit) integers, there isn't going to be a great deal of
  27. difference between hashing and radix sorting.  Generalising the
  28. problem (say to spotting duplicated strings) will tend to favour
  29. hashing. 
  30.  
  31. However if you want guaranteed performance, avoid the hash table
  32. method because it's worst case becomes O(N^2)...
  33.  
  34. ------------------------------------------------------
  35. |\  /|          | ,  M. Tillotson       Harlequin Ltd. \
  36. | \/ |  /\| |/\ |<   markt@uk.co.harlqn  Barrington Hall,\
  37. |    |  \_| |   | \  +44 223 872522       Barrington,      \
  38. I came, I saw, I core-dumped...            Cambridge CB2 5RG \
  39.  
  40.