On Fri, Feb 03, 2012 at 11:39:55PM +0100, Waldek Hebisch wrote: > Serge D. Mechveliani wrote: > > [..] > > >> dropWhileInStr(p: Character -> Bool, xs: String) : String == > > >> empty? xs => "" > > >> p first(xs) => dropWhileInStr(p, delete(xs, 1)) > > >> xs > > >> > > >> for dropping first letters from xs which satisfy a predicate p. > > >> It this a reasonable code? > > > > Waldek Hebish writes > > > > > IMHO reasonable, but potentally quite inefficient: delete creates copy. > > > If the string has length n delete allocates new string of length n-1 > > > and then copies characters. > > > [..] > >
> [..] > In other words by _not_ providing O(1) delete we can make other > operations faster. > > > What may be an efficient code for dropWileInStr ? > > I posted a generic version earlier -- it should be > reasonably efficient. If you want to be more efficient > than explicitely loop over characters (unfortunately, this > requires different code for strings and lists). > > > Consider the List approach: > > > > dropWhile(p: Character -> Boolean, xs: List Character) : > > List Character == > > empty? xs => xs > > p first(xs) => dropWhile(p, rest xs) > > xs > > Is this more efficient? > > For lists it should be more efficient than your original version, possibly > about 2-3 times. Namely, for List 'empty?', 'first' and 'rest' are > primitive operations which compile to few machine instructions. ? 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. 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? 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. (?) Thanks, ------ Sergei [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.
