Serge D. Mechveliani wrote:
>
> On Mon, Mar 19, 2012 at 06:24:07PM +0100, Waldek Hebisch wrote:
> > Ralf Hemmecke wrote:
> > >
> > > Personally, I tend to agree that there should be a hashtable that does
> > > not impose SetCategory on its second argument. Of course, one cannot
> > > output such a table, but maybe the user doesn't want output anyway.
> > >
> >
> > SetCategory is not very important, but BasicType (that is equality)
> > is crucial.
>
>
> It is desirable to understand how this `=' is used for the second
> (Entry) argument in the operations `search' and `insert!'.
Not used at all. I meant equality of keys. AFAICS SetCategory
for Entry is used to define bunch of extra functions which
are uninteresting to you. In fact, we probably should not
require SetCategory for Entry and define those functions
only conditionally.
>
> And the main thing which I cannot understand about Tables in Axiom is:
> whether it has a regular
> balanced binary search tree
>
> for defining a _finite map_ Key -> Entry.
No.
> And in Axiom, HashTable and BinarySeachTree look like something
> different and difficult to understand.
> For BinarySeachTree, I do not see how to search a value for a key
> (because it has only one type parameter S).
This is not the main problem (you could use a record with key and
entry components as S) -- the real problem is that search function
is unimplemented. The second problem is that it performs no
balancing (so the worst case is linear).
> For HashTable, I cannot tell what may be (in my example), for example,
> the cost of `insert!'.
Hash tables give very good average access time assuming that
hash function produces values which are pseudorandom enough.
Lisp hash tables may have bad performance for some types of
keys (basically arrays), because some implementations use
the same hash function for all types and language definition
essentially forbids defining a single hash function which
works well for all types.
> Meanwhile, I use HashTable. But in future I shall need to rewise its
> usage, for the thing may ruin the performance.
As I wrote, there are limitations on types of keys. Basically,
if you have record with more than two components or an
array inside the keys, then it will not work. In particular,
you can not use Type as component of key. Any in itself is
OK because it uses two component record (which is OK) and
hidden compoment is an SExpression which is OK too. But
of course the actual value stored in Any must be of appropriate
type...
AFAICS your ConstructedDomain contains Type inside. This
is tricky case, it will work most of the time but is not
guaranteed to always work. Basically, as optimization FriCAS
runtime tries to construct given type only once. This
is done by keeping a cache of already constructed types.
But size of cache is limited and if you construct so many types
that you overflow the cache then FriCAS may construct the
same type second time. Technically it means that most of
the time Lisp EQ function will correctly compute equality
of types, but it type is constructed second time EQ will
return false and one needs to use more complicated function
to establish equality. For types HashTable will use Lisp
EQ, so it may think that two types which are in equal are
not and give wrong results.
Also, your ConstructedDomain seem to store almost arbitrary
FriCAS values inside. Of popular domains Expression and
DistributedMultivariatePolynomial are not good as keys.
So it seems that you can not use your ConstructedDomain as
HashTable keys.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
