mojavy.com

Common Lisp練習 - CodeChef : TSORT

October 24, 2012 at 06:00 PM | categories: programming, common lisp |

codechef

Common Lispの練習にCodeChefの↓の練習問題をやってみた。

http://www.codechef.com/problems/TSORT

問題自体は全然難しくないけど、Common Lispで解こうとしたらTime Limit Exceededでおちてしまった。

最初は以下のように書いて、

(let ((_n (parse-integer (read-line)))
      (lis ()))
  (dotimes (i _n)
    (push (parse-integer (read-line)) lis))
  (setf lis (sort lis #'(lambda (x y) (< x y))))
  (dolist (x lis) (format t "~a~%" x)))

以下の用にして時間を測ったところ

$ time ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}' | sbcl --script turbosort.cl > /dev/null
ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}'  1.19s user 0.01s system 91% cpu 1.311 total
sbcl --script turbosort.cl > /dev/null  3.42s user 0.43s system 97% cpu 3.938 total

ローカルだと3.42s程度だった。codechef上での制限は5secなのでセーフかと思ったけどTime Limit Exceededだった。

そこで、vectorを使うように改良

(let* ((_n (parse-integer (read-line)))
       (lis (make-array _n :fill-pointer 0)))
  (dotimes (i _n)
    (vector-push (parse-integer (read-line)) lis))
  (setf lis (sort lis #'(lambda (x y) (< x y))))
  (loop for i across lis do (format t "~a~%" i)))

$ time ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}' | sbcl --script turbosort.cl > /dev/null
ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}'  1.21s user 0.01s system 94% cpu 1.289 total
sbcl --script turbosort.cl > /dev/null  2.64s user 0.44s system 98% cpu 3.137 total

若干改善されたが、まだTime Limit Exceededだった。

read-sequenceで読み込んだほうが早いかと思って以下のように書いてみた。

(defun parse-input (str)
  (loop
     for i = 0 then (+ 1 j)
     as j = (position #\Newline str :start i)
     as k = (parse-integer (subseq str i j) :junk-allowed t)
     if (not (null k))
     collect k
     while j))

(let* ((_n (parse-integer (read-line)))
       (lis (make-array (* _n 20) :element-type 'character))
       (nums ())
       )
  (read-sequence lis *standard-input*)
  (setf nums (sort (parse-input lis) #'(lambda (x y) (< x y))))
  (loop for i in nums do (format t "~a~%" i)))

$ time ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}' | sbcl --script turbosort.cl > /dev/null
ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}'  1.13s user 0.01s system 97% cpu 1.159 total
sbcl --script turbosort.cl > /dev/null  3.67s user 0.48s system 96% cpu 4.297 total

残念ながら逆に遅くなってしまった。parse-inputの部分で60%くらい時間がかかっていた。 あと、#'(lambda (x y) (< x y))の部分を #'<にするとなぜか遅くなる。

まだ誰もlispではパスしてない模様。こういうのをもっと高速に書く方法あるのだろうか。

ちなみにCだと余裕。ローカルだと0.2秒くらいだけどリモートでは3秒くらいかかってた。そもそもCodeChefの実行環境がしょぼすぎる疑惑が。。

#include <stdio.h>
#include <stdlib.h>

int f(const void *i, const void *j) {
    return *((int*)i) > *((int*)j);
}

int main(void) {
    char buf[256];
    int num = atoi(fgets(buf, 256, stdin));

    int lis[num];
    for (int i = 0; i < num; ++i) {
        lis[i] = atoi(fgets(buf, 256, stdin));
    }
    qsort(lis, num, sizeof(int), f);
    for (int i = 0; i < num; ++i) {
        printf("%d\n", lis[i]);
    }

$ time ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}' | ./a.out > /dev/null
ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}'  0.99s user 0.01s system 99% cpu 1.006 total
./a.out > /dev/null  0.18s user 0.01s system 17% cpu 1.116 total
blog comments powered by Disqus

About Me

pic
mojavy

Recent posts



Categories

Badges