Help us understand the problem. What is going on with this article?

競技プログラミングでCommon Lispを使っている人とこれから使うかもしれない人のために

表題の通り、競技プログラミングに参加しているLisperとこれから参加するかもしれないLisperのために、必要な情報を一通りまとめています。

コンテストサイトの選択

AtCoderではCommon Lispが使えますし、CLで投稿できる大手コンテストサイトはCodeChefyukicoderCS Academyなど他にもいくつかあります。日本語の問題文があって運営の質が高くてコンテストが頻繁に開催されていて……というような点を考えていくと、競プロに興味を持った日本語圏のLisperにとってAtCoderは第一の選択肢といってよいでしょう。第二はyukicoderとCodeChefです。以下の解説は、特に断りがなければAtCoderを前提にしています。

Lispで競プロすることについて

本題ではありませんが、セクションを立てて言及しておくことにします。というのも、競技プログラミングに熱心なLisperはほぼ皆無に見えるからです。C++の使用率がどのサイトでも圧倒的なのは事実なので、競プロに興味のある人の中にも、そもそもLispに向いているジャンルなのかどうか不透明に思う人がいるかもしれません。

端的に言うと、わたしのレベルではパフォーマンスの面でデメリットを感じたことはありません。より高レートの状況でどうなるかは知りえないことですが、悲観する材料は特に見つかっていません。終わり。

……でもよいのですが、いくつかのポイントに絞って説明してみます。

○: 柔軟な構文

素早く・簡潔に・柔軟にDSLを生やすことにかけてはLispは今なお優れた言語であると言えるでしょう。競プロの文脈でもそれはちゃんと役に立ちます。もっとも、そういったものは競プロにおけるパフォーマンスにさほど影響しないとも思います。競プロで大事なのは考察力です。

○: スピード

最良ではないが、悪くもないです。AtCoderにおける速さという観点で言語を雑に分類すると

  • A群: C/C++/Rustなどの、システムプログラミングのための言語
  • B群: Ocaml/Haskellなど、ネイティブコードへの事前コンパイルを前提とするその他の言語。Java/C#などの高速VMを持つ言語。
  • C群: Python/Ruby/PHPなどのスクリプト言語

で性能はおおむねA>B>Cということになりますが、LispはBの中で速いほう、くらいの位置づけです。状況にもよるので絶対的な比較は難しいですが、「Java/C#よりやや有利」くらいの認識を持っています。そして、Java/C#専のまま強くなる人は特に珍しくもありませんから、スピードの問題はさほど心配しなくてよいです。

実情を言うと、500点くらいまでの問題では正しいロジック(=最悪計算量が制約に適っているロジック)で書けていればTLE(Time Limit Exceeded)することはめったにありません。TLEするのは、最適化が足りないからではなく、計算量の考察がおかしいからと思ってほぼ間違いないです。ほとんどの場合、最適化のための基本的な宣言すら必要ないと思います。それ以上のレベルの問題でも、SBCLが遅くて通せないとか、あるいは最適化しても制限時間ぎりぎりになるという事態に陥ったことは一度もありません。そもそもAtCoderではJavaで通らない問題は出題されないそうなので、SBCLで通せないというケースは考えにくいです。

ただ、AtCoderのシステム上の問題として、Lispは(C++等と違って)コンパイルの時間を取らずにsbcl --scriptで実行されるので、その時間の分だけやや損をしているという点があります。このロスですが、普通は150ms以内におさまるし、必要な長さのコードを提出する限り300msを超えることは稀なので、深刻な問題にはなっていません。1 もちろん、コンパイルのフェーズを用意してくれるに越したことはないですし、次回の言語更新ではそのようになるでしょう。

△: 標準機能・ライブラリの充実度

Common Lispの標準ライブラリは貧弱です。平衡二分木もなければ、優先度付きキューも両端キューもないし、それどころかただのキューすらないので、あらゆるデータ構造をいちいち用意しなければなりません。2 良い所もそれなりにはあって、多倍長整数が自然に扱えるのでオーバーフローの処理をちょっとくらいサボってもOKなのは悪くない点ですし、有理数や複素数も競プロでは活躍します。stringが文字の配列であるという時代遅れな仕様も、競プロではむしろ望ましいです。しかし、総合的に見てやや不十分なのは否めないでしょう。

もっとも、競プロerはどの言語を使っていてもけっきょくは自前実装のデータ構造を少しは用意することになるので、二分ヒープを自分で書くことくらいは誤差レベルとも言えます。ただ、自分でデータ構造を書く場合に、効率のために要素型で静的ディスパッチするようなコードを書くのが大変という別の問題はあります。CLにはパラメータ多相を自然に導入する方法の決定版がいまだにないので…… (競プロに限った話ではありませんが、ジェネリクスのデファクトがないのはCLのアキレス腱だと思っています。)

△: コンテストサイト・オンラインジャッジの選択肢

Common Lispは最大手のCodeforcesで使えませんし、もちろんTopCoderでも使えません。日本の競プロer御用達のAOJも対応していません。したがって、LisperはAtCoderyukicoderCodeChefを中心に利用し、Google Code Jamがあれば出て、足りなければCS AcademyHackerRankなどを使うことになります。それが不満ならC++やJavaを選んだほうがよいでしょう。ちなみにわたしはまあまあ不満です。

✕: 言語コミュニティの規模

Lisperの数が極めて少ないため、参考にできるコードがありません。AtCoderで400点以上の問題だとLispの提出はゼロであることが多いです。困ります。もちろん、根幹のロジックを理解するために読むのはなんの言語でもよいので、C++やPythonの提出コードを見ればよいです。しかし、他人のコードを読むのは、より洗練された間違えにくい書き方を学ぶためという側面が強いので、言語が同じであるほうがはるかに参考にしやすいのも確かです。

もっとも、この問題はあなたが参加すれば解消されるとも言えます。ぜひやってみませんか。

いくつかの問題と解決策

実践で生じるトラブルとその回避方法を挙げます。「いくつか」と題しましたが、今のところ重要なものは最初の1つだけです。また、入出力関係の話題はまとめて後のセクションで扱います。

スタックサイズが足りない(重要度:◎)

SBCLのデフォルトのスタックサイズは2MBであり3、このサイズを超えて関数呼び出しするとエラーになります。(末尾呼び出しになっていればジャンプに変わるので安全です。)

2MBというサイズですが、目安としては105の深さで再帰すると確実にcontrol-stack-exhaustedする、104ならたぶんOK、くらいです。オーダー的に無理そうなら再帰を使わなければ良いのですが、DFSなどを手動スタック+ループで書くのは馬鹿馬鹿しいと思うLisperも多いでしょうし、そもそもツリーの走査や分割統治的な処理は再帰で書いたほうが間違えにくいのも確かです。幸運なことに、この問題については解決策が確立しています。スタックサイズを増やしたSBCLを子プロセスとして呼び出せばよいのです。ファイルの冒頭に次のフォームを置きましょう。

#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))

こうすればスタックサイズの大きいSBCLが代わりに処理してくれます。

  • 終了コード絡みの処理は、子プロセスでエラーが起こった時に親プロセスのエラーにするためにやっています。そうしないと子プロセスでエラーが起こってもREと表示されなかったりします。
  • #-swankは必須ではありませんが、わたしはSLIMEでコーディングしているので、編集中にこのフォームが評価されないようにするために書いています。
  • 直接--scriptで実行する仕様でも、コンパイルしてから実行する仕様でも、どちらでも通るようにしています。yukicoder、CodeChef、CS Academy、HackerRank、GCJでも使えることを確認しています。
  • 今のところ128MBで足りなかったことはありませんが、64MBで足りなかったことはあります。スタックサイズが足りないとき、必ずしもREと表示されるわけではなく、TLEになることもあるので気をつけましょう。

やや強引なハックではありますが、この方法の欠陥は発見されていません。10ms程度ロスしてわずかにメモリ消費が増えるだけですし、なんなら、常にこのフォームをくっつけて投稿しても問題ない可能性があります。(わたしは今のところ、スタックサイズが不安な時にしか使っていません。)

最初のテストケースに時間がかかっている(重要度:○)

atcoder.jpg

20ms程度で済むはずの処理が、最初のテストケースだけ200ms以上掛かっていることがよくあります。原因は知りませんが、AWSの問題らしく、Lisp以外でも生じるようです。TLEした場合には繰り返し実行して検証するという対応を取っているとのことで、これが原因でACできなかったと思われるパターンはわたしは経験したことがないです。したがって、解決策は「無視する」です。問題で与えられた時間制限よりずっと短い実行時間を比較するような目的にはAtCoderの環境は向いていません。(そもそもそういう競技ではないので。)

ベクタのソートが遅い(重要度:△)

(declare (inline sort))しましょう。SBCLのsortsb-ext:maybe-inlineなので、デフォルトではインライン化されません。4 インライン化されないと、ベクタの要素型を考慮した静的ディスパッチがされないので、常識的なスピードが出ません。

ただ、SBCLのソートはベクタに対してはヒープソートなので、いずれにせよスピード重視ではないし、標準のソートは範囲指定ができないという問題もあります。5 マージソートなりクイックソートなりを用意しておくのもよいかもしれません。

リストをsortする場合(マージソート)に関してはさらに(declare (inline sb-impl::stable-sort-list))が必要だったりします。(ソートが間に合うか不安なくらいに入力が大きいケースではリストで持たないほうがよいと思いますが。)

また、普段からSBCLのどの関数がどの場合にインライン化(インライン宣言やdefine-source-transformdeftransformdefine-vopによる変換)されるのか、型を考慮した最適化があるのかを気にしておきましょう。SLIME上なら、標準の関数に対してM-. slime-edit-definitionするとSBCLのソースにジャンプできます。

末尾の改行の扱いが一貫していない(重要度:△)

  1. テストケースの入力の末尾に改行があるとは限りません。常に#\Newlineがあるという仮定で処理をすると原因不明のREに苦しむことになります。

  2. 同様に、出力の末尾に改行がなくても通るかどうかは不定です。必ず改行を送っておきましょう。

ただ、これらは昔の問題に限った注意点だと思います。最近のジャッジは出力を柔軟に受けつけてくれる印象があります。

入出力の改行コードは#\Linefeed決め打ちで問題なかったはずです。ウェブ上のサンプルケースにはCR+LFのものもありますが、合わせる必要はありません。

コンパイルメッセージが見たい(重要度:△)

AtCoderのSBCLのバージョンは1.1.14です。ローカルのバージョンもそれに合わせたい場合は、roswellを使うなりする手があると思いますが、コンパイラの出力を確認したいだけなら、コードテストで次のヘッダをつけて送ると良いでしょう:

#-swank
(quit
 :unix-status
 (process-exit-code
  (run-program *runtime-pathname*
               (list "--noinform"
                     "--eval" (format nil "(compile-file \"~A\")" *load-pathname*)
                     "--quit")
               :output t :error t :input t)))

CS Academy: 実行時エラーが起きてもWrong Answerと表示される

注意: 2019年8月頃に仕様が変わったらしく、下の記述はたぶん今の事情とは異なる。

CS Academyの環境でCommon Lispを使うと、実行時エラーが起きてもResultにWrong Answerと表示されるので、エラーなのか答えが間違っているかの区別がつきません。おそらく、SBCLを--scriptで実行しておらず、デバッガが起動したときのエラー出力を回答とみなしているのだと思います。対策は簡単で、提出コードの始めのほうに

(sb-ext:disable-debugger)

という一行を入れておけば、エラーが起きたときにNon zero exit code = 1と表示されるようになります。ローカルで編集しているときにdisable-debuggerするのが不都合であれば、例えばSLIMEなら#-swank (disable-debugger)などとするとよいでしょう。

入出力のTips

大量の入出力をこなす場合(目安としては105行くらいから)、全部(read)して一行ずつ書き出すような素朴すぎる方法を使うと無視できないロスになることがあります。このセクションでは効率をある程度考慮した方法を紹介します。しかし、ベストプラクティスと言えるような方法は特に確立していないので、以下のポイントを頭に入れつつ各自で好きなようにしましょう。

read-lineを高速化する(使用頻度: △)

read-lineは遅いとよく言われます。遅い理由として、read-lineは呼び出すたびにコンシングするからという説明を見たことがありますが、わたしの知る限りでは、律速しているのはマルチバイト文字を考慮したread-charです。AtCoderでは(おそらく)ASCIIしか出ないので、バイト単位で読んでsimple-base-stringのバッファに読みだす関数を作ってしまいましょう。SBCLの標準IOはbivalentなので、read-byteが使えます:

(declaim (inline read-line-into))
(defun read-line-into (buffer-string &key (in *standard-input*) (term-char #\Space))
  (declare (inline read-byte))
  (loop for c of-type base-char =
           #-swank (code-char (read-byte in nil #.(char-code #\Newline)))
           #+swank (read-char in nil #\Newline)
        for idx from 0
        until (char= c #\Newline)
        do (setf (char buffer-string idx) c)
        finally (when (< idx (length buffer-string))
                  (setf (char buffer-string idx) term-char))
                (return (values buffer-string idx))))

  • term-charは入力終了を表す文字として使います。例えば#\Spaceの場合、1 2 3という行を読むとbuffer-string"1 2 3 "で上書きするわけです。buffer-stringの長さがちょうど5なら"1 2 3"になります。
  • SWANKの標準IOはbivalentでないため、SLIME上で編集している時は代わりにread-charを使う必要があります。
  • 読み込みの終了位置を多値で返しています。
  • (declare (sb-kernel:ansi-stream in))を宣言するとさらに速くなります。

上の関数はread-lineよりずっと速いですが、いちいちバッファを作るのも面倒です。サイズだけ指定してバッファは自動で用意するという手もあるでしょう:

(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (term-char #\Space))
  (let ((buffer (gensym))
        (character (gensym))
        (idx (gensym)))
    `(let* ((,buffer (load-time-value (make-string ,buffer-size :element-type 'base-char))))
       (declare (simple-base-string ,buffer)
                (inline read-byte))
       (loop for ,character of-type base-char =
                ,(if (member :swank *features*)
                     `(read-char ,in nil #\Newline) ; on SLIME
                     `(code-char (read-byte ,in nil #.(char-code #\Newline))))
             for ,idx from 0
             until (char= ,character #\Newline)
             do (setf (schar ,buffer ,idx) ,character)
             finally (when (< ,idx ,buffer-size)
                       (setf (schar ,buffer ,idx) ,term-char))
                     (return (values ,buffer ,idx))))))
  • バッファサイズはコンパイル時に与えるべきなので、マクロにしました。

read-lineとの比較ですが、105行以上のデータを読み込むなら200msくらいは得できるイメージです。最大で800msほど速くなるパターンを経験しています。

ただ、リードにしろパースにしろ、行単位で1文字ずつ読むのを止めてread-sequenceを使ったほうが速くなりそうですし、それでなくともどうせ1文字ずつ読むならストリームから直接処理したほうがいくらか良くなります。以下にそのやり方も紹介しますが、read-lineや上の関数が役に立つこともよくあります。ストリングを介した行単位の処理は柔軟で、変則的な入力にも対応しやすいためです。

整数を高速に読み込む(使用頻度: ◎)

大量の整数を読み込んで処理する問題は頻繁に出ます。整数が$10^5$個を超えたあたりからreadでは苦しくなってきます。

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare (inline read-byte)
           #-swank (sb-kernel:ansi-stream in))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (read-byte in nil 0))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (the (integer 0 #.(floor most-positive-fixnum 10)) (* result 10))))
              (return (if minus (- result) result))))))))

(defun read-bignum (&optional (in *standard-input*))
  (declare (inline read-byte)
           #-swank (sb-kernel:ansi-stream in))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (read-byte in nil 0))))
    (let* ((minusp nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minusp t))
                                 ((= byte #.(char-code #\+))
                                  (setf minusp nil))))))
           (mid-result 0)
           (index-mod18 0))
      (declare (fixnum mid-result)
               ((integer 0 19) index-mod18)
               (integer result))
      (loop
        (when (= index-mod18 18)
          (setq result (+ mid-result (* result #.(expt 10 18))))
          (setq mid-result 0)
          (setq index-mod18 0))
        (let ((byte (%read-byte)))
          (unless (<= 48 byte 57) (return))
          (setq mid-result (+ (- byte 48) (* 10 (the (mod #.(expt 10 17)) mid-result))))
          (incf index-mod18)))
      (setq result (+ mid-result (* result (expt 10 index-mod18))))
      (if minusp (- result) result))))
  • 上と同様の理由で、SLIME上とそれ以外で入力方法を変えています。

read-fixnumは、読み込む整数がfixnum(=(signed-byte 63))とわかっている場合のreadの代替であり、わたし自身、ここに挙げた関数の中でもっとも頻繁に使っています。

read-bignumも用意してありますが、ほとんど使ったことがありません。AtCoderでは多倍長整数をそのまま扱えないと厳しい問題はそうそう出ないと思いますし、出ても1つ読むだけならreadが十分速いです。6 どのくらい大きな整数を扱えるかは感覚で覚えるしかありませんが、目安としては10100000を読むのに200ms掛かると覚えておくとよいです。

出力をstring-output-streamにためる(使用頻度: ○)

出力データが大量にある場合、一行ずつ*standard-output*に出していくとロスが大きくなることがあります。そういう時はstring-output-streamを使いましょう:

(let ((out (make-string-output-stream :element-type 'base-char)))
  (dotimes (i n)
    (princ data out)
    (terpri out))
  (write-string (get-output-stream-string out)))

これは場合によってはかなり効きます(400ms以上の得になったりする)。マクロ化すると次のような感じでしょうか。

(defmacro with-buffered-stdout (&body body)
  (let ((out (gensym)))
    `(let ((,out (make-string-output-stream :element-type 'base-char)))
       (let ((*standard-output* ,out))
         ,@body)
       (write-string (get-output-stream-string ,out)))))

ただし、大昔の問題はメモリ制限が64MBなので、string-output-streamに全部ためるとMLE(Memory Limit Exceeded)になってしまうことがあります。最近の問題は256MBまたは1GBなので、この点を気にする必要はありません。

小数を出力する(使用頻度: △)

SBCLのformat~F~$は遅いです。特に、~,5F~5$のように小数点以下の桁数を指定した場合、出力だけで時間切れするレベルのボトルネックになったりします。

単純な解決策としてはwriteprincをそのまま使うことが挙げられます。この場合、出力に指数表記が混じることになりますが、AtCoderは基本的には指数表記で回答しても問題なかったはずです。(初期の問題に通らないものがあった気もします。) ただし、指数の記号はもちろんeでないといけません。実数を扱う問題では、精度を考慮するとdouble-floatが必要になることも多いのですが、その場合は*read-default-float-format*を変更する必要があります:

CL-USER> (write 1.4f10)
1.4e10
CL-USER> (write 1.4d10)
1.4d10
CL-USER> (let ((*read-default-float-format* 'double-float))
           (write 1.4d10))
1.4e10

なお、わたし自身はdouble-float通常の表記で出力する関数も用意してはいます(がほとんど試していないので注意)。

小数を高速に読み込む(使用頻度:✕)

小数を大量に入力する問題は意外にもほとんど出ないですね。SBCLのリーダーをいじったものをいちおう用意していますが、やはりほとんど試していません。

その他の情報へのリンク

先に述べたように、Lisperの競プロerは皆無に近く、Lispに関係する情報は(英語でも)ほとんど目にしたことがありません。

https://competitive12.blogspot.com/
わたしの競プロ関連の記事はここに載せています。Lispに絡んだ話題もたまに扱っています。

https://github.com/privet-kitty/cl-competitive
CLの競プロ用ライブラリです。だいたいの競プロerは、典型的なデータ構造・アルゴリズムはある程度用意しておきつつ、コンテスト中に「あれがない」となったらググってコピペしたりその場で実装したりします。CLの競プロ向けコード集は他に見たことがありませんが、上のリポジトリには頻出のものが(頻出でないものも)だいたい揃っています。大部分のコードはパブリックドメインにしているので、必要ならコピペしましょう。CIも導入していますが、テストされているコードは一部なのであまり信用しないでください。当然ですが、製品のためのコードではありません。

結び

最後に、いろいろ述べましたが、特にAtCoderでは事前準備(ライブラリの整備)はさほど重要なポイントではないので、気おくれすることはありません。入出力絡みはそれなりに注意を払う必要があるので上で紹介しましたが、そこをクリアすればあとは考察力がすべてです。

ということです。競プロ、楽しいですよ。


  1. コンパイルを重くしすぎると1秒近く使ってしまうケースはありえて、ここまで失うとさすがにTLEのリスクがあります。ただ、わたしの経験の範囲では、コンテスト中にこれで失敗したことは一度もないくらいにレアな事象です。 

  2. ただし、SBCLではただのキューで良ければsb-queueが十分使えます。また、src/code/target-bst.lisp(バージョン1.5.0より前)かsrc/code/avltree.lisp(1.5.0以降)に平衡二分木が一応あったり、src/code/timer.lispに二分ヒープがあったりしますが、これらはユーザーが使うことを意図したものではないでしょうし、汎用的に作られてはいません。 

  3. AtCoder上のSBCLについては、コードテストで(print (sb-alien:extern-alien "thread_control_stack_size" sb-kernel::os-vm-size-t))を送れば確認できます。 

  4. 標準の関数のうち、SBCLでmaybe-inlineなのはacons, both-case-p, digit-char-p, float-precision, get-properties, getf, intersection, keywordp, lower-case-p, nintersection, nset-difference, nset-exclusive-or, nsublis, nsubst, nsubst-if, nsubst-if-not, nthcdr, nunion, remprop, set-difference, set-exclusive-or, sort, stable-sort, sublis, subsetp, subst, subst-if, subst-if-not, tailp, tree-equal, union, upper-case-pです。ソート以外で覚えておきたいのはdigit-char-pでしょうか。また、maybe-inlineとだいたい同じですが、inline宣言されたあとnotinline宣言されている関数としてunread-char, listen, read-char, read-byteがあり、これらも明示すればインライン化されます。 

  5. 一応、displaceしたベクタをソートして副作用を利用するという方法はあります。おそらく未定義動作ですし、simpleでなくなるので遅いですが、SBCLでは意図通りに動くはずです。 

  6. いっぽう、SBCLのparse-integerは多倍長整数をパースするのが遅いので注意。10100000を読むのに2秒以上かかります。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away