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-extension
がnil
の場合、拡張が必要になると、(max 1 (length vector))
、すなわちだいたい2倍になるように増える。
気づいたときはなぜ?と思ったが、ユーザーが正確に指定できるほうが究極的にはよい仕様と言えるかもしれない。引数の名前は単にextension
にしてほしい気がするけど……