gotoの使用とランタイムコードの評価
質問
最近、プログラミングクラスでは、 n を指定すると、配列のすべての可能な混乱を生成する任意の言語でプログラムを作成する割り当てが与えられました p p [i]!= iのようなすべてのi:0 <!> lt; = i <!> lt; n。イテレータを使用する必要がありました。 yield
。
例:n = 3、[0、1、2]は混乱ではありませんが、[2、0、1]は[1、2、0]と同様です。
機能する擬似コードソリューションを思いつきましたが、問題は電源ループ(つまり、 n が n ランタイム)。これを行うために、Rubyコードで文字列に n ネストされたループを生成し、文字列をeval
-edしました。私のソリューションは機能しましたが、教授は、動的なコード生成よりも、数個のgoto
を使用する方が(少なくとも読みやすい)より良いソリューションになると考えていました。
<=>は常に悪い選択であるという印象を受けました。動的に生成されたコードのランタイム評価が<=>よりも悪い選択になるのはなぜですか?生成されたコードはクリーンでシンプルであり、与えられた問題に対してかなり効率的です。コード生成が依存する唯一のユーザー入力は n で、事前に整数値であることを確認するためにチェックされます。それは<=>唯一の混乱であるはずです。
プログラミングの割り当てに対する解決策を求めているのではなく、動的コード評価での<=>の使用の背後にある理由、またはその逆を知りたいだけです。
編集:明確にするために、イテレータを使用したプログラムと再帰を使用したプログラムの作成が割り当てに含まれていたため、反復バージョンは必ずしも効率的であるとは限りませんでした。
解決
これは本当に興味深い質問です-明確な答えがあるかどうかわかりません。
gotoの問題は、構造化されていない方法での使用です-gotoは<!> quot; massive random leap <!> quot;です。したがって、一般的な例では、ジャンプ後、デバッグと保守性の両方の面であらゆる種類の問題を引き起こす原因はわかりません-より正式な意味で<!> quot;正確性<!> quot;コードの。もちろん、コードに構造を課す時点でオプションがない言語があります(私はしばらく前から)。結論としては、gotoの使用方法(および悪用)ほどGOTOが悪いわけではないということです。
コード生成を使用してから結果を評価するのは賢い方法です:)ただし、<!> quot; clever <!> quot;必ずしも良いことではなく、それを解決策として使用することの問題の一部は、意図したとおりに問題に実際に対処していないことだと思います。 <!> quot;不正行為<!> quot;ある意味で-少なくともあなたの教授に関する限りでは-ソリューションを無効にしませんが、<!> quot; inelegant <!> quot;にすることができます。デバッグと保守の問題は、コードに関しても発生します。
再帰解-特に、25年前にループに再帰を解くことができると教えられたことを漠然と覚えているように、おそらく最もエレガントでしょう。
間違いなく興味深い質問です!
他のヒント
GOTOとコード生成はどちらも、この問題IMOに対する洗練されたソリューションではありません。おそらくここに正しい答えである再帰アルゴリズムがあります。
あなたのコードを見ることなく、私は教授を支持する傾向があります。 GoToと動的コードのどちらかを選択する場合は、前者に頼ります。 GoToは常に悪い選択ではありません。
GoToを使用しなくても、ほとんどすべての問題を解決できます。具体的には、ループを使用すると、breakおよびcontinueステートメントを使用して、コード標準を維持したままgotoを暗黙的に使用できます。
n ネストされたループは悪い計画のように聞こえます。代わりに再帰関数を調べることをお勧めします。 nループを実行する必要があるたびに、常に再帰を考える必要があります。
動的コードはコンパイル時にチェック可能ではないため、エラーは実行時まで検出されません。見つけにくくする可能性があります。 Rubyの場合、これは、使用しているIDEまたはエディターのどちらでも構文エラーが検出されないことを意味します。これはgotoを選択するのにプラスです。
この場合、両方を見て決定を下す必要があると思います。私はコードを見ていませんが、動的コードまたはgotoを使用しない優れたソリューションがあると確信しています。 gotoは必ずしも悪いわけではありませんが、使用することを考えている場合は、現時点までに最適な設計上の決定を下しておらず、おそらくソリューションを再検討する必要があります。
大学での割り当ての1つで、私はかつて比較的似たようなことをしなければなりませんでした 私の解決策は、再帰関数を使用して、配列、配列のサイズ、ネストレベルを引数として渡すことでした。関数は、ネストレベルが配列のサイズに等しくなるまで、ネストレベル+1でそれ自体を呼び出します。後藤、コード評価なし、クリーンなコードのみ!
例
function computeDerangement(yourArray, loopLevel, arraySize)
{
//We check to see if the loop level is the same as the array size
//if true, then we have executed exactly n loop
if (loopLevel == arraySize) {
display(yourArray); //Display being some kind of function that show the array,
//you get the idea
} else {
while(something) {
//Here you put the logic that you execute at one level of the loop
//Then you call yourself with one more level of nesting
computeDerangement(yourArray, loopLevel + 1, arraySize);
}
}
}
ご協力ください!
gotoを使用したことがないため、gotoを回避する方法は常にあると確信しています
gotoステートメントを避ける主な理由は、プログラムを理解しにくくする可能性があるためです。
コードを見なくても、gotoを使用する同等のプログラムよりも理解するのは難しいと思います...
GOTOソリューション-関数呼び出しをシミュレートする場合、gotoは便利です。以下は、スタックとgotoラベルを使用して再帰的なソリューションを単純にシミュレートし、関数呼び出しが発生した時点に戻る非再帰的ソリューションです。
比較のために、再帰的な手順(これを別の回答として投稿しています)を参照してください。
オプションの厳密オン オプションの明示的オン
モジュールModule1 Dim x As Stack
Private Sub printGeneratedList(ByVal generatedList As List(Of Integer))
For Each el In generatedList
Console.Write(el & " ")
Next
Console.WriteLine()
End Sub
Private Sub generateAux(ByVal i As Integer, ByVal n As Integer, _
ByVal generatedList As List(Of Integer))
Dim stackI As Stack(Of Integer) = New Stack(Of Integer)
Dim stackJ As Stack(Of Integer) = New Stack(Of Integer)
Dim j As Integer
StartLabel:
j = 0
If i >= n Then
printGeneratedList(generatedList)
If stackI.Count = 0 Then
Return
Else
GoTo ReturnLabel
End If
End If
While j < n
If Not j = i Then
If Not generatedList.Contains(j) Then
generatedList.Add(j)
stackI.Push(i)
stackJ.Push(j)
i = i + 1
GoTo StartLabel
ReturnLabel:
i = stackI.Pop()
j = stackJ.Pop()
generatedList.Remove(j)
End If
End If
j = j + 1
End While
If stackI.Count = 0 Then
Return
Else
GoTo ReturnLabel
End If
End Sub
Private Sub generate(ByVal n As Integer)
Console.WriteLine("Generating for n = " & n.ToString())
Dim l As List(Of Integer) = New List(Of Integer)
If n < 0 Then
Throw New Exception("n must be >= 0")
End If
generateAux(0, n, l)
End Sub
Sub Main()
generate(0)
Console.ReadLine()
generate(1)
Console.ReadLine()
generate(2)
Console.ReadLine()
generate(3)
Console.ReadLine()
generate(4)
Console.ReadLine()
End Sub
モジュールの終了
gotoはクリーンではありません。ただし、高いパフォーマンスが必要な場合は、これらのコーディング規則のいくつかを破る必要がある場合があります...
速度が本当に重要な場合、たとえば、非常に重要なライブラリやコードを書きたい場合は、gotoの使用を検討してください。すべてがうまくいくことに注意を払う必要があります。
コメント:最後に、実行中のCPUは単純なジャンプ以外は何もしません。プログラミング言語/コンパイラがそれらを作成するだけです。注意して使用し、混乱させないでください。
gotoソリューションと動的コード生成のアイデアはどちらも悪いです。他の人が述べたように、これは再帰的な解決策で簡単に解決できます。単純にすべての順列を再帰的に生成し(標準の再帰的ソリューション)、生成が完了すると(つまり、再帰のリーフで)、混乱していない順列を返すことをスキップします。
再帰的ソリューション-早期のプルーニングを使用したソリューションを次に示します。私の唯一の質問は列挙に関することです。彼は、呼び出しが成功するたびにリスト内の次の項目を生成する列挙子を作成してほしいと考えましたか?これはおそらく、このプログラムのラムダバージョンを作成することで最も簡単に実装できます。プロローグインタープリタースタイルのクエリを実行するときに質問に対する次の回答を生成するクエリジェネレータを作成するときは、常にLispでこれを実行していました。
オプションの厳密オン オプションの明示的オン
モジュールModule1
Private Sub printGeneratedList(ByVal generatedList As List(Of Integer))
For Each el In generatedList
Console.Write(el & " ")
Next
Console.WriteLine()
End Sub
Private Sub generateAux(ByVal i As Integer, ByVal n As Integer, _
ByVal generatedList As List(Of Integer))
If i >= n Then
printGeneratedList(generatedList)
Return
End If
For j As Integer = 0 To n - 1
If Not j = i Then
If Not generatedList.Contains(j) Then
generatedList.Add(j)
generateAux(i + 1, n, generatedList)
generatedList.Remove(j)
End If
End If
Next
End Sub
Private Sub generate(ByVal n As Integer)
Console.WriteLine("Generating for n = " & n.ToString())
Dim l As List(Of Integer) = New List(Of Integer)
If n < 0 Then
Throw New Exception("n must be >= 0")
End If
generateAux(0, n, l)
End Sub
Sub Main()
generate(0)
Console.ReadLine()
generate(1)
Console.ReadLine()
generate(2)
Console.ReadLine()
generate(3)
Console.ReadLine()
generate(4)
Console.ReadLine()
End Sub
モジュールの終了