[Maude-help] Efficiency question: lists vs. vectors

[Steven Eker]

It's best to avoid 60 element constructors unless your sort structure is 
trivial since Maude compiles the sort declarations for each operator into a 
lookup structure which is potentially exponential in the arity.

As always it would help if you posted code - particularly now since I'm doing 
the final optimization and bug fixing pass for the Maude 2.5 release.

I suspect that associative lists would not work for your permutation code, but 
the MAP data structure defined in the prelude might work for both if you 
instantiated the first parameter by Nat and you do permutations using the 
insert operator (which overwrites the previous association). Recursive looping 
over the elements can be done thus:

fmod SUM is inc MAP{Nat, Float}
  op sum : Map{Nat, Float} -> Float .
var N : Nat .
var F : Float .
var M : Map{Nat, Float} .
  eq sum((N |-> F, M)) = F + sum(M) .
  eq sum(empty) = 0.0 .
endfm

red sum( (0 |-> 3.0, 1 |-> 3.5, 2 |-> -2.0) ) .
 
The is a mechanism for added C++ built-ins (it used for all the built-in 
functions that currently exist) but it is not documented and changes as 
needed. Also to work properly with the rest of Maude a built-in function needs 
to be able to export its hooks (so it works with upModule() among other 
things) so it is a fair amount of work.

Steven Eker

On Saturday 13 March 2010, Todd Wilson wrote:
> I am writing a functional module to deal with 60-element vectors that
> support operations that (1) permute the elements of the vector and (2)
> recursively loop over the elements in order, and I'm trying to find the
> most efficient representation, since I will be performing thousands of
> these operations at a time.
> 
> A sixty-argument constructor seems to work well for the permutation
> operations, and (non-associative) lists seem to work well for the
> recursive operations, but each data structure doesn't seem to support
> the other kind of operation well.  Is there anything better than
> converting the vector to a list in order to do a recursion over it, and
> then converting the result back to a vector when I'm done, so that later
> permutations on it are efficient?  Is there any documentation for the
> C++/special interface, so that I might define my own "built-in" module
> that supports all of my operations efficiently?
> 
> Todd Wilson
> _______________________________________________
> Maude-help mailing list
> Maude-help at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/maude-help
>