The entries are short (4 bytes) and the key is the entire entry. My understanding is that in this situation a hash table has no benefit. Is this correct?
I should emphasize that the entries coming in are random in nature and all that is needed to be determined is if a new 4-byte entry coming in is already present or is unique to the list. This is because processing is performed on new entries (the entries are the key for that processing), but that processing should not be duplicated. Once the input stream has been exhausted the list of entries can be discarded. In most situations the list size would be less than a few hundred entries. However, there is no specified upper limit (other than running out of memory) and the size could potentially be a million entire or more. -----Original Message----- From: IBM Mainframe Assembler List [mailto:[email protected]] On Behalf Of Paul Gilmartin Sent: Monday, August 23, 2010 11:56 AM To: [email protected] Subject: Re: Efficient Memory List On Aug 23, 2010, at 08:45, Patrick Roehl wrote: > > > 3) The binary search from step 1 indicates where the new entry should be > inserted. To add the entry to the list, individual entries are moved one > at a time (to avoid overlapping moves) to open a spot in the list for the > new entry. > At least, keep the active entries at the top of the storage area and MVCL downward to avoid overlapping moves while avoiding the overhead of one-at-a-time. Would name/token services work for you? What's its storage overhead? At some large number of entries it will outperform moving the list for each new entry. At some larger number it becomes an abuse of system resources. Hash sounds good. -- gil
