4 ms·

I've been taking some time to learn CL lately, and one of the things I've been doing is SPOJ (http://www.spoj.pl http://www.spoj.pl) problems. One one paticula

by kruhft 16y ago

I've been taking some time to learn CL lately, and one of the things I've been doing is SPOJ (http://www.spoj.pl http://www.spoj.pl) problems. One one paticular problem (FCTRL) I attempted to solve it in CL and came up with code that I was pretty sure would work. After submitting a number of times using the SBCL compiler, I could not solve the problem in the time allocated. 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.

lispm 16y ago
Common Lisp is not simply fast. Common Lisp enables you to write a lot of code in Lisp that is fast. If you write Python and just call the in C written functionality of the implementation it can be easily as fast. With Common Lisp it is possible to stay a long time in Lisp, without the need to use C to improve the speed. Plus you can write code with optimizations that can then get rid of much of the overhead (type checking, bounds checking, ...). But that should only be done locally. Generally the performance model of Common Lisp is not that simple. It takes some practice and some understanding of the compiler and underlying runtime to get code 'really' fast. 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.
mahmud 16y ago
Code please.
- kruhft 16y ago
  I'll try and post the Python and CL code tonite.
- kruhft 16y ago
  Here is python code that I first used to solved to problem in the time allowed: #!/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.

by kruhft 16y ago

lispm 16y ago

Common Lisp is not simply fast. Common Lisp enables you to write a lot of code in Lisp that is fast. If you write Python and just call the in C written functionality of the implementation it can be easily as fast. With Common Lisp it is possible to stay a long time in Lisp, without the need to use C to improve the speed. Plus you can write code with optimizations that can then get rid of much of the overhead (type checking, bounds checking, ...). But that should only be done locally. Generally the performance model of Common Lisp is not that simple. It takes some practice and some understanding of the compiler and underlying runtime to get code 'really' fast. 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.

mahmud 16y ago

Code please.

kruhft 16y ago
I'll try and post the Python and CL code tonite.
kruhft 16y ago
Here is python code that I first used to solved to problem in the time allowed: #!/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.