Lambdaカクテル

Common Lispを書くMT-03ライダー(初心者)です

AtCoder Beginner Contest 128にCommon Lispで参加した

競技プログラミングに初参加しました.実装言語はもちろんCommon Lispです.

残念なことにコンテスト開始からしばらくたってから気付いたので,B問までしか完成させられなかった.C問で頭をひねっていたら終了.

成績はこちら.

atcoder.jp

Common Lispはそれほど実行速度が速いわけではなく(AtCoderの実行環境がどうなっているのか知らないが,なんとPerlよりもPythonよりも遅い),平均100msもかかってしまうことが多い. おそらく処理系のブートストラップかコンパイルに時間を取られているのだと思う.Cやgoは実行前にコンパイルしているのか,かなり高速に動作する. おそらく直接ソースコードを処理系に渡していて,その時間も込みで計上されているのかもしれない.できればプリコンパイルして測定するようにしてほしい.

というわけで「Common Lispは遅いクソ言語」と言われたら悲しいのでいろいろチューニングしようとしてみたけれど,なんとチューン前の方がメモリ消費も実行時間もマシという悲しい結果に. ヤンナルネ・・・

チューン前のB解答

(defun f (s)
  (let* ((n (read s))
         (ps (loop for i from 1 to n
                   for city = (read s)
                   for point = (read s)
                   collecting (list i city point)))
         (sorted1 (sort ps #'(lambda (p pp) (> (third p) (third pp)))))
         (sorted2 (sort sorted1 #'(lambda (p pp) (string< (second p) (second pp))))))
    (loop for p in sorted2
          do (format t "~A~%" (first p)))))
(f t)

そしてチューン後

(defstruct p (i 0 :type integer) (city nil :type symbol) (point 0 :type integer))
(defparameter *initial* (make-p))
(defun f ()
  (declare (optimize (speed 3) (safety 0)))
  (let* ((n (read))
         (arr (make-array `(,n) :element-type 'p :initial-element *initial* :adjustable nil))
         (_ (loop #:for i #:from 1 to n
                  #:for city symbol = (read)
                  #:for point integer = (read)
                  #:do (setf (svref arr (1- i))
                             (make-p :i i :city city :point point))))
         (sorted1 (sort arr #'> :key #'p-point))
         (sorted2 (stable-sort sorted1 #'string< :key #'p-city)))
    (loop #:for p #:across sorted2
          #:do (progn (princ (p-i p)) (terpri)))))

defstructが邪魔だったのだろうか.なにもわからない

追記(2019-05-27T01:24+09:00)

atcoder.jp

ルールを見たところ,コンパイルに

sbcl --eval '(write-line "Hello, world!")' --non-interactive > /dev/null

実行に

sbcl --script Main.lisp

が使われるようだ.コンパイルフェーズでコンパイルしてないじゃん.そら遅いわ.他の言語ではちゃんとコンパイルしてるのになんでCommon Lispだけこんな扱いなんだ・・・(何も知らない人向け豆知識: Common Lispの大抵の処理系,もちろんAtCoderで使われるSBCLは事前にコンパイルできます!)