If you are disappointed with the speed of your code, you should really ask the experts in the Lisp community for some help. There are often trivial ways for speed up and then there are sometimes very complex ways to get better performance.
It is hard to learn this from books. You really need to interact with some people who have experience.
#!/usr/bin/env python
import sys
import math
count = int(sys.stdin.readline())
for i in xrange(0, count):
n = int(sys.stdin.readline())
ndiv5 = math.floor(n / 5.0)
if n >= 25:
ndiv5 += math.floor(n / 25.0)
if n >= 125:
ndiv5 += math.floor(n / 125.0)
if n >= 625:
ndiv5 += math.floor(n / 625.0)
if n >= 3125:
ndiv5 += math.floor(n / 3125.0)
if n >= 15625:
ndiv5 += math.floor(n / 15625.0)
if n >= 78125:
ndiv5 += math.floor(n / 78125.0)
if n >= 390625:
ndiv5 += math.floor(n / 390625.0)
if n >= 1953125:
ndiv5 += math.floor(n / 1953125.0)
if n >= 9765625:
ndiv5 += math.floor(n / 9765625.0)
if n >= 48828125:
ndiv5 += math.floor(n / 48828125.0)
if n >= 244140625:
ndiv5 += math.floor(n / 244140625.0)
print int(ndiv5)
And here is my optimized Common Lisp version: (declaim (optimize (speed 3) (space 3) (safety 0)))
(declaim (inline floor))
(defun calc-trailing-zeros (n)
(declare (type (integer 0 1000000000) n))
(let ((ndiv5 (floor n 5)))
(declare (fixnum ndiv5))
(if (>= n 25)
(setq ndiv5 (+ ndiv5 (floor n 25)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 125)
(setq ndiv5 (+ ndiv5 (floor n 125)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 625)
(setq ndiv5 (+ ndiv5 (floor n 625)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 3125)
(setq ndiv5 (+ ndiv5 (floor n 3125)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 15625)
(setq ndiv5 (+ ndiv5 (floor n 15625)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 78125)
(setq ndiv5 (+ ndiv5 (floor n 78125)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 390625)
(setq ndiv5 (+ ndiv5 (floor n 390625)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 1953125)
(setq ndiv5 (+ ndiv5 (floor n 1953125)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 9765625)
(setq ndiv5 (+ ndiv5 (floor n 9765625)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 48828125)
(setq ndiv5 (+ ndiv5 (floor n 48828125)))
(return-from calc-trailing-zeros ndiv5))
(if (>= n 244140625)
(setq ndiv5 (+ ndiv5 (floor n 244140625)))
(return-from calc-trailing-zeros ndiv5))))
(let ((count (parse-integer (read-line))))
(declare (fixnum count))
(dotimes (n count)
(declare (fixnum n))
(let ((factn (parse-integer (read-line))))
(princ (calc-trailing-zeros factn)) (terpri))))
Notice the Python code doesn't even have the early returns that the Lisp code does. The Python code comes in at 5.42 seconds; the optimized Lisp version's best time was 3.39 seconds. I know the algorithm to solve the problem is probably not the most elegant, but it does get accepted. Any ideas on how to optimize the Lisp code further would be appreciated.1) Read a line from a stream, parse it into an integer. 2) Do a little math. 3) Convert an integer into text and print it to a stream.
In Python, (1) and (3) are implemented in C. For Common Lisp, (1) and (3) are mostly implemented in Lisp.
Beyond that, (1) and (3) will completely dominate the runtime. (2) is probably just a couple of dozen CPU cycles, but the print and terpri will involve flushing stdout, which will involve a system call which will be thousands to tens of thousands of CPU cycles. Depending on how the stream is buffered, the read-line will likely involve a system call as well.
Basically in this test is just measuring how quickly the program can sit and wait for read()/write() system calls to complete. Since they're both calling into the same kernel, it's unsurprising they're the same speed.
One thing I did, though, was to call both functions directly with arguments, and not rely on read-line/readline. That might be the difference, I wouldn't be surprised if Python was optimized for text processing, and SBCL was lazier about it (Lisp programs call read et al. infrequently). Your code is decently optimized, IMO. Cheers.
(defun calc-trailing-zeros-2 (n)
(do ((n (floor n 5) (floor n 5))
(total 0 (+ total n)))
((zerop n) total)))
Methinks this is much better; if there is a performance disadvantage, I wouldn't care about it (and you can add type-decs as you wish; if you do, note that you'd probably have to say (the fixnum (+ a b)) even if a and b are known fixnums). If you want to verify that it works... (dotimes (i 30) (print (= (calc-trailing-zeros i) (calc-trailing-zeros-2 i))))
It prints a bunch of T.As for the performance comparison, I'd echo what others have said: I expect the I/O (read-line, princ, terpri) to dominate the run time. ... Now for some experimentation. "randomthing" is an SBCL image in my executable "mybin" directory that executes the "let ..." code at the bottom; achieved with (save-lisp-and-die "randomthing" :executable t :toplevel (lambda () (let ...))). Let's test it:
;Clipboard is "100000" followed by 100000 instances of "500000"
$ time pbpaste | randomthing > /dev/null
real 0m0.453s
user 0m0.352s
sys 0m0.096s
;Clipboard is "100000" followed by 100000 instances of "000000"
$ time pbpaste | randomthing > /dev/null
real 0m0.352s
user 0m0.263s
sys 0m0.091s
In the case of "000000", the "calc-trailing-zeros" part should take about zero time, and therefore the remaining time is all the I/O stuff. Depending on whether we go by the "real" or "user" thing, this tells us that the math part takes up either 2/7 or 2/9 of the time of the whole program.And just to be sure that "pbpaste" isn't the main cause of slowness:
$ time pbpaste > /dev/null
real 0m0.024s
user 0m0.012s
sys 0m0.009s
Fairly insignificant. Likewise, startup time for this Lisp image can be experimentally determined by having my clipboard only contain "10" followed by 10 integers: $ time pbpaste | randomthing > /dev/null
real 0m0.032s
user 0m0.010s
sys 0m0.027s
So, yeah, I/O dominates the run time, at least on my SBCL (SBCL 1.0.47).
So I went off and just manually translated my code to Python. Exact same algorithm, pretty much word for word translation. Submitted, and made the cut (barely).
This I found dissapointing; how could a byte code interpreted language be faster than a compiled language?
So I picked up 'ANSI Common Lisp' and started optimizing. Found some problems where I was using / instead of when I could just use floor (but then I found a problem where floor always does a cons; why is there no simple floor where I don't get multiple return values). Submitted, finally got accepted (and slightly faster than python). Further optimizations included giving the exact ranges for certain numbers and inlining the floor function.
After an hour or two of optimization work I got it down to about 66% of the python run time. Not even close to what I was expecting in runtime performance, especially considering the 'SBCL is just as fast as C' arguments that are all around.
Not that I'm not going to stop learning CL, but it seems the performance claims just don't add up to the performance reality (for this case). And the development time was doubled just to make the program run acceptably fast.
As Paul Graham said in ANSI Common Lisp: Lisp lets you write slow programs fast, and fast programs slow. But in many cases 'good enough' is just that and I can really see how python excells in this regard and how it's taken over the hearts and minds of a lot of Ex-Lispers.