Serge D. Mechveliani wrote:
>
> I care mainly of O(n) for dropWhileInStr and dropWhile for a data of
> length n,
> and assume that p(x) costs 1.
> And you wrote about O(n^2) in the worst case for the initial version of
> dropWhileInStr for String. This O(n^2) has frightened me.
Of course how bad it is depends on n. If you want to slurp some
huge expression as a string and then one by one delete token
from it then you will get bad performance. OTOH by keeping
a single 'current position' variable you can get similar
effect and reasonable performance.
> Now: as 'empty?', 'first' and 'rest' take only few (O(1)?) machine
> instructions, dropWhile occurs n times (not 2-3) faster (in the worst
> case) than the initial version of dropWhileInStr.
> Right?
Depends. Your orignal version would work both with lists and
strings. On lists delete(x, 1) is O(1). On strings is O(n).
So on lists your new versions just gains a constant factor.
Since the new version can not be applied to strings I compared
behaviour on lists. Of course, when you run your new version
on lists and original on strings then new version will be
about n times faster. But at the same time original version
when run on long list will be about n times faster then
when it is run on strings.
> Also I always programmed List in this style in Haskell, and had several
> examples in Lisp (somewhat 15 years ago). And all the examples with long
> lists, with composed functions, showed that what is expected to be O(n)
> also shows O(n) on practice, and what is expected as O(n^2) also shows
> O(n^2) on practice.
> Now, this important property breaks when I use FriCAS String with `delete'.
> But I hope that it remains O(n) for dropWhile for List.
Well, arrays have quite different performance properties than lists,
with arrays I can poke at element at some index i confident that
this is O(1), but with list it would be O(n)...
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
