[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: FW: data structure vs. mathematical structure (was: [Axiom-developer

From: Bill Page
Subject: RE: FW: data structure vs. mathematical structure (was: [Axiom-developer] Graph theory)
Date: Mon, 13 Nov 2006 23:35:24 -0500


On November 13, 2006 10:17 PM you wrote:
> ... 
> [ Is it normal that I don't see Ralf's messages? ]

I believe that all messages that I received recently from Ralf are
here in the axiom-developer email archive:

which means that under normal circumstances these would also have
been forwarded to you. Are you missing some?

> Bill Page writes:
> ...
> | 
> | All domains that have SetCategory are required to have a hash
> | into SmallInteger.
> That is not a mathematical requirement.

I would tend to agree but perhaps Kurt Gödel would not have... ;-)

[Concerning the complexity of Set(T) for some type T ...]

> | I suppose that this means that the cost of adding
> | new elements is independent of Type T.
> Why?

hash makes testing equality O(1).

Axiom's implementation of Set is rather primitive.


Set(S:SetCategory): FiniteSetAggregate S

++ \spad{insert(x,t)} and \spad{remove(x,t)} is \spad{O(n)}
      insert_!(x, s) ==
        for k in minIndex s .. maxIndex s repeat
          s.k = x => return s
        insert_!(x, s, inc maxIndex s)

Bill Page.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]