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

Groups > comp.lang.forth > #41252

Re: dictionary layouts

Show all headers | View raw

Mat <dambere@web.de> writes:
>In this regard, I've noticed that by efficient=
> factoring, the last defined words are often temporary the most frequent us=
>ed ones. If so, probably the memory overhead for hashed dictionaries if avo=
>idable though a simple cache which list pointers to the most frequent used =
>words for example. This cache can be combined with either a traditional lin=
>ked list or a balanced binary tree (which I would prefer) as layout.
>
>I think such dictionary concept can probably be a good compromise between s=
>earch performance and memory usage.

No, it's worse in search performance, memory usage, and implementation
complexity.  Given the requirements of the Forth dictionary, hashing
with external chaining is hard to beat (especially if you don't
implement FORGET, but also if you do).  It's only slightly more
complex than a linked list, and uses only h-1 (where h is the number
of hash buckets) more memory, and improves search time by a factor of
h when the word is not found (because it is a number), and a little
less than h when the word is found.

In contrast, your cache consumes memory, too, and *increases* the
search time if the word is not found.  If you use hashing for your
cache, the overall code complexity is at least as bad as for a hashed
dictionary; if you use a balanced binary tree for your cache, the
complexity is even worse, and the access speed is slower than for a
hashed cache; if you use linear search through your cache, the
performance is slow.

Using a binary tree for the dictionary with n entries consumes n
additional cells compared to a linked list.  If I use that much extra
memory for hashing, e.g., external chaining with n hash buckets, the
average chain length is 1 and hashing is really fast.

Using a balanced binary tree has the same memory overhead, but is even
more complex to implement.  One particular problem is that, in Forth,
you can have the same name several times in the dictionary, and always
need to find the one that was inserted last.  I can see how to do that
with (unbalanced) binary trees (can you), but for balanced binary
trees that's non-trivial (unless you keep only the last entry in the
tree, but that costs another cell in each entry for the link to the
previous definition with the same name).

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2015: http://www.mpeforth.com/euroforth2015/euroforth2015.htm

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

Thread

dictionary layouts Mat <dambere@web.de> - 2015-08-09 04:39 -0700
  dictionary layouts Mark Wills <markwills1970@gmail.com> - 2015-08-09 11:37 -0700
    Re: dictionary layouts Mat <dambere@web.de> - 2015-08-09 12:30 -0700
  Re: dictionary layouts anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-08-10 08:05 +0000
    Re: dictionary layouts Mat <dambere@web.de> - 2015-08-10 03:57 -0700
    Re: dictionary layouts hughaguilar96@gmail.com - 2015-08-10 15:00 -0700
      Re: dictionary layouts Mat <dambere@web.de> - 2015-08-11 14:15 -0700

csiph-web