0

ケース 1 :

int fun(int num)
{
    if (num == 1)
        return 1;
    else
        return num * fun(num - 1);
}

ケース 2:

int fun(int num)
{
    int i = 1;
    do
    {
        i = i * num;
        num--;
    }
    while (num);
    return i;
}

インタビューの質問で上記の質問を受け、どちらがより高速でメモリの消費量が少ないかについて尋ねました。コードの行を数えるだけで推測したことを除いて、どちらが速いかを見つける方法は本当にわかりません。しかし、それは正しい方法ではないと思います。この種の質問を解決するには、何を考慮すればよいでしょうか。

アップデート

上記のシナリオだけでなく、一般的なケースを求めています。

4

6 に答える 6

3

コードサイズ

コード サイズに関しては、最初の実装をファイルf1.cに、2 番目の実装を に配置しましたf2.c。

$ gcc -c f1.c f2.c
$ size f1.o f2.o
__TEXT  __DATA  __OBJC  others  dec hex
123 0   0   0   123 7b  f1.o
119 0   0   0   119 77  f2.o
$ gcc -O3 -c f1.c f2.c
$ size f1.o f2.o
__TEXT  __DATA  __OBJC  others  dec hex
372 0   0   0   372 174 f1.o
362 0   0   0   362 16a f2.o
$

どちらの実装でも、コード サイズにほとんど違いがないことに注意してください。ただし、興味深いことに、最適化されたコードは、最適化されていないコードよりもはるかに大きくなります (約 3 倍)。

(コンパイラ: Mac OS X 10.7.5 上の GCC 4.7.1。)

階乗 (これらの関数が実装するもの) は非常に急速に成長することに注意してください。実は13！は大きすぎて 32 ビットの符号なし整数 21 に収まりません! は大きすぎて 64 ビットの符号なし整数に収まらず、35! は大きすぎて 128 ビットの符号なし整数に収まりません (そのようなタイプのコンピューターが見つかれば)。

コード速度 — 逆張りの発見!

また、仮定に注意してください。反復ソリューションは再帰ソリューションよりも高速であると予想していました。しかし、測定はそうではないことを示唆しています。

テストは、2.3 GHz Intel Core i7 (および 16 GiB メモリですが、メモリはこの計算の要素ではありません) を搭載した MacBook Pro で実行されました。

測定によると、コードが最適化されている場合、再帰ソリューションは一貫して純粋な反復ソリューションよりも少し高速です。これは私の予想とはまったく逆ですが、パフォーマンス測定が必要な理由を示しています。

最適化されたコード

# iteration
# Count    = 10
# Mean     =   0.799869
# Variance =   0.000011

# recursion
# Count    = 10
# Mean     =   0.750904
# Variance =   0.000014

後でルックアップ テーブル関数を追加しましたが、その時間は次のとおりです。

# lookuptab
# Count    = 10
# Mean     =   0.213836
# Variance =   0.000004

そして、テスト ハーネスのオーバーヘッドを測定するために入力パラメーターを返すだけの関数を追加したところ、次の結果が得られました。

# over-head
# Count    = 10
# Mean     =   0.211325
# Variance =   0.000001

したがって、配列ルックアップの計算コストは​​非常に小さくなります。

最適化されていないコード

オプティマイザーの能力に疑問を持ったことがある場合は、最適化されていないビルドの最適化された時間をこれらと比較してください。

# iteration
# Count    = 10
# Mean     =   1.852833
# Variance =   0.000020

# recursion
# Count    = 10
# Mean     =   2.937954
# Variance =   0.000059

ルックアップ テーブルのバージョン:

# lookuptab
# Count    = 10
# Mean     =   0.730275
# Variance =   0.000026

そしてオーバーヘッドバージョン：

# over-head
# Count    = 10
# Mean     =   0.633132
# Variance =   0.000009

一般的な観察

  • 単純な「コード行」だけでは、パフォーマンスについては何もわかりません。
  • 測定は当て推量に勝る。
  • オプティマイザは優れています。

コードの行数を単純に数えることが適切なガイドラインではない理由は、行ごとにコストが異なるためです。たとえば、 、 、 などの関数の呼び出しを含む 1 行のコードはsin()、cos()(tan()おそらく) 単一の整数算術演算と代入を含む 20 行のコードよりもはるかにコストがかかります。

問題のように、2 つの非常によく似た関数を比較すると、より複雑な再帰は単純な反復よりも遅くなる傾向があります。しかし、示されているように、特に階乗などの単純な末尾再帰関数の場合、コンパイラが最適化に成功すると、そのような推測された結果が間違っている可能性があります。

タイミングの詳細

テストプログラムは次のとおりです。

static int fun1(int num)
{
    if (num == 1)
        return 1;
    else
        return num * fun1(num - 1);
}

static int fun2(int num)
{
    int i=1;
    do{
        i = i * num;
        num--;
    } while (num);
    return i;
}

static int fun3(int num)
{
    static const int factorial[] =
    {   1, 1, 2, 6, 24, 120, 720, 5040, 40320,
        362880, 3628800, 39916800, 479001600,
    };
    enum { MAX_FACTORIAL_NUM = (sizeof(factorial)/sizeof(factorial[0])) };
    if (num < 0 || num >= MAX_FACTORIAL_NUM)
        return 0;
    else
        return factorial[num];
}

static int fun4(int num)
{
    return num;
}

#include "timer.h"
#include <stdio.h>

static void tester(char const *name, int (*function)(int))
{
    char buffer[32];
    Clock  clk;
    unsigned long long sumfact = 0;

    clk_init(&clk);
    clk_start(&clk);
    for (int i = 0; i < 100000000; i++)
        sumfact += (*function)(i % 12 + 1);
    clk_stop(&clk);
    printf("%s: %s (%llu)\n", name, clk_elapsed_us(&clk, buffer, sizeof(buffer)), sumfact);
}

int main(void)
{
    for (int i = 0; i < 10; i++)
    {
        tester("recursion", fun1);
        tester("iteration", fun2);
        tester("lookuptab", fun3);
        tester("over-head", fun4);
    }
    return(0);
}

テスト コードは、2 つの関数を可能な限り対称的に扱うように注意し、各関数を交互にテストして、バックグラウンド プロセスがパフォーマンスに干渉する可能性を減らします。(通常、バックグラウンドで実行されている BOINC プロセスは、これらのテストではオフにされました。以前の質問のタイミングに関する経験から、それらが結果に深刻な影響を与え、結果により多くのばらつきをもたらすことが示されています。)

最適化された ( -O3) ビルドの raw 時間

ルックアップ テーブルまたはオーバーヘッド関数のない初期バージョンのプログラム。

recursion: 0.754428 (4357969100681262)
iteration: 0.799330 (4357969100681262)
recursion: 0.749773 (4357969100681262)
iteration: 0.798897 (4357969100681262)
recursion: 0.747794 (4357969100681262)
iteration: 0.800977 (4357969100681262)
recursion: 0.748282 (4357969100681262)
iteration: 0.792708 (4357969100681262)
recursion: 0.748342 (4357969100681262)
iteration: 0.798776 (4357969100681262)
recursion: 0.748377 (4357969100681262)
iteration: 0.801641 (4357969100681262)
recursion: 0.750115 (4357969100681262)
iteration: 0.802468 (4357969100681262)
recursion: 0.750807 (4357969100681262)
iteration: 0.802829 (4357969100681262)
recursion: 0.751296 (4357969100681262)
iteration: 0.796841 (4357969100681262)
recursion: 0.759823 (4357969100681262)
iteration: 0.804221 (4357969100681262)

real        0m15.575s
user        0m15.556s
sys         0m0.027s

最適化されていないビルドの生時間

ルックアップ テーブルまたはオーバーヘッド関数のない初期バージョンのプログラム。

recursion: 2.951282 (4357969100681262)
iteration: 1.852239 (4357969100681262)
recursion: 2.932758 (4357969100681262)
iteration: 1.851512 (4357969100681262)
recursion: 2.924796 (4357969100681262)
iteration: 1.862686 (4357969100681262)
recursion: 2.946792 (4357969100681262)
iteration: 1.846961 (4357969100681262)
recursion: 2.941705 (4357969100681262)
iteration: 1.849099 (4357969100681262)
recursion: 2.938599 (4357969100681262)
iteration: 1.852089 (4357969100681262)
recursion: 2.930713 (4357969100681262)
iteration: 1.854765 (4357969100681262)
recursion: 2.935669 (4357969100681262)
iteration: 1.851478 (4357969100681262)
recursion: 2.938975 (4357969100681262)
iteration: 1.856979 (4357969100681262)
recursion: 2.938250 (4357969100681262)
iteration: 1.850521 (4357969100681262)

real        0m47.980s
user        0m47.939s
sys         0m0.041s

両方の階乗関数のコードにバグがあることに注意してください。0! を計算するように求められると、どちらも長時間実行ループに入ります (そして、32 ビットint型をオーバーフローさせることによってあらゆる種類の未定義の動作を呼び出します)。これは実際には適切に定義されており、値は 1 です。そのため、テスト ハーネスでの呼び出しは私が最初に書いたよう(*function)(i % 12 + 1)ではなく。(*function)(i % 13)

于 2013-02-09T16:28:14.370 に答える
3

使用しているコンパイラと最適化によって異なりますが (優れたコンパイラは最初のコードを反復処理に変えることができます)、一般的には、2 番目のソリューションの方が高速で、使用するメモリが少なくて済みます (再帰呼び出しでスタック フレームを作成する必要があるため)。 ）。

于 2013-02-09T16:19:21.497 に答える
2

(1) 再帰を使用しており、スタック オーバーフローの対象となる可能性があります。(2) は反復的であり、一定量のメモリを使用します。(2) の方が速いと思います。

逆アセンブルされたコードを見ると、(1) にはcallループ カウンターのインクリメント/デクリメントよりもコストのかかる命令があります。ただし、関数の引数として 1 を渡すと、おそらく (1) の方が高速になると思います。引数が 1 より大きい場合は、(2) をより高速に実行する必要があります。

于 2013-02-09T16:17:37.180 に答える
0

ループは関数呼び出しよりも単純で、いつアセンブリにコンパイルされるかについて言えます。

コードが呼び出される前後のタイムスタンプとメモリ使用量を測定して比較することで、所要時間とメモリ使用量を測定できます。

于 2013-02-09T16:17:40.097 に答える
0

反復 (再帰のない 2 つ目) の方が高速です。

パフォーマンス分析でこの記事を確認してください: http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches

于 2013-02-09T16:20:52.973 に答える
0

より多くのメモリを使用する理由は、問題を解決するために再帰的にスペースを消費するためです。問題は再帰自体ではありません。再帰はスタック領域を使用しないように実装できるためです (少なくとも、「テール」再帰をペナルティなしで使用できる特定の言語では)。ただし、書かれているように、これは末尾再帰ではありません。再帰呼び出しの結果は、アクティブな呼び出しの結果で乗算する必要がありnumます (これはもっとうまく書くことができます。申し訳ありません)。

于 2013-02-09T16:28:00.353 に答える