FunctionalScalaのループ

投稿日: 2022-10-15 2022-10-15
タグ: Functional Programming

1. 概要

このチュートリアルでは、JVMのループと再帰について見ていきます。また、回避するための一般的な落とし穴と、コードを簡潔にし、エラーが発生しないようにするための最適化手法についても説明します。

2. スタックとスタックフレーム

Scalaの機能ループを理解するには、スタックとは何かを理解することが重要です。

2.1. スタック

スタックは、コールスタックとも呼ばれ、 official docs によって、ローカル変数と部分的な結果を保持し、メソッドの戻りと呼び出しを部分的に制御するデータ構造として定義されています。

単一のJVMスレッドには、スレッドと同時に作成されたプライベートJVMスタックがあり、スタックフレームを格納します。 JVMは、Javaスタック上で直接2つの主要な操作を実行します。スタックフレームをプッシュおよびポップします。

このドキュメントに示されているように、デフォルトのスタックサイズはコンピュータアーキテクチャによって異なります。スタックサイズを増やすことはできますが、スタックサイズを不必要に増やすのではなく、安全で効率的な方法でコードを設計することをお勧めします。

スタックには、スレッドが現在の実行ポイントに到達するために呼び出したメソッドに関する情報が含まれています。スレッドがコードを実行すると、呼び出しスタックが変化します。

スタックには、実行されている各メソッド（呼び出しスタック上のすべてのメソッド）のすべてのローカル変数も含まれます。スレッドは、それ自体のスレッドスタックにのみアクセスできます。

スレッドによって作成されたローカル変数は、それを作成したスレッド以外のスレッドには表示されません。 2つのスレッドがまったく同じコードを実行している場合でも、両方のスレッドは、それぞれのスレッドスタックにそのコードのローカル変数を作成します。したがって、各スレッドには、各ローカル変数の独自のバージョンがあります。

2.2. スタックフレーム

スタックフレーム（または複数のフレーム）は、Javaスタックを構成します。スタックフレームには、単一のJavaメソッド呼び出しの状態が含まれています。スレッドがメソッドまたは関数を呼び出すと、Java仮想マシンは新しいフレームをそのスレッドのJavaスタックにプッシュします。メソッドが完了すると、JVMはそのメソッドのフレームをポップして破棄します。

このスタックフレームには3つの部分があります。

スタックフレームのサイズは、そのメソッドのローカル変数とオペランドスタックによって異なります。測定の単位は単語です。

JVMが関数またはメソッドを呼び出すと、クラスデータをチェックして、ローカル変数とオペランドスタック内のメソッドに必要なワード数を決定し、そのメソッドに適切なサイズのスタックフレームを作成してから、スタックにプッシュします。

メソッドまたは関数を呼び出すたびに、スタックフレームが作成されます。作成されたスタックフレームには、そのメソッドに関するすべての情報が含まれており、実行中、コードは現在のスタックフレームの値にのみアクセスできます。

3. ループ

Scalaは、すべてのプログラミング言語と同様に、ループを作成する機能を提供します。例として、必須と機能の両方で数値のListの合計を取得しようとします。

数値のリストの合計を強制的に計算する例を次に示します。

def getSumOfList(list: List[Int]): Int = {
  var sum = 0
  for (i <- 0 until list.length) {
    sum += list(i)
  }
  sum
}
assert(getSumOfList((1 to 10).toList) == 55)

これは正しいように見えますが、機能しておらず、リストをより小さなリストに分割して別のスレッドで実行すると、競合状態などの問題が発生しやすくなります。蓄積。 Scalaは、本質的な場合を除いて、varの使用を推奨していません。

ループを実装するもう1つの方法は、再帰を使用することです。

3.1. 再帰

再帰は、関数がそれ自体を直接または間接的に呼び出すプロセスを定義します。ほとんどの問題は、再帰を使用して解決されます。これは、問題が基本条件または再帰が停止して合計結果が照合される終了条件に達するまで、問題をより小さなタスクに分割するためです。

再帰の使用は、forループを使用するよりもループを作成するためのより機能的なアプローチです。 Scalaは、機能ループの使用を強く推奨しています。

再帰的アルゴリズムは、非常に深い呼び出しスタックを作成し、スタックスペースを使い果たすことがあります。

再帰を使用してリストの同じ合計を計算する例を次に示します。

def getSumOfListRecursive(list: List[Int]): Int = {
  list match {
    case Nil => 0
    case head :: tail =>
      head  +  getSumOfListRecursive(tail)
  }
}
assert(getSumOfListRecursive((1 to 10).toList) == 55)

varが見えないことがわかります。 List でインデックス付きルックアップを実行していないため、コードはより効率的です。

var を使用する代わりに、 getSumOfList がそれ自体を呼び出すたびに、新しいスタックフレームを独自の変数セットを使用して呼び出しスタックにプッシュし、そのときにポップします。特定の機能が完了しました。

このソリューションは十分に簡潔に見えますが、次の例に示すように、非常に大きなListを合計してみましょう。

getSumOfListRecursive((1 to 10000).toList)

このエラーが発生しました：

Exception in thread "main" java.lang.StackOverflowError

このStackOverflowErrorは、スタック内に処理できるよりもはるかに多くのスタックフレームがあったことを意味します。

再帰関数がそれ自体を呼び出すときはいつでも、関数の新しいインスタンスの情報と他の関数情報がスタックにプッシュされます。このため、再帰の各レベルには新しいスタックフレームが必要です。

その結果、再帰関数はスタックに割り当てられたメモリをますます消費します。 sum関数がそれ自体を1000回呼び出すと、1000のスタックフレームが作成されます。

これは、大きなデータ構造で再帰を使用できないことを意味しますか？幸い、Scalaは、末尾再帰と呼ばれる大きなデータ構造で再帰を使用できるようにする効率的なメカニズムを提供します。

3.2. 末尾再帰関数

テール再帰関数は、最後のアクションがそれ自体への直接呼び出しである関数を記述します。再帰関数がこのように記述されている場合、Scalaコンパイラは、再帰のレベルごとに1つのスタックフレームではなく、関数が1つのスタックフレームのみを必要とするように、結果のJVMバイトコードを最適化できます。

通常の再帰は多くのスタックフレームを作成し、深いレベルの再帰を必要とするアルゴリズムの場合、これはStackOverflowErrorを作成します（そしてプログラムをクラッシュさせます）。

Scalaコンパイラーは末尾再帰関数を見つけると、本質的にそれをwhileループに変えることによってそれを最適化することを知っています。これは、再帰呼び出しがなくなり、スタックにプッシュされるフレームがなくなることを意味します。

末尾再帰を使用してListの合計を計算する同じ例を次に示します。

def getSumOfListTailRecursive(numbers: List[Int]): Int = {
  def innerFunction(list: List[Int], accumulator: Int): Int = {
    list match {
      case Nil => accumulator
      case head :: tail => innerFunction(tail, head + accumulator)
    }
  }
  innerFunction(numbers, 0) // give an initial accumulator
}
assert(getSumOfListTailRecursive((1 to 1000000).toList) == 1784293664)

末尾再帰関数を使用すると、非常に大きなリストに対して再帰を実行できました。 リストのサイズを大きくしても、StackOverflowErrorに遭遇しないようにすることができます。

この例を以前の非末尾再帰関数と比較すると、末尾再帰関数では、関数の最後のアクションはそれ自体の呼び出しでしたが、前者では次のようになりました。

head + getSumOfListRecursive(t)

Scalaコンパイラーは、末尾再帰ではなく、再帰の各レベルに新しいスタックフレームをもたらすため、これを最適化できませんでした。

関数が末尾再帰であるかどうかを確認する1つの方法は、関数の先頭にこのアノテーションを追加することです。

@scala.annotation.tailrec

このように、関数が末尾再帰でない場合、コードはコンパイルされません。

3.3. 再帰でのスタックフレームの使用

末尾再帰関数で使用される単一のスタックフレームと非末尾再帰関数で使用される複数のスタックフレームの使用法を証明するために、関数が開始された時点と関数が開始した時点でのスタックフレーム数の差を簡単に出力できます。再帰の最後のレベルに達したとき。これは、 List が空の場合、またはNilの場合です。

非テール再帰関数で使用されるスタックフレームの数を出力する例を次に示します。

val length = Thread.currentThread().getStackTrace.length + 1
def getSumOfListRecursive(list: List[Int]): Int = {
  list match {
    case Nil =>
      println(Thread.currentThread().getStackTrace.length - length) // prints 100 for 100 items
      0
    case h :: t =>
      h + getSumOfListRecursive(t)
  }
}
assert(getSumOfListRecursive(1 to 100 toList) == 5050)

関数が開始する前に作成されたスタックフレームの数と最後の再帰レベルの違いを確認することにより、作成されたスタックフレームの数と非末尾再帰関数の再帰レベルの数の間に直接的な比例関係がわかります。

末尾再帰関数で使用されるスタックフレームの数を出力する例を次に示します。

val length = Thread.currentThread().getStackTrace.length + 1
def getSumOfListTailRecursive(numbers: List[Int]): Int = {
  def innerFunction(list: List[Int], accumulator: Int): Int = {
    list match {
      case Nil =>
        println(Thread.currentThread().getStackTrace.length - length) // prints 1 for 1000000 items
        accumulator
      case head :: tail =>
        innerFunction(tail, head + accumulator)
    }
  }
  innerFunction(numbers, 0) // give an initial accumulator
}
assert(getSumOfListTailRecursive((1 to 1000000).toList) == 1784293664)

非末尾再帰関数では、100万個のアイテムを処理しているにもかかわらず、スタックフレームが1つしか作成されていないことがわかります。

4. 結論

この記事では、scalaを使用して、必須および機能の両方でループを作成する方法について説明しました。また、ループを作成するための機能的なアプローチとして再帰とその欠点、および末尾再帰関数の実装がこれらの欠点をどのように解決するかについても検討しました。

コードスニペットと例は、GitHubのにあります。

getdocs

13036