2019年7月3日水曜日

SBCLのvector-push-extendはちょうどmin-extensionだけベクタのサイズを増やす

SBCLのvector-push-extendはちょうどmin-extensionだけベクタのサイズを増やす

Extension is the minimum number of elements to be added to vector if it must be extended. (from http://clhs.lisp.se/Body/f_vec_ps.htm)

CLHSにこう書いてあるし、SBCLの引数名もmin-extensionなので、SBCLは少なくともmin-extensionのぶんだけサイズを増やす(がたいていは効率のために余分に拡張する)のかと思っていたが、実際には正確にmin-extensionの値だけ増やすようだ。したがって、次の処理を(気を利かせて)後者のように書くとむしろ遅くなったりする。

;; 普通の書き方
(vector-push-extend obj1 vector)
(vector-push-extend obj2 vector)
;; 最初に2つ以上確保する
(vector-push-extend obj1 vector 2)
(vector-push obj2 vector)

前者の例:
https://atcoder.jp/contests/agc002/submissions/6218164
後者の例:
https://atcoder.jp/contests/agc002/submissions/6218113

この例のように後者が致命的に遅くなるケースに遭って気づいた。(クエリ毎にsb-vm::extend-vectorするのでオーダーレベルで遅くなっているはず。)

ちなみにmin-extensionnilの場合、拡張が必要になると、(max 1 (length vector))、すなわちだいたい2倍になるように増える。


気づいたときはなぜ?と思ったが、ユーザーが正確に指定できるほうが究極的にはよい仕様と言えるかもしれない。引数の名前は単にextensionにしてほしい気がするけど……