18

私の知る限り、再帰は非常にエレガントですが、OOPおよび手続き型プログラミングでは非効率的です（すばらしい「高次perl」、Mark Jason Dominusを参照）。関数型プログラミングでは再帰が高速であるという情報がいくつかありました。その優雅さとシンプルさを維持しています。誰かがこれを確認し、おそらく増幅することができますか？私はXSLTとHaskellの観点から考えています（私の次の学習言語リストの上位にあります）

ありがとう

ダニエル

4

8 に答える 8

20

末尾再帰は、まともな関数型言語の実装における反復です。GHC Haskell を使用した例を次に示します。数列を追加する簡単なプログラム。これは、いくつかの再帰関数の構成として始まります。

import qualified Data.Vector as U

main = print (U.sum (U.enumFromTo 1 (10000000 :: Int)))

コンパイラーが(ソースからソースへの変換で)シングルテール再帰関数に最適化するもの:

loop x y = case y <= y 10000000 of
      False -> x
      True  -> loop (x + y) (y + 1)

次に、この再帰関数は単純なループにコンパイルされます。

loop:
    .Lc216:
            cmpq $10000000,%rsi
            jle .Lc219
            movq %r14,%rbx
            movq (%rbp),%rax
            jmp *(%rax)
    .Lc219:
            addq %rsi,%r14
            incq %rsi
            jmp loop

または、GHC LLVM バックエンドを使用すると、プログラムの命令表現に追加の最適化が適用されます。

    loop:
        leaq    1(%rsi), %rax
        addq    %rsi, %r14
        cmpq    $10000001, %rax
        jge     .LBB1_5
        addq    $2, %rsi
        addq    %rax, %r14
    test:                                # %tailrecurse
        cmpq    $10000001, %rsi
        jl      loop

末尾の再帰ラベルがどのようにタグ付けされているかに注意してください。

そのため、スタックを使用しない単一の命令型ループにコンパイルされた単一の末尾再帰関数にコンパイルされた再帰関数のパイプラインがありました。そして最後に8つの命令。

そしてそれが、関数合成と再帰の両方が、優れた最適化関数言語で非常に効率的である理由です。

于 2010-02-26T17:00:24.950 に答える
7

OOP/手続き型言語は、再帰呼び出しが行われるたびにデータをスタックに配置する傾向があります。したがって、再帰は、これらの言語の反復ほど効率的ではありません。

対照的に、関数型言語のコンパイラ/インタプリタは通常、反復と同じくらい効率的になるように末尾再帰を最適化するように設計されています。

再帰にはスタックの維持が必要な場合がありますが、末尾再帰はコンパイラによって認識され、命令型言語で反復を実装するために使用される同じコードに最適化されます。Scheme プログラミング言語標準では、末尾再帰を認識して最適化する実装が必要です。末尾再帰の最適化は、コンパイル時にプログラムを継続渡しスタイルに変換するなどの方法で実装できます。

what-is-tail-call-optimizationとwhich-languages-support-tail-recursion-optimizationには、より詳細な情報があります。

于 2010-02-26T16:03:20.843 に答える
6

使用中のコンパイラが末尾呼び出しの最適化をサポートしていて、それを利用するようにコードを構成する場合、再帰は非効率的ではありません。

関数型プログラミングでは再帰が普及しているため、関数型言語のコンパイラは、手続き型の最適化よりも末尾呼び出しの最適化を実装する可能性が高くなります。

于 2010-02-26T16:17:10.067 に答える
3

XSLT での効率的な再帰

XSLT で効率的な再帰を実現するには、主に 2 つの方法があります。

  1. 末尾再帰の最適化
  2. 分割統治 (DVC)

末尾再帰をカバーする多くの回答があるため、ここに簡単な例を示します。

  <xsl:function name="my:sum">
   <xsl:param name="pAccum" as="xs:double*"/>
   <xsl:param name="pNums" as="xs:double*"/>

   <xsl:sequence select=
     "if(empty($pNums))
        then $pAccum
        else
           my:sum($pAccum + $pNums[1], $pNums[position() >1])
     "
   />
 </xsl:function>

my:sum(0, 1 to 100) が 5050 に評価されることを確認できます。

sum()DVC の方法で関数を実装する方法は次のとおりです。

  <xsl:function name="my:sum2">
      <xsl:param name="pNums" as="xs:double*"/>

      <xsl:sequence select=
        "if(empty($pNums))
          then 0
          else
            if(count($pNums) eq 1)
              then $pNums[1]
              else
                for $half in count($pNums) idiv 2
                  return
                    my:sum2($pNums[not(position() gt $half)]) 
                   + 
                    my:sum2($pNums[position() gt $half])

        "
      />
  </xsl:function>

DVC の背後にある主なアイデアは、入力シーケンスを (通常は) 2 つ以上の部分に分割し、それらを互いに独立して処理し、結果を結合して入力シーケンス全体の結果を生成することです。

アイテムのシーケンスの場合N、任意の時点での呼び出しスタックの最大深度は を超えないことlog2(N)に注意してください。これは、ほとんどの実用的な目的には十分です。たとえば、1000000 (1M) アイテムのシーケンスを処理するときのコール スタックの最大深度は、わずか 19 です。

一部の XSLT プロセッサは末尾再帰を認識して最適化するほどスマートではありませんが、DVC 再帰テンプレートはどの XSLT プロセッサでも機能します。

于 2010-02-26T20:44:30.620 に答える
2

ドンの答えに追加しなければならない唯一のことは、多くの言語がレガシー呼び出し規約の人質であるということです。これは、x86 の C 呼び出し規約に準拠する言語ほど真実ではありません。すべてのパラメーターがスタックに置かれます。関数型言語は、少なくともいくつかのパラメーターをレジスターで渡します。したがって、32 ビット プラットフォームでは、非末尾呼び出し (最適化できない) でさえ、たとえば C よりも効率的です。

神に感謝します x86-64 にはまともな C 呼び出し規約があります!

于 2010-02-28T03:18:00.600 に答える
1

言語がコンパイラによって最適化されていない場合、再帰は反復よりも遅くなる可能性が非常に高くなります。これは、反復とほとんど同じである特定のレーンを下っていくことに加えて、仕事。

それ以外の場合は、コンパイラとシステムが舞台裏でループを処理できるようにするため、はるかに洗練されていることを除けば、ほとんど同じです。もちろん、再帰が唯一の方法であるタスク (ツリーのような構造の処理など) もあります (少なくとも、絶望的に複雑でない唯一の方法です)。

于 2010-02-26T16:07:53.190 に答える
0

再帰と反復が懸念事項であると思い込まないでください。

通常、これは、一連のより大きなパフォーマンスの問題を最初に排除した後で重要になります。

于 2010-02-26T23:46:39.967 に答える
0

関数型言語で再帰が高速になるのは、コンパイラが末尾再帰の削除 (または、より一般的には末尾呼び出しの削除) を使用して再帰を反復に内部的に変換できるためです。基本的に、再帰呼び出しが関数が戻る前の最後の操作であり、関数の戻り値が再帰呼び出しの値である場合、プログラムは新しいスタック フレームを作成する代わりに、現在のフレームを再利用します。引数変数は新しい値に設定され、PC は関数の先頭に設定されます。

末尾再帰の除去を利用するには、プログラマーがある程度意識する必要があります。再帰呼び出しが実際に末尾呼び出しであることを確認する必要があります。たとえば、階乗を計算する OCaml のコードは次のとおりです。

let rec factorial n =
  if n = 0 then
    1
  else
    n * factorial (n - 1)

再帰呼び出しの後に乗算を実行する必要があるため、末尾呼び出しの削除はここでは直接機能しません。ただし、関数が次のように書き直された場合:

let factorial n =
  let rec fac_helper n p =
    if n = 0 then
      p
    else
      fac_helper (n - 1) (p * n)
   in
   fac_helper n 1

これで、テール コールの除去が使用できるようになりました。これは次のように変換されます (疑似コード):

factorial p n = 
  p = 1
  while n > 0
    n = n - 1
    p = p * n
  return p

このスタイルは直感に反するように見えるかもしれませんが、反復バージョンと同じくらい理にかなっています。計算の各ステップは、再帰関数の呼び出しで実行されます。pおよび上記のような誘導変数nは、計算全体で使用され、引数として宣言されます。

命令型言語と関数型言語の両方のほとんどのコンパイラが、この最適化を利用していることに注意してください。実際、LLVM のバージョンの最適化では、再帰呼び出しとリターンの間の連想操作も許可されているため、factorial の最初のバージョンを作成しても最適化を使用できます。ただし、テール コールの削除は JVM ではサポートされていないため、Scala などの JVM 上の関数型言語ではサポートが限定されています。

于 2010-02-26T16:45:02.100 に答える