2020年2月9日日曜日

remove-duplicatesの計算量

SBCLのremove-duplicatesについて。

remove-duplicatesは常にO(N2){O}(N^2)と思っていたのだけど、O(N){O}(N)の場合もあることを知った。[1] 具体的には、

  1. 入力がリストで
  2. keyとtest-notが与えられていなくて
  3. testがeq・eql・equal・equalpのどれか

である場合にハッシュテーブルが使われてO(N){O}(N)になる。

自分が必ずO(N2){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も参照。副作用云々は別に関係ない気がしてきた。

  1. AtCoderで ar44denchiさんの提出を見て気づいた。 ↩︎

  2. ユーザー定義のテスト関数でも、sb-impl::*user-hash-table-tests*に登録済みでsb-c::flushableとかの宣言があれば最適化してもよいことになる？ ↩︎

投稿者