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

Groups > comp.lang.forth > #33992

Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search

From "Rod Pemberton" <buzzoff@nonamewhichexists.cmm>
Newsgroups comp.lang.forth
Subject Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search
Date 2014-10-17 21:33 -0400
Organization Aioe.org NNTP Server
Message-ID <op.xnwjx41lmk81un@localhost> (permalink)
References (4 earlier) <op.xnue6gpemk81un@localhost> <9sCdnTcocuD0093JnZ2dnUU7-L2dnZ2d@supernews.com> <GNKdnULWhZqxR93JnZ2dnUU7-eOdnZ2d@supernews.com> <op.xnwg0gx1mk81un@localhost> <Y-2dnSXzi-tFK9zJnZ2dnUU7-YWdnZ2d@supernews.com>

Show all headers | View raw

On Fri, 17 Oct 2014 20:39:51 -0400, Elizabeth D. Rather  
<erather@forth.com> wrote:
> On 10/17/14 2:30 PM, Rod Pemberton wrote:
>> On Fri, 17 Oct 2014 04:58:20 -0400, Andrew Haley
>> <andrew29@littlepinkcloud.invalid> wrote:
>>> Elizabeth D. Rather <erather@forth.com> wrote:
>>>> On 10/16/14 11:55 AM, Rod Pemberton wrote:
>>>>> On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather
>>>>> <erather@forth.com> wrote:

>>>>>> The requirement (from Forth 2000X) is "When searching a word list  
>>>>>> for
>>>>>> a definition name, the system shall search each word list from its
>>>>>> last definition to its first." There is no restriction on how the
>>>>>> dictionary is organized or searched, providing that the most recent
>>>>>> definition of a word will be found in preference to any prior
>>>>>> definition that may exist in the current search order.
>>>>>
>>>>> Unfortunately, requiring that the most recent definition of a word
>>>>> to be
>>>>> found requires that the order of *all* other words be preserved in  
>>>>> time
>>>>> order they were defined.
>>>>
>>>> That is correct. However, 40 years of use has found this not in the
>>>> least "unfortunate" but rather an asset that most users depend upon.
>>>
>>> Actually not: it only requires that identically-named words be
>>> preserved in the order they were defined.  Otherwise, hashed
>>> dictionaries could not work.
>>>
>>
>> Are you saying it's valid to change this defining order?
>>
>> : TODO 1 . ;
>> : FIXME TODO ;
>> : HELP1 FIXME ;
>> : TODO  2 . ;
>> : FIXME TODO ;
>> : HELP2 FIXME ;
>>
>> E.g., to this order?
>>
>> : TODO 1 . ;
>> : TODO  2 . ;
>> : FIXME TODO ;
>> : FIXME TODO ;
>> : HELP1 FIXME ;
>> : HELP2 FIXME ;
>>
>> That has the identically-named words preserved in the order
>> they were defined, which is what you just stated.  Clearly,
>> this doesn't and wouldn't ever work correctly.
>
> Yes, but you're trying to reference them before they've been
> compiled at all. Nobody ever said that would work.

The entire point was that they must be compiled in a certain order
to preserve their relationships.  Are you saying that _after_
the words have been compiled, then the dictionary is reorganized
and/or sorted?  What's the point in that?  Each definition
consumes space.  Sorting wastes time.  The best option would
be to leave them where they are in the linked-list and provide
an additional layer of indexing.  Of course, there needs to
be a point in time when that operation is cost-effective.
You're not going to do that over and over again or continuously.
So, you'd do it for the system dictionary, but not for user apps.


Rod Pemberton

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

Thread

Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search mfanyikazi@gmail.com - 2014-10-11 08:52 -0700
  Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-11 08:06 -1000
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search mfanyikazi@gmail.com - 2014-10-12 02:46 -0700
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-12 08:33 -1000
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 17:55 -0400
          Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-16 13:02 -1000
            Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-10-17 03:58 -0500
              Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-17 07:39 -1000
              Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-17 20:30 -0400
                Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-17 14:39 -1000
                Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-17 21:33 -0400
                Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-17 21:51 -1000
                Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search Bernd Paysan <bernd.paysan@gmx.de> - 2014-10-18 13:51 +0200
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search dwarman@davidwarman.net - 2014-10-17 08:38 -0700
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 17:54 -0400
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search hughaguilar96@yahoo.com - 2014-10-17 19:33 -0700
  Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search Bernd Paysan <bernd.paysan@gmx.de> - 2014-10-11 22:39 +0200
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search mfanyikazi@gmail.com - 2014-10-12 02:50 -0700
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-12 08:38 -1000
  Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search hughaguilar96@yahoo.com - 2014-10-11 15:05 -0700
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-12 12:14 +0200
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search mfanyikazi@gmail.com - 2014-10-12 10:06 -0700
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search hughaguilar96@yahoo.com - 2014-10-12 15:50 -0700
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-13 01:02 +0200
          Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search jfong@ms4.hinet.net - 2014-10-12 21:11 -0700
            Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search Michael Barry <barrym95838@yahoo.com> - 2014-10-12 22:01 -0700
            Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-14 02:06 +0200
          Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 18:11 -0400
            Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-17 11:38 +0200
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 18:06 -0400
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-17 11:38 +0200
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 18:04 -0400
  Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 17:53 -0400

csiph-web