Scalaで特定の長さを越えているか見る

Scala

LinearSeqの長さを制限する

LinearSeqの長さが一定を越えているか見たいとする。

ScalaのLinearSeqはListのような、次の要素へのポインタを持つだけの再帰的かつ単純な実装を前提にしている。

この為、LinearSeqの順番のアクセスは早いが、lengthを取得するのに、全てのリンクを辿る必要があるため、O(n)時間掛かってしまう、という問題がある。

従って、良くあるコードとして

list.length >= n

は時間が掛かり過ぎる。（最適化するかどうかは分からない）

しかし本来この計算は、LinearSeqの長さではなく、比較する数値に比例するところまで落とし込める筈である。

Haskell的アプローチ

そこでHaskell的に（どこをHaskell的と言われると困るが）

list match {
  case _ :: _ :: _ => true
  case _ => false
}

とか考えてみたが、問題が幾らかあって

  • 割と冗長
  • 数字が固定
  • 実は::はListを返す（従ってList以外だとオーバヘッドが考えられる）

今んとこの最適解

という訳でこんなのを考えてみた

list.take(n).length == n

こうすれば数がnで渡せるし、1行だし、take(n)は定数時間だし、例外飛ばないし良さげ

ちなみに

冷静に考えてみると、takeとlengthの無い関数型言語無いと思うので、Scalaに限らず割と汎用的に使えると思う。

補足

コメントにもあるけど、与えられるLinearSeqの長さ（ここではlとする）とnのサイズの平均がn << lになるような場合のみ有用で、しかも頻繁にこのようなことをするのであればIndexedSeqの使用を考えるべき