SBCLのremove-duplicatesについて。
remove-duplicatesは常に${O}(N^2)$と思っていたのだけど、${O}(N)$の場合もあることを知った。[1] 具体的には、
- 入力がリストで
keyとtest-notが与えられていなくてtestがeq・eql・equal・equalpのどれか
である場合にハッシュテーブルが使われて${O}(N)$になる。
自分が必ず${O}(N^2)$になると思いこんでいたのはCLHSの次の記述
The elements of sequence are compared pairwise, and if any two match, then the one occurring earlier in sequence is discarded, unless from-end is true, in which case the one later in sequence is discarded. (http://clhs.lisp.se/Body/f_rm_dup.htm)
が理由で、pairwiseに比較すると決まっていればそれを利用した副作用をtest関数に含めてもよいことになるので、比較自体をやめてしまうのは標準に反するように見えたからだった。
でも、よく考えてみるとtestがeqlの場合は副作用がないので、pairwiseの比較をさぼっても挙動を区別できない。[2] keyがある場合にハッシュテーブルを使わないのは、keyが副作用を持つケースがあるからだろう。しかし、入力がリストの場合に限定している理由はわからない。
delete-duplicatesにはこの最適化がなぜかない（のでこちらのほうが遅くなったりする）のだが、in-place性を重視する意図があるかもしれない。
この実装になったのはわりとずっと昔のことらしい。
redditも参照。副作用云々は別に関係ない気がしてきた。
AtCoderで ar44denchiさんの提出を見て気づいた。 ↩︎
ユーザー定義のテスト関数でも、
sb-impl::*user-hash-table-tests*に登録済みでsb-c::flushableとかの宣言があれば最適化してもよいことになる？ ↩︎
