oldk1331 wrote:
>
> I have updated the patch:
>
> https://github.com/oldk1331/fricas/commit/5d0a6c2dc30825d53ddeafac6d0df1df0edf42ce.patch
>
> more efficient Rep for Queue and Dequeue
>
> I use destructive operations in map, but I think it's correct.
> I fixed a bug that 'construct' requires a copy of argument.
I am affraid there are few problems with the patch:
1) You add default implementation to QueueAggregate. In such
case you need to add QueueAggregate to CATDOMS in Makefile.in
2) Consider the following (with current implementation):
(1) -> x := queue([])$Queue(Integer)
(1) []
Type: Queue(Integer)
(2) -> x := insert!(1, x)
(2) [1]
Type: Queue(Integer)
(3) -> front(x)
(3) 1
Type: PositiveInteger
AFAICS it will fail with your code. You can replaces front
with 'dequeue!' or intead of 'insert!' use 'reverse!' to
construct a dequeue and have the same problem.
3) More generaly I am concerned by complexity -- your code is
significantly more complex than the old code. This means
slower code and higher chance of bugs. Of course, bugs can
be worked out, but it is not clear if we will get any practical
gain in speed. Namely, small number of elements is a frequent
case, there are a lot of parts in FriCAS which use quadratic
algorithms and since they work with small number of elements
are fast enough. OTOH if for some computation queue operations
become critical it is likely that array based queue will
give better performance.
4) Classical version with pointer to tail needs something like:
enqueue!(e, q) ==
empty?(q) => q.front := q.rear := e
tail(q.rear) := [e]
q.rear := tail(q.rear)
with most other Queue routines essentially unchanged compared
to current version. This gives O(1) insertion and small
complexity (but extractBottom! in Dequeue is still O(n)).
>
> https://github.com/oldk1331/fricas/commit/f806cd1b1e0044888dbac27fe3a5e96a89de8454.patch
>
> add a simple testcase for dequeue
>
> The test is very simple and basic, doesn't cover the case
> that 'balance!' is called.
>
> What do you think a test file should contain? A domain's
> exclusive operations? Every operations of a domain?
> Tests cover all/most branches?
For simple domains we should aim to execute all nontrivial
unique lines. Unique means that snippets which are copied
to another routine need only one test. Once code gets
more complex we should excercise various cases/boundary
conditions. In extreme cases it makes sense to try
exhaustive testing for all "small" structures. To be
more concrete: basic operations on linked lists are
simple enough that very little tests are needed: code
just works as written. OTOH I once created implementation
of AVL trees. In a sense this was code from a texbook,
but I had to do some modifications. Anyway, after code
passed usual tests I tried it on all trees of limited size.
The extra test found several bugs that were missed by
simpler tests.
The point is that for complex code you need _much more_
tests than for simple code. Part of problem is that if
you forget about some special case during coding you
are quite likely to forget about it during testing.
Extra remark: several core domains have no tests
which applies directly to them, but they are heavily
used by other domains and so get a lot of testing
as byproduct of testing other code. OTOH things
which are unused by other parts (like Queue and
friends) needs their on tests,
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
