6

最近のSOの質問で述べたように、私はプロジェクトオイラーの問題を経験してF＃を学んでいます。

私は今、次のように見える問題3に対する機能的な答えを持っています：

let rec findLargestPrimeFactor p n = 
    if n = 1L then p
    else
        if n % p = 0L then findLargestPrimeFactor p (n/p)
        else findLargestPrimeFactor (p + 2L) n

let result = findLargestPrimeFactor 3L 600851475143L

ただし、への異なる呼び出しにつながる可能性のある実行パスが2つあるfindLargestPrimeFactorため、末尾再帰用に最適化できるかどうかはわかりません。だから私は代わりにこれを思いついた：

let rec findLargestPrimeFactor p n = 
    if n = 1L then p
    else
        let (p', n') = if n % p = 0L then (p, (n/p)) else (p + 2L, n)
        findLargestPrimeFactor p' n'

let result = findLargestPrimeFactor 3L 600851475143L

への末尾呼び出しにつながるパスは1つしかないためfindLargestPrimeFactor、実際に末尾再帰用に最適化されると思います。

だから私の質問：

  1. 2つの異なる再帰呼び出しがある場合でも、最初の実装を末尾再帰用に最適化できますか？
  2. 両方のバージョンを末尾再帰用に最適化できる場合、一方が他方よりも優れている（より「機能的」、高速など）のでしょうか。
4

2 に答える 2

9

最初のfindLargestPrimeFactor関数は末尾再帰です。複数の再帰呼び出しがある場合でも、すべての再帰呼び出しが末尾位置で発生すると、関数を末尾再帰にすることができます。

コンパイルされた関数のILは次のとおりです。

.method public static int64  findLargestPrimeFactor(int64 p,
                                                    int64 n) cil managed
{
  .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = ( 01 00 02 00 00 00 01 00 00 00 01 00 00 00 00 00 ) 
  // Code size       56 (0x38)
  .maxstack  8
  IL_0000:  nop
  IL_0001:  ldarg.1
  IL_0002:  ldc.i8     0x1
  IL_000b:  bne.un.s   IL_000f
  IL_000d:  br.s       IL_0011
  IL_000f:  br.s       IL_0013
  IL_0011:  ldarg.0
  IL_0012:  ret
  IL_0013:  ldarg.1
  IL_0014:  ldarg.0
  IL_0015:  rem
  IL_0016:  brtrue.s   IL_001a
  IL_0018:  br.s       IL_001c
  IL_001a:  br.s       IL_0026
  IL_001c:  ldarg.0
  IL_001d:  ldarg.1
  IL_001e:  ldarg.0
  IL_001f:  div
  IL_0020:  starg.s    n
  IL_0022:  starg.s    p
  IL_0024:  br.s       IL_0000
  IL_0026:  ldarg.0
  IL_0027:  ldc.i8     0x2
  IL_0030:  add
  IL_0031:  ldarg.1
  IL_0032:  starg.s    n
  IL_0034:  starg.s    p
  IL_0036:  br.s       IL_0000
} // end of method LinkedList::findLargestPrimeFactor

句の最初の分岐else（つまり、if n % p = 0L）はIL_0013で始まり、IL_0024まで続き、そこで無条件に関数のエントリポイントに分岐します。

else句の2番目の分岐は、IL_0026で始まり、関数の終わりまで続き、そこで再び無条件に関数の先頭に戻ります。F＃コンパイラは、再帰呼び出しを含むelse句の両方の場合について、再帰関数をループに変換しました。

于 2013-02-22T19:16:55.553 に答える
6

2つの異なる再帰呼び出しがある場合でも、最初の実装を末尾再帰用に最適化できますか？

再帰ブランチの数は、末尾再帰と直交しています。最初の関数はfindLargestPrimeFactor、2つのブランチの両方での最後の操作であるため、末尾再帰です。疑わしい場合は、関数をReleaseモード（末尾呼び出しの最適化オプションがデフォルトでオンになっている）で実行して、結果を観察することができます。

両方のバージョンを末尾再帰用に最適化できる場合、一方が他方よりも優れている（より「機能的」、高速など）のでしょうか。

2つのバージョンにはわずかな違いがあります。2番目のバージョンでは、余分なタプルが作成されますが、計算がそれほど遅くなることはありません。私は最初の関数をより読みやすく、要点をまっすぐに考えています。

気を悪くするために、最初のバリアントはelifキーワードを使用して短くなります。

let rec findLargestPrimeFactor p n = 
    if n = 1L then p
    elif n % p = 0L then findLargestPrimeFactor p (n/p)
    else findLargestPrimeFactor (p + 2L) n

別のバージョンは、パターンマッチングを使用することです。

let rec findLargestPrimeFactor p = function
    | 1L -> p
    | n when n % p = 0L -> findLargestPrimeFactor p (n/p)
    | n -> findLargestPrimeFactor (p + 2L) n

基礎となるアルゴリズムは同じであるため、どちらも高速にはなりません。

于 2013-02-22T19:24:14.997 に答える