Serge D. Mechveliani wrote:
>
> Thanks to people for their advices.
> To my
>
> >> I define
> >> 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.
> > [..]
>
> Is a string represented in FriCAS as a C array?
FriCAS uses Lisp strings which are stored as arrays.
> Is this total copying due to the array representation?
Not exactly. Lisp arrays may be "displaced" which means
that one array may take its storage from middle of another
arrays. This is somewhat like using pointers in C,
however displaced array besides pointer to data has also
header with metadata. When using displaced arrays delete
could just create new header without copying actual data.
I did not check if it is possible to have displaced strings
in Lisp, but in principle FriCAS could use displaced arrays
of characters for strings.
However, this has some drawbacks:
- operations on displaced arrays are slower than on normal ones,
if you allow mixing displaced arrays with normal all operations
must check if array is a normal one or a displaced one and
only then perform actual access
- for short string creating array header can cost almost the
same as copy (on 64-bit machine the header is likely to take
24 bytes).
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. So this version performs two
function calls per charater dropped (one for p and the
recursive call). Generic one will have 3 extra function
calls. In FriCAS function calls cost time comparable
with execution of tens of normal instructions, so counting
calls give you reasonable approximation to execution
time as long as each call is doing only little work.
Of course, speed will also depend on how costly is p,
it may well happen that p is doing tens of calls, making
other differences irrelevant.
Without measurement it is hard to compare your version with
generic one that I gave, but _may_ they have similar
efficiency. Generic version have to walk list twice,
but that can be done via loops (I am not sure if FriCAS
library uses tail call or loop). So assuming efficient
library the main cost wil be call to 'p' and here negation
introduces extra call, so again we have 2 calls per character
dropped.
BTW: When I care about speed I am trying to organize code
as a loop and if possible have only primitive operations
inside inner loop. Of course many callse are unavoidable,
but then I trying to minimize number of them.
--
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.
