home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3449 < prev    next >
Encoding:
Internet Message Format  |  1993-01-12  |  1.0 KB
  1. Path: sparky!uunet!dtix!uranus!tecsun1!zogwarg!hoey
  2. From: hoey@zogwarg.etl.army.mil (Dan Hoey)
  3. Newsgroups: comp.programming
  4. Subject: Re: Locating duplicates
  5. Message-ID: <1293@zogwarg.etl.army.mil>
  6. Date: 7 Jan 93 17:01:06 GMT
  7. References: <1993Jan5.043456.29130@micor.ocunix.on.ca> <1993Jan5.224141.21639@organpipe.uug.arizona.edu> <1993Jan7.021146.2290@cs.cornell.edu>
  8. Organization: Naval Research Laboratory, Washington, DC
  9. Lines: 15
  10.  
  11. karr@cs.cornell.edu (David Karr) writes:
  12. >A shortcoming of course is that the running-time analysis is valid
  13. >only if you can repeatedly allocate large amounts of zeroed-out memory
  14. >in a small (essentially constant) time.
  15.  
  16. You can actually skip the zeroing out at a cost of a constant factor
  17. at access time.  It's well-known; email me if you're interested.
  18.  
  19. There's a known linear-time solution for the element uniqueness
  20. problem on the real-ram-with-floor model (none of this bogus 32-bit
  21. integer restriction) that uses a kind of hash table in this way.  It
  22. was in JACM in the seventies, if I recall.
  23.  
  24. Dan Hoey
  25. Hoey@AIC.NRL.Navy.Mil
  26.