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!'.
I suspect that when insert!([key, entry], tab)
finds some key' = key in tab, then is compares entry = entry',
and acts futher depending on the result of this comparison.
Is this so?
If yes, then my application, probably, needs to pre-analyse
member?(key, tab) in order to avoid an expensive and unneeded operation
of entry = entry'.
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.
For example, in the Glasgow Haskell library, data Map ...
has the internal representation like
data Tree kKey eEntry =
Leaf kKey eEntry | Node (Tree kKey eEntry) (Tree kKey eEntry)
-- left branch right branch
(may be, not precisely this).
If any total ordering `compare' (of Ord) is declared for kKey, then
* the operations of (lookup key tab) and (insert key entry tab)
are possible,
* they cost O( log(card(table)) ),
* lookup is by applying compare key key' (or key > key') several
times in a binary search,
* insert also implies re-balancing of a tree, but it is also of
O( log(card(table)) ).
The thing is explained clearly in docs and also works reliably
(it is a pity that it is not in the Standard).
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).
For HashTable, I cannot tell what may be (in my example), for example,
the cost of `insert!'.
Meanwhile, I use HashTable. But in future I shall need to rewise its
usage, for the thing may ruin the performance.
Regards,
------
Sergei
[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.
