On 02/04/2012 06:13 PM, Serge D. Mechveliani wrote:
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?
dropWhileInStr(p: Character -> Boolean, xs: String): String ==
empty? xs => xs
i := 1; while p qelt(xs,i) repeat i := i+1
i = 1 => xs
l := #xs
s: String := new(l - i+1)
for j in i..l for k in 1.. repeat qsetelt!(s, k, qelt(xs, j))
s
dropWhile(p: Character -> Boolean, xs: List Character) :
List Character ==
empty? xs => xs
p first(xs) => dropWhile(p, rest xs)
xs
Is this more efficient?
In the list case I guess using a loop instead of recursive call is a
little more efficient.
LC ==> List Character
dropWhile(p: Character -> Boolean, xs: LC): LC ==
while not empty? xs and p first xs repeat xs := rest xs
xs
Both versions are O(n) where n is the string/list length. The O(n^2)
that Waldek mentioned comes from the fact that each single delete
operation costs O(n) and you may have to delete the whole string, i.e. n
times.
Ralf
--
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.
