1

このコードがひどく非効率的であることは別として、ここで再帰関数を書いているこの方法は「良いスタイル」と見なされます。たとえば、ラッパーを作成してそれを渡しているのint midと同様に、 counterを渡しint countます。

このコードが行うことは、配列から値を取得し、それを と組み合わせた値blockIndexが より大きいかどうかを確認することmidです。では、非効率であることは別として、このような再帰関数を書く仕事を得ることができるでしょうか?

int NumCriticalVotes :: CountCriticalVotesWrapper(Vector<int> & blocks, int blockIndex)
{

    int indexValue = blocks.get(blockIndex);
    blocks.remove(blockIndex);
    int mid = 9;

    return CountCriticalVotes(blocks, indexValue, mid, 0);
}


int NumCriticalVotes :: CountCriticalVotes(Vector<int> & blocks, int blockIndex, int mid, int counter)
{
    if (blocks.isEmpty())
    {
        return counter;
    }

    if (blockIndex + blocks.get(0) >= mid)
    {
        counter += 1;
    } 

    Vector<int> rest = blocks;
    rest.remove(0);
    return CountCriticalVotes(rest, blockIndex, mid, counter);
}
4

5 に答える 5

2

これは、十分に小さいコレクションで機能する範囲で有効です。

ただし、これは非常に非効率的です。再帰呼び出しごとに、Vectorのカウントされていない部分全体のコピーを作成します。したがって、たとえば1000アイテムを含むベクトルを数える場合、最初に999アイテムのベクトルを作成し、次に998アイテムのベクトルを作成し、次に997アイテムのベクトルを作成し、以下同様に0アイテムまで作成します。

これ自体はかなり無駄ですが、さらに悪化するようです。次に、ベクターからアイテムを削除しますが、最初のアイテムを削除します。ベクターがのようなものであると仮定するとstd::vector、最後のアイテムの削除には一定の時間がかかりますが、最初のアイテムの削除には直線的な時間がかかります。つまり、最初のアイテムを削除するには、その後の各アイテムが空いた場所に「前方」にシフトされます。

これは、一定の空間と線形時間をとる代わりに、アルゴリズムが空間と時間の両方で2次式であることを意味します。関連するコレクションが非常に少ない場合を除いて、それはかなり無駄になります。

呼び出しごとにまったく新しいVectorを作成する代わりに、既存のVectorにオフセットを渡すだけです。これにより、アイテムのコピーと削除の両方が回避されるため、時間と空間の両方で線形にするのは非常に簡単です（これはまだ最適値にはほど遠いですが、少なくとも2次式ほど悪くはありません）。

使用するスペースをさらに減らすには、アレイを2つの半分として扱います。それぞれの半分を別々に数え、結果を合計します。これにより、再帰の深さが線形ではなく対数に減少します。これは一般にかなり重要です（たとえば、1000アイテムの場合、深さは約1000ではなく約10になります。100万アイテムの場合、深さはではなく約20になります。 100万）。

于 2012-12-12T19:05:37.717 に答える
1

ソリューションの問題は、カウントを渡すことです。カウントの受け渡しを停止し、スタックを使用してカウントを追跡します。もう1つの問題は、2番目の条件が何を想定しているのかわからないことです。

int NumCriticalVotes :: CountCriticalVotesWrapper(Vector<int> & blocks, int blockIndex)
{

    int indexValue = blocks.get(blockIndex);
    blocks.remove(blockIndex);
    int mid = 9;

    return CountCriticalVotes(blocks, indexValue, mid);
}


int NumCriticalVotes :: CountCriticalVotes(Vector<int> & blocks, int blockIndex, int mid)
{
    if (blocks.isEmpty())
    {
        return 0;
    }

    if (/*Not sure what the condition is*/) 
    {
        return 1 + CountCriticalVotes(blocks, blockIndex, mid);
    }

    return CountCriticalVotes(blocks, blockIndex, mid);
}
于 2012-12-12T19:01:39.357 に答える
1

非常に主観的な質問。末尾再帰は（私の本では）素晴らしいですが、呼び出しごとに新しいベクトルを作成することとバランスを取り、線形アルゴリズムを2次にします。再帰とは関係なく、特に簡単に回避できるため、これは大きな問題です。

コードが何を達成しようとしているのかについてのいくつかのコメントも役に立ちますが、コンテキストではそれほど問題はないと思います。

于 2012-12-12T19:07:06.110 に答える
1

C++ では、再帰を使用して任意の長さのリストをトラバースすることは、決して良い方法ではありません。パフォーマンスだけではありません。標準では末尾呼び出しの最適化が義務付けられていないため、リストのサイズが制限されていることを保証できない場合、スタック オーバーフローのリスクがあります。

確かに、再帰の深さは通常のスタック サイズで数十万回に及ぶ必要がありますが、プログラムを設計するときに、将来どのような種類の入力を処理できなければならないかを知ることは困難です。問題は、ずっと後にあなたを悩ませるために戻ってくるかもしれません.

于 2012-12-12T19:14:16.210 に答える
1

あなたが達成しようとしていることを正確に知らなければ、これは答えるのが非常に難しい質問です. 私は、再帰、または一般的なコーディングについて、次の 3 つの要件を満たしていると考えています。

  1. 必要なすべての機能を実現していますか?
  2. エラー耐性はありますか? つまり、無効な入力が渡​​されたとき、またはエッジケースが渡されたときに壊れません。
  3. 十分な時間内に目標を達成できていますか?

3番が気になっていると思いますが、時間は問題に合わせるべきだと言えます。たとえば、2 つの巨大なリストを検索する場合、O(n^2) はおそらく受け入れられません。ただし、2 つの小さなセットを検索している場合、O(n^2) はおそらく十分に高速です。

私が言えることは、テストケースでアルゴリズムのさまざまな実装のタイミングを試すことです。ソリューションが再帰的であるからといって、「力ずく」の実装よりも常に高速であるとは限りません。（もちろん、これはケースによって異なります）。

あなたの質問に答えるために、再帰に関する限り、このサンプルは問題ないようです。しかし、あなたはこのようなコードを書く仕事を得るでしょうか? これが他の 2 つのコーディング要件をどの程度満たしているかわかりません。

于 2012-12-12T18:57:54.423 に答える