I need to build a hash which keys on strings. I am using
EQUAL as the test when building the hash to assure that no
two keys are strings which contain the same characters.
However, after finishing building the hash, I would like
to change the test from EQUAL to EQ. Is this possible?
Jim Newton wrote:
> I need to build a hash which keys on strings. I am using
> EQUAL as the test when building the hash to assure that no
> two keys are strings which contain the same characters.
> However, after finishing building the hash, I would like
> to change the test from EQUAL to EQ. Is this possible?
I don't know of a desired solution like you describe but why not the
convert strings to symbols? If you use symbols you can just use a
hashtable that tests with eq from the beginning.
From: Bulent Murtezaoglu
Subject: Re: changing the test of a hash table.
Date:
Message-ID: <87br94ok37.fsf@p4.internal>
>>>>> "bondowine" == bondowine <·········@yahoo.com> writes:
bondowine> Jim Newton wrote:
>> I need to build a hash which keys on strings. I am using EQUAL
>> as the test when building the hash to assure that no two keys
>> are strings which contain the same characters. However, after
>> finishing building the hash, I would like to change the test
>> from EQUAL to EQ. Is this possible?
bondowine> I don't know of a desired solution like you describe
bondowine> but why not the convert strings to symbols? If you use
bondowine> symbols you can just use a hashtable that tests with eq
bondowine> from the beginning.
Um, or no seperate hash table at all: the info keyed off the symbol could
be stuck into the symbol's property list. I know symbol plists are no
longer in style, but if you'll create symbols anyway you might as well
use the facility. I'd at least benchmark that if efficiency is important.
BM
From: Bulent Murtezaoglu
Subject: Re: changing the test of a hash table.
Date:
Message-ID: <877jjsojug.fsf@p4.internal>
>>>>> "BM" == Bulent Murtezaoglu <··@acm.org> writes:
[...]
BM> Um, or no seperate hash table at all: the info keyed off the
BM> symbol could be stuck into the symbol's property list. I know
BM> symbol plists are no longer in style, but if you'll create
BM> symbols anyway you might as well use the facility. I'd at
BM> least benchmark that if efficiency is important.
Heh, never mind me. As Ron Garrett says, symbol-value will be a far better
idea than plists (unless, I suppose, you are using a plist).
BM
In article <···············@individual.net>,
Jim Newton <·····@rdrop.com> wrote:
> I need to build a hash which keys on strings. I am using
> EQUAL as the test when building the hash to assure that no
> two keys are strings which contain the same characters.
> However, after finishing building the hash, I would like
> to change the test from EQUAL to EQ. Is this possible?
Use symbols (and symbol-value) and packages instead of hash tables. A
package does precisely what you say you need.
rg
From: Christophe Rhodes
Subject: Re: changing the test of a hash table.
Date:
Message-ID: <sqis3c27jm.fsf@cam.ac.uk>
Jim Newton <·····@rdrop.com> writes:
> I need to build a hash which keys on strings. I am using
> EQUAL as the test when building the hash to assure that no
> two keys are strings which contain the same characters.
> However, after finishing building the hash, I would like
> to change the test from EQUAL to EQ. Is this possible?
Well, no, not in general, but you could quite trivially create a new
EQ-test hash table from your EQUAL one (using maphash,
with-hash-table-iterator or loop) when you know that your table is
finished.
Christophe
i was afraid of that. actually i have 1 very large hash
table with aroun 100,000 entries and about 100,000
smaller hash tables. it would be nice not to have to
copy them.
thanks for the info.
-jim
Christophe Rhodes wrote:
> Jim Newton <·····@rdrop.com> writes:
>
>
>>I need to build a hash which keys on strings. I am using
>>EQUAL as the test when building the hash to assure that no
>>two keys are strings which contain the same characters.
>>However, after finishing building the hash, I would like
>>to change the test from EQUAL to EQ. Is this possible?
>
>
> Well, no, not in general, but you could quite trivially create a new
> EQ-test hash table from your EQUAL one (using maphash,
> with-hash-table-iterator or loop) when you know that your table is
> finished.
>
> Christophe
In article <···············@individual.net>,
Jim Newton <·····@rdrop.com> wrote:
> i was afraid of that. actually i have 1 very large hash
> table with aroun 100,000 entries and about 100,000
> smaller hash tables. it would be nice not to have to
> copy them.
Even if there were a way to change the test of the hash table, it would
have to do pretty much the same work as copying the table. Every key
would have to be re-hashed, since different tests usually require
different hash functions.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Jim Newton wrote:
> i was afraid of that. actually i have 1 very large hash
> table with aroun 100,000 entries and about 100,000
> smaller hash tables. it would be nice not to have to
> copy them.
I had a similar problem. You can always INTERN the strings in some
package and then use EQ in the hash table on the resulting symbols. I
found that this solved my problem nicely.
In alternative, you can use plists on the symbols, provided that the
symbols are interned in a separate package and that the property
indicator you are using is completely under your control.
Cheers
--
Marco
>
> thanks for the info.
> -jim
>
> Christophe Rhodes wrote:
>
>> Jim Newton <·····@rdrop.com> writes:
>>
>>
>>> I need to build a hash which keys on strings. I am using
>>> EQUAL as the test when building the hash to assure that no
>>> two keys are strings which contain the same characters.
>>> However, after finishing building the hash, I would like
>>> to change the test from EQUAL to EQ. Is this possible?
>>
>>
>>
>> Well, no, not in general, but you could quite trivially create a new
>> EQ-test hash table from your EQUAL one (using maphash,
>> with-hash-table-iterator or loop) when you know that your table is
>> finished.
>>
>> Christophe
Marco Antoniotti <·······@cs.nyu.edu> writes:
> Jim Newton wrote:
> >>> I need to build a hash which keys on strings.
> > i was afraid of that. actually i have 1 very large hash table
> I had a similar problem. You can always INTERN the strings in some
> package and then use EQ in the hash table on the resulting symbols. I
> found that this solved my problem nicely.
But then in effect you're using the implementation's package
algorithms, possibly an EQUAL hash-table:-) which the OP wanted to
avoid. Yet your solution is likely to yield faster access in the later
phase since presumably SYMBOL-VALUE or SYMBOL-PLIST is faster than
GETHASH.
This general scenario raises two topics in my head:
1) is there a real performance bottleneck and would switching to EQ
hashtables really boost performance in the implementation that the
OP uses?
2) The OP's scenario falls in the broader category of switching data
structures based on the use. The OP mentions two consecutive
phases: a) filling (using EQUAL) and b) "using" (where EQ is most
appropriate).
Likewise, some other dataset could be represented as a binary tree in an
initial insertion phase, later as an ordered array.
It's a matter of optimization whether it's worth to use two
representations and switch between them, depending on the current
phase of the program, taking into consideration the cost of migrating
one data structure into another.
Another problem then is whether object identity is deemed important
for the object that represents that data. I.e. if some module stores a
reference to the initial object (e.g. a list), it won't notice when
the actual data structure is later converted to something else.
CHANGE-CLASS is IMHO not the necesary solution.
There are two solution paths:
A) static: explicitly model the change of representation in code.
Your program becomes
(use (convert (gather data)))
B) dynamic: some program entity monitors the current usage of the data
structure (e.g. size and kind of access) and may change the
internal representation transparently to the callers. This
scenario also has its uses. CHANGE-CLASS could be used here, but
maybe it's just better to use an indirection slot within the object.
Regards,
Jorg Hohle
Telekom/T-Systems Technology Center