home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3433 < prev    next >
Encoding:
Text File  |  1993-01-07  |  2.4 KB  |  48 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!caen!batcomputer!cornell!karr
  3. From: karr@cs.cornell.edu (David Karr)
  4. Subject: Re: Locating duplicates
  5. Message-ID: <1993Jan7.173822.12773@cs.cornell.edu>
  6. Organization: Cornell Univ. CS Dept, Ithaca NY 14853
  7. References: <1993Jan5.043456.29130@micor.ocunix.on.ca> <1993Jan5.224141.21639@organpipe.uug.arizona.edu> <1993Jan7.021146.2290@cs.cornell.edu>
  8. Date: Thu, 7 Jan 1993 17:38:22 GMT
  9. Lines: 37
  10.  
  11. In article <1993Jan7.021146.2290@cs.cornell.edu> 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.  But pessimistic assumptions
  15. >about memory initialization are bad for other index-array algorithms
  16. >as well.
  17.  
  18. Mark Tillotson objected that my assumption about O(1) memory
  19. allocation was a bad one.  In fact I ran some benchmarks on a Sun 4
  20. and found that the running time of calloc() was proportional to k
  21. where K is the number of bytes allocated and initialized to 0.  (I
  22. also noticed that allocating new space took 4 times as long as
  23. reallocating freed space, perhaps virtual memory management is even
  24. more expensive than traversing the physical memory?)
  25.  
  26. In fact the time required for all the allocations in my algorithm was
  27. about 40 seconds on the Sun 4.  What a shame!  It seems that support
  28. for large blocks of data initialized to a constant byte value would be
  29. quite practical in hardware and a useful feature to support.
  30.  
  31. Mark Tillotson also suggests a second pass over each sublist of the
  32. input in order to clear all the bit flags that were set for that list.
  33. This makes the algorithm once again proportional to N (though with
  34. almost twice the constant factor) with a much smaller constant term,
  35. i.e. whatever it takes to allocate one copy of the flag array.  In
  36. that case I believe it makes sense to use a much smaller flag array,
  37. say 2^16, with a correspondingly larger array for head-of list, in
  38. this case 2^13 entries.  Then the constant term will be something on
  39. the order of 2^16 instructions (note you should be able to zero out
  40. the bit vector four bytes at a time).  Still I suspect for fairly
  41. small problem sizes a fast O(n log n) sort will still win, and it's
  42. quite possible that Mark Tillotson's hashing scheme has better
  43. average-case performance on any problem size.
  44.  
  45. -- David Karr (karr@cs.cornell.edu)
  46.  
  47.  
  48.