>
> > IndexedList is useful if somebody wants to port code which
> > uses differernt indexing.
>
> My point is, for List, one should not use index to get its element,
> because it's O(n) to do index.
Indexing on list has it good uses and we should not forbid
it because abuse may lead to slow programs.
> 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).
Well, I against tying complexity to types. Types will not
prevent writing inefficient code. Actually, unnecessary restrictions
may lead to workarounds which decrease efficiency.
And any extra type distincion means less opportunity to
share code, so works against generic coding.
There is also practical thing: suppose that we can compute
a function using code which costs log(n) clocks where n
is size of the problem, or we can use table lookup which
is O(n). At first glance table lookup looks like pure
win, we get O(1) instead of O(log(n)). But on modern
machines array lookup may take as much as 200 clocks,
while for realistic sizes (such that table fits into RAM)
log(n) will be less than 40. So in practice recomputation
may win, despite worse theoretical complexity. In
other words, to make informed deductions about execution
time you need to consider much more than complexity.
Sure, complexity is useful first approximation, but
far from full story. Anyway, in case above forbiding
logarithmic 'elt' would be stupid when it is faster
than O(1) version.
--
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 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.
