home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3437 < prev    next >
Encoding:
Internet Message Format  |  1993-01-08  |  1.5 KB
  1. Path: sparky!uunet!gatech!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  2. From: dave@cs.arizona.edu (Dave Schaumann)
  3. Newsgroups: comp.programming
  4. Subject: Re: Locating duplicates
  5. Message-ID: <1993Jan8.051051.18788@organpipe.uug.arizona.edu>
  6. Date: 8 Jan 93 05:10:51 GMT
  7. References: <C07FJo.4vq@ux1.cso.uiuc.edu> <1993Jan2.041658.21596@organpipe.uug.arizona.edu> <1993Jan5.150010.27104@ulysses.att.com> <MARKT.93Jan7122729@wundt.harlqn.co.uk>
  8. Sender: news@organpipe.uug.arizona.edu
  9. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  10. Organization: University of Arizona
  11. Lines: 18
  12. In-Reply-To: markt@harlqn.co.uk (Mark Tillotson)
  13.  
  14. In article <MARKT.93Jan7122729@wundt.harlqn.co.uk>, markt@harlqn (Mark Tillotson) writes:
  15. >Use a hash table from integers to the number of occurrences, then you
  16. >do N hash-lookups, and one scan of the hash table looking for
  17. >duplicates, giving an expected time O(N),
  18.  
  19. But what happens when the number of elements to be scanned is much
  20. larger than the number of buckets you choose?  You get collisions
  21. up the wazoo, and then your algorithm is suddenly O(N*f(N/#buckets)),
  22. where your collision resolution algorithm is O(f(N/#buckets)).
  23.  
  24. If you choose the number of buckets at run-time based on the number
  25. of elements, you might as well just use the "radix sort" solution
  26. already posted.
  27.  
  28. -- 
  29. You're traveling through another dimension -- a dimension not only of sight and
  30. sound but of mind. A journey into a wonderous land whose boundaries are that of
  31. imagination.  That's a signpost up ahead: your next stop -- the Twilight Zone!
  32.