Sum of digits
Hi,
I wanted to compare how to do sum of digits in Scala and Pico Lisp, and
to my surprise my Pico Lisp version was much slower than my Scala version.
Well, Scala is a compiled language, but I hadn't anticipated that big a
difference. My test input number was a rather big one: (2^100 + 3^200)^300
(#8776;1.885 x 10^28627)
My Scala code was like this:
def sumOfDigits(n: BigInt): BigInt = n.toString.map{ _.asDigit
}.foldLeft(0){ _+_ }
val big = (2:BigInt).pow(100)+(3:BigInt).pow(200)
sumOfDigits(big.pow(300))
- 128458
My Pico Lisp code was like this:
(de sumOfDigits (N)
(apply + (mapcar format (chop (format N )
(setq Big (+ (** 2 100) (** 3 200)))
(sumOfDigits (** Big 300))
- 128458
Could I have written the Pico Lisp code differently to make it faster?
/Jon
--
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
Re: Blob problems
It worked OK, and I realized I had another relation with the same setup:
(class +Awords +Entity)
(rel words (+Blob))
(rel counts (+Blob))
(dm put (Key Val)
(put! This Key T)
(out (blob This Key)
(prinl Val)))
The above works but I wanted to follow your advice on this one too, so
I changed it to:
(dm put (Key Val)
(super This Key T)
(out (blob This Key)
(prinl Val)))
However, I'm getting:
!? (has (meta This Var) Val (get This Var))
has -- Bad message
When I run the code which is using the above like this:
(let Awords (new! '(+Awords))
(put Awords 'words Words)
(put Awords 'counts (mapcar val Words))
(put A 'words Awords))
Any ides on why the super version isn't working out this time?
/Henrik
On Wed, Sep 16, 2009 at 7:55 AM, Alexander Burger a...@software-lab.de wro=
te:
Hi Henrik,
(class +Article +Entity)
(rel aid =A0 =A0 =A0 (+Key +Number))
(rel title =A0 =A0 (+String))
(rel type =A0 =A0 =A0(+String))
(rel htmlUrl =A0 (+Key +String))
(rel body =A0 =A0 =A0(+Blob))
(dm put (Key Val)
=A0 =A0(if (=3D Key 'body)
=A0 =A0 =A0 (prog
=A0 =A0 =A0 =A0 =A0(put! This 'body T)
=A0 =A0 =A0 =A0 =A0(out (blob This 'body)
=A0 =A0 =A0 =A0 =A0 =A0 (prinl Val)))
=A0 =A0 =A0 (super Key Val)))
I didn't try this code, and have no direct explanation why you get an
error upon re-import, but I see a different problem:
It is not good to nest 'put!' within 'put'. 'put!' builds its own
transaction with 'dbSync' and 'commit'. This means, that you get a
preliminary 'commit', which will unlock the database too early.
So the 'put!' above should at least be a simple 'put'. Then
we might simply use 'super' instead:
=A0 (dm put (Key Val)
=A0 =A0 =A0(ifn (=3D=3D Key 'body)
=A0 =A0 =A0 =A0 (super Key Val)
=A0 =A0 =A0 =A0 (super 'body T)
=A0 =A0 =A0 =A0 (out (blob This 'body)
=A0 =A0 =A0 =A0 =A0 =A0(prinl Val) ) ) )
As usual, this 'put' must run in a transaction (surrounded by 'dbSync'
and 'commit'), of course.
I don't know if this solves the original problem though.
The same situation ('put!' inside 'lose!') we have here:
(dm lose! ()
=A0 =A0(call 'rm (blob This 'body))
=A0 =A0(put! This 'body NIL)
=A0 =A0(super))
In fact, I never directly remove blobs, and rely on the nightly garbage
collection to have them cleaned up. So the above 'lose!' method might
simply be omitted.
Cheers,
- Alex
--
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=3dunsubscribe
--
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
Re: Sum of digits
Hi Jon, to my surprise my Pico Lisp version was much slower than my Scala version. You've hit upon an old problem. Conversion from internal to decimal representation in PicoLisp takes too long. We had a similar discussion here some time ago, initiated by Tomas Hlavaty. You can see this easily if you look at the steps separately (I put a 'T' at the end of each line to avoid the actual output of the big numbers): : (bench (** Big 300)) T 0.049 sec - T This is very short in comparison to decimal formatting: : (bench (format (** Big 300))) T 17.862 sec - T BTW, you can also directly 'chop' a number, without the need of 'format'ing it. But this won't change anything either: : (bench (chop (** Big 300))) T 17.814 sec - T Same goes for direct printing: : (bench (out /dev/null (println (** Big 300 T 18.079 sec - T In all these cases, the final conversion took about 360 times longer than the actual calculation. Could I have written the Pico Lisp code differently to make it faster? Not the Lisp code, the conversion goes completely in the kernel. But I have also no better idea how to do a decimal conversion faster. Cheers, - Alex -- UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
Re: Blob problems
I might be inclined to think something similar normally, but in this case the only difference is: (put! This Key T) which works as opposed to (super This Key T) which doesn't. And that has absolutely nothing to do with A (an article). /Henrik On Sat, Sep 19, 2009 at 4:36 PM, Alexander Burger a...@software-lab.de wro= te: Hi Henrik, (let Awords (new! '(+Awords)) =A0 (put Awords 'words Words) =A0 (put Awords 'counts (mapcar val Words)) =A0 (put A 'words Awords)) 'A' probably is not an object of a class that knows about 'words'. However, I'm getting: !? (has (meta This Var) Val (get This Var)) has -- Bad message I also frequently get such an error, if some code does not match the E/R definitions. I would type here =A0 : This =A0 - =A0 # Something which is the value of 'A' and =A0 : Var =A0 - words =A0# Probably 'words' In any case, when you know 'This' and 'Var', you usually have a clue what went wrong. Cheers, - Alex -- UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=3dunsubscribe -- UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
Re: Sum of digits
On Sat, 19 Sep 2009, Jon Kleiser wrote:
Hi,
I wanted to compare how to do sum of digits in Scala and Pico Lisp, and
to my surprise my Pico Lisp version was much slower than my Scala version.
Well, Scala is a compiled language, but I hadn't anticipated that big a
difference. My test input number was a rather big one: (2^100 + 3^200)^300
(#8776;1.885 x 10^28627)
My Scala code was like this:
def sumOfDigits(n: BigInt): BigInt = n.toString.map{ _.asDigit
}.foldLeft(0){ _+_ }
val big = (2:BigInt).pow(100)+(3:BigInt).pow(200)
sumOfDigits(big.pow(300))
- 128458
My Pico Lisp code was like this:
(de sumOfDigits (N)
(apply + (mapcar format (chop (format N )
(setq Big (+ (** 2 100) (** 3 200)))
(sumOfDigits (** Big 300))
- 128458
Could I have written the Pico Lisp code differently to make it faster?
1. avoid being redundant in the code, but it's not something that will make any
difference in speed here:
(de sumOfDigits (N)
(apply + (mapcar format (chop N))) )
# 'chop implicitly uses 'format, so there's no real reason to keep it there.
2. What's taking a long time here is not the 'sumOfDigits, but rather the
bigass number calculation and handling.
The bignum implementation was not intended to be.. *fast*, in the first
place. The implementation works with linked lists instead of arrays.
(setq Big (+ (** 2 100) (** 3 200))
Groso (** Big 300)
Venoso (format Big))
(sumOfDigits Venoso) # This alone should be *really* fast
So, what you'd really wanted to say in the original email is Hey, scala has better bignum
implementation than pL rather than Hey, scala does 'sumOfDigits faster than pL
(which is true, but derived from the first) ;-)
Solutions:
1. Use a C lib (like GMP) to do all the dirty work and then bring back the
result to pL to do the chopping and stuff.
2. To write a better bignum implementation for pL.
3. Cope with it(?)
--
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
Re: Blob problems
I don't understand how a (show This) would show anything else but this
in this case:
[test3.l:23] !? (has (meta This Var) Val (get This Var))
has -- Bad message
? (show This)
{4-5v;} (+Awords)
- {4-5v;}
If you check the earlier code listing you will see that +Awords is
clearly a descendant of +Entity. I mean, this works perfectly for
+Article (as per your instructions earlier), why it doesn't work for
+Awords too is beyond me.
/Henrik
On Sat, Sep 19, 2009 at 5:43 PM, Alexander Burger a...@software-lab.de wrote:
Still it might be helpful to find out why 'has' cannot be invoked:
!? (has (meta This Var) Val (get This Var))
has -- Bad message
What is 'This'? It must be an object of a class (if any?) which is
perhaps not an '+Entity', or where (meta This Var), the inheritance of
the relation class, does not have a method for 'has'. Perhaps this
would be a hint then what's going wrong.
--
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
--
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
