On 09/18/2016 04:26 PM, oldk1331 wrote:
> My point is, for List, one should not use index to get its element,
> because it's O(n) to do index.  In C++, std::list does not have
> operator[], "all STL sequences that support operator[] should
> do it in amortized constant time".

> I would even suggest we do the same, domains that export
> IndexedAggregate must have constant time elt(%, n).

Cool. You hit a point that I would also love to see. No, for
computations it is not enough if a function documentation says something
about what the function does, i.e., input/output behaviour. It is also
important to say something about the complexity of the implementation.

Yes, it is sometimes good to have functionality that maybe inefficient
in a certain implementation (like indexing in lists). That would allow
for easier prototyping where it is not yet clear how the final (most
efficient data structure will look like. But I am very much in favour of
having some functionality that says something about its complexity.
So one could have elt: .. -> .. and constantTimeElt: .. -> .. (I just
made up the name) and the latter would only be exported if the
implementtion assures that access is O(1). Or, we introduce separate
categories for this (maybe something like ConstantTimeElementAccess).
I'm open for discussion.


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 fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.

Reply via email to