Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #2017

Re: Sizing a dictionary

Show key headers only | View raw

jdaw1 <jdawiseman@gmail.com> writes:

> At language level ≥2 dictionaries can created with length 0, as they grow automatically. But I always create them to be the correct length, to match the maximum value of currentdict length. 
>
> These lengths are sometimes checked with:
>
> 	/dict {dup 1 add dict dup 3 -1 roll /DictionaryOriginalSize exch put} bind def
>
> 	/end {currentdict /DictionaryOriginalSize known {DictionaryOriginalSize currentdict length 1 sub lt {TypeOfPagesBeingRendered = DictionaryOriginalSize = currentdict length 1 sub = (###) =} if} if end} bind def
>
>
>
> In https://groups.google.com/forum/#!topic/comp.lang.postscript/hc9-b2W5tY0 luser- -droog wrote:
>> `10 dict` creates a dict with capacity for 10 elements 
>> (rule of thumb: double the expected size needed for speedy hash lookups)
>
> The quoted text advising aiming for double size. Oooh: that’s new to me. Please, is there evidence of this? It feels like messy programming, so I’d do it only reluctantly. Is there background that I should read? Please say more.

http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables

When the Apple LaserWriter first came out, I bought the PostScript Red
Book and started figuring out how PostScript Level I was implemented.
In the case of dictionaries, I figured out (modulo my foggy memory) that
if you asked for a dictionary of size smaller than 10, it was promoted
to 10.  Also, whatever size you specified, the internal dictionary was
allocated to be 25% bigger than you asked.  I vaguely recall that hash
collisions were resolved by linear probing using a step of one location.
Collisions become more frequent as the dictionary fills up (or is
constructed) so a dictionary should never be allowed to become more than
80% full (this is the conventional figure, I don't know the original
source).  Note that the 25% premium allows the dictionary to be just 80%
full when you've filled it with the expected number of elements.

See also: Knuth, vol. 3 "Sorting and Searching" section 6.4 Hashing
Also: Google "hash table 80% full" (without the quotes).

Scott
-- 
Scott Hemphill	hemphill@alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear

Back to comp.lang.postscript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Sizing a dictionary jdaw1 <jdawiseman@gmail.com> - 2014-09-03 03:57 -0700
  Re: Sizing a dictionary Scott Hemphill <hemphill@hemphills.net> - 2014-09-04 18:04 -0400
    Re: Sizing a dictionary luser- -droog <mijoryx@yahoo.com> - 2014-09-04 16:59 -0700
      Re: Sizing a dictionary jdaw1 <jdawiseman@gmail.com> - 2014-09-06 03:31 -0700
        Re: Sizing a dictionary Scott Hemphill <hemphill@hemphills.net> - 2014-09-09 13:35 -0400
          Re: Sizing a dictionary luser- -droog <mijoryx@yahoo.com> - 2014-09-13 01:11 -0700
            Re: Sizing a dictionary Scott Hemphill <hemphill@hemphills.net> - 2014-09-13 12:04 -0400

csiph-web