home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3428 < prev    next >
Encoding:
Text File  |  1993-01-07  |  1.9 KB  |  43 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: kpv@ulysses.att.com's message of Tue, 5 Jan 1993 15:00:10 GMT
  6. Message-ID: <MARKT.93Jan7122729@wundt.harlqn.co.uk>
  7. Lines: 29
  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. Date: Thu, 7 Jan 1993 12:27:25 GMT
  13.  
  14. In article <1993Jan5.150010.27104@ulysses.att.com> kpv@ulysses.att.com
  15. (Phong Vo) writes:
  16.  
  17. > In article <1993Jan2.041658.21596@organpipe.uug.arizona.edu> dave@cs.arizona.edu (Dave Schaumann) writes:
  18. > >In article <C07FJo.4vq@ux1.cso.uiuc.edu>, ceblair@ux1 (Charles Blair) writes:
  19. > >>   Given a large array of integers.  Is there a way to identify duplicates
  20. > >>which is substantially less work than sorting the array?
  21. > >
  22. > >...lots of good suggestions for the general case...
  23. > 
  24. > But most often this kind of question comes up in practice
  25. > because you have a large array of integers in a small range.
  26. > In that case, using a bit map for the range, you can do it
  27. > in linear time and space proportion to the range size.
  28.  
  29. Use a hash table from integers to the number of occurrences, then you
  30. do N hash-lookups, and one scan of the hash table looking for
  31. duplicates, giving an expected time O(N), with no bound on the range
  32. of integers (other than word-size, and address-space!).  You need a
  33. suitable hash function, but for integers taking the modulo w.r.t. some
  34. prime p, where p is about the size of the incoming array.
  35.  
  36.  
  37. ------------------------------------------------------
  38. |\  /|          | ,  M. Tillotson       Harlequin Ltd. \
  39. | \/ |  /\| |/\ |<   markt@uk.co.harlqn  Barrington Hall,\
  40. |    |  \_| |   | \  +44 223 872522       Barrington,      \
  41. I came, I saw, I core-dumped...            Cambridge CB2 5RG \
  42.  
  43.