Scalaで「Listの要素数がnを超えているかどうか」を調べるときはlengthよりlengthIsを使う


> <b>2021-4-12 追記</b>
実際にはコレクションに対しては`length`より`size`を使うことのほうが多いので､タイトルも 「sizeよりsizeIsを使う」 に書き換えたほうがいいかもしれませんが､`length`メソッドの内部実装を取り上げたかったのでこのままにしておきます｡

##はじめに
ScalaのListは、シンプルな単方向リスト(Singly Linked List、片方向リストとも)です。
`head`と`tail`を定数時間で行えることから、不変性とパフォーマンスを両立させるために昔からよく使われてきました(参考: [具象不変コレクションクラス#リスト](https://docs.scala-lang.org/ja/overviews/collections/concrete-immutable-collection-classes.html#リスト))。

そんな便利なListですが、以下のようなケースでは少し困ったことになります。

```scala
  // 1〜100万までの連番のリストを生成
  val xs = List(1 to 1_000_000: _*)

  if (xs.length > 10) {
    println("要素数が10を超えています。")
  }
```

上記のケースの何が問題なのでしょうか？

##Listの要素数の求め方
実は、ScalaのListは自身の要素数を保持していません。
そのため上記のように`length`メソッド(フィールドではなくメソッドです)を使用した場合、ループを通じて自身の要素数を1から数え始めるという挙動になります。[^1]
これは実際にソースコードを見たほうが早いかもしれません。

```List.scala
  override final def length: Int = {
    var these = this
    var len = 0
    while (!these.isEmpty) {
      len += 1
      these = these.tail
    }
    len
  }
```

見ての通り、自身が空になるまでインクリメントと`tail`を続けることで、最終的な要素数を算出しています。

##「10より大きいかどうか」を知りたいだけなのに
以上の前提を踏まえた上で、もう一度最初の例を見てみます。


```scala
  // 1〜100万までの連番のリストを生成
  val xs = List(1 to 1_000_000: _*)

  if (xs.length > 10) {
    println("要素数が10を超えています。")
  }
```

ここで`length`メソッドは、Listの要素数が10を超えているかどうかを調べるためだけに使われています。
確かにこれでも望む答えを得ることはできますが、先程の`length`の定義と照らし合わせると、「要素数が10を超えているかどうか」を調べるために100万回のループが行われることになります。
なおこれは`length`でなく`size`メソッドで要素数を調べた場合も同様です。[^2]

また下記のようなケースも考えられます。

```scala
  if (xs.length <= 10) {
    println("要素数が10以下です。")
  }
```

```scala
  if (xs.length == 10) {
    println("要素数は10です。")
  }
```

上記のケースは全て、最高でも11までカウントすれば事足ります。
要素数が11以上ならその時点で`> 10`はtrueとわかりますし、 `<= 10`や`== 10`はfalseになります。
残りの999,989回分のカウントは明らかに無駄なので、「要素数が11以上」とわかった段階で処理を打ち切りたいところです。
これをしてくれるのが、Scala2.13で追加された`lengthIs`メソッドです。

##lengthIsメソッド
`lengthIs`メソッド[^3] は、下記のように使用します。

```scala:lengthIsで比較したケース
  val xs = List(1 to 1_000_000: _*)

  if (xs.lengthIs > 10) {
    println("要素数が10を超えています。")
  }
```

見た目は`length`を使用した場合とほとんど変わりませんが、内部的には必要に応じて処理を打ち切っているので、より効率的となっています。
`>`に限らず、`>=` `<` `<=` `==` `!=`の全てで使用可能です。
Scala2.13以降で上記のような比較を行いたい場合、積極的に`lengthIs`メソッドを使用していくのがいいでしょう。

なお、`lengthIs`とは別に`sizeIs`というメソッドも用意されていますが、`length`と`size`が同じものであるのと同様に、これらも全く同じ挙動となります。

```scala:
  if (xs.sizeIs > 10) { // lengthIsと全く同じ
    println("要素数が10を超えています。")
  }
```

##おまけ1 - IndexedSeq系列のクラス(とArray)の場合
`lengthIs`メソッドはSeqのメソッドなので、Listや別のLinerSeq系列のクラスに限らず、RangeやVectorのようなIndexedSeq系列のクラスでも、またはArrayでも使用可能です。

```scala:
  val xs = 1 to 1_000_000
  val ys = Vector(xs: _*)
  val zs = Array(xs: _*)

  if (xs.lengthIs > 10 && ys.lengthIs > 10 && zs.lengthIs > 10) {
    ...
  }
```

しかしこれらのクラスはそもそも`length`の演算自体が不要または高速なクラスです。
なのでこれらのクラスに対してListのようにカウントのためのループを一つずつ回してしまうと、(途中までとはいえ)逆に`length`で比較するより遅くなってしまいます。

そのため`lengthIs`メソッドは(内部的に)これらのクラスでは`length`を呼び出しており、ループによるカウントは行いません。[^4]
ループによる性能劣化の懸念がなくなるので、利用者はSeqの種類がLinerSeqなのかIndexedSeqなのかなどを気にせず、比較したいときは気軽に`lengthIs`メソッドを使えるようになっています。

##おまけ2 - Scala2.12以前の場合
`lengthIs`メソッドはScala2.13から追加されたメソッドなので、2.12以前では使えません。
2.12以前で上記のような比較を行いたい場合、`lengthCompare`メソッドを使うことで、`lengthIs`メソッドと同じく無駄のない比較が可能です。

```scala:lengthCompareメソッドの例
  if (xs.lengthCompare(10) > 0) {
    println("要素数が10を超えています。")
  }
```

`lengthCompare`メソッドはよくある`compare`メソッドと同様に、`-1`,`0`,`1`のいずれかを返すことで大小を表します。[^5]
2.13以降であれば`lengthIs`メソッドの方が直感的ですし、積極的に使う理由はないと思われますが、2.12以前を扱う際は覚えておいて損はないと思います。

<br>
最後までお読み頂きありがとうございました｡
質問や不備についてはコメント欄か[Twitter](https://twitter.com/ka2_kamaboko)までお願いします。

[^1]: Listに限らず、LinearSeq系列のクラス(List, LazyList, Queueなど)の基本的な挙動です。
[^2]: `size`メソッドは`length`メソッドのエイリアスです。
[^3]: `lengthls`ではなく`lengthIs`(length is)です(~~最初間違えて覚えた~~)。
[^4]: `knownSize`というメソッドを使って判断しています。
[^5]: `lengthIs`メソッドも内部的には同じことをしてます。