テスト効率(特に時間に関連する効率性)をテストするための良いボーナスクイズを探しています[閉じた
-
23-10-2019 - |
質問
私は週に一度、コンピューターサイエンスラボへの紹介をしています。私は次のラボの終わりに簡単なコンテストをしたいと思っていました。私は彼らにこのようなコードのブロックを与えたいです:
public class EfficientCode{
public static void main(){
long startTime, endTime, executionTime;
startTime = System.currentTimeMillis();
yourEfficientMethod():
endTime = System.currentTimeMillis();
executionTime = endTime – startTime;
}
public static void doSomething(){
// you do this part.
}
}
彼らはDosomThe Methodを実装し、最速のコードを持つ人は少数のボーナスマークを取得します。
問題は、質問がやや単純である必要があることです。生徒は、ループ、/else、文字列、追加、配列などをよく把握しています。
質問が何であるかについての私のアイデアは次のとおりです。
- 1〜1,000,000のすべての完璧な数字を見つけます。 (完全な数字とは、すべての数値の要因が数値に合計される数字です。つまり、6 = 3 + 2 + 1)
- 1〜1,000,000のすべての素数を見つけます
メソッド間のパフォーマンスに測定可能な違いがあるためには、何度も何かをしなければならないと思います。
解決
これは紹介クラスであり、生徒はまだソートをカバーしていないので、私はそれが十分に簡単なこと、それを行うのに十分な面白いこと、そしてそこに十分な複雑なことを考え出すのが非常に難しいと思います最新のコンピューター上のさまざまな実装間の速度のかなりの違いです。しかし、あなたの本当の問題は、彼らが試してみるのに十分な単純なものは、すでに標準的な実装を持っていることは、短いGoogle検索だけを離れているということです。
私の提案は、挑戦を反転させることです。生徒に競争して、考えられる最もゆっくりとした、最も遅い、ほとんどのメモリホギングソリューションを思いつくようにします。私は、正しいことを考えるのと同じように、何かをするためのすべての間違った方法について考えることは教育的に価値があると信じています。悪いコードはそうなるので、主観的に結果を見るのも簡単です 本当 スロー。回答のためのグーグルはありません。最後に、私の(無関係な)意見では、これは挑戦をより楽しくするという追加のボーナスを持っています。
別の文字列内で文字列を見つけるようなものは、良いものよりも悪くなりやすいです。たぶん、ランダムな英数字の2kbストリングからすべての素数を抽出してもらうかもしれません。その問題の豚の耳を作る多くの方法。
他のヒント
短い操作では「多くの回数」について同意しましたが、より長い操作では、一度だけで十分かもしれません。
調べることをお勧めします プロジェクトオイラー, 、プログラミングの質問の優れたコレクション。最良の部分は、問題が「1分間のルール」を念頭に置いて設計されていることです。ほとんどの問題は、1分未満の中程度のコンピューターを実行するのに1分未満で実行する必要があることです。 効率的 回答を見つけるアルゴリズム。だから、始めるのに最適な場所です。 :)
2つのこと。
まず、効率は実行時間以上のものです。また、メモリの使用、メモリアクセス、ファイルシステム/リソースアクセスなどについてもあります。効率が高まるものがたくさんあります。したがって、最短の実行時間でルーチンを探していることを明確にしてください。それ以外の場合は、混合メッセージを送信しています...
第二に、私は約15年前にこの問題を聞きました、そして私はそれを忘れることはできません:
合計するすべての5桁の数字ペアのリストを作成します 121212
. 。ただし、2つの数値のいずれも小数桁を繰り返すことはできません。そう 1
いずれかの数字で1回しか表示できません。したがって、結果の例はそうです 98167 + 23045
. 。かなりの数があり、ブルートフォースソリューションを構築するのは簡単ですが、効率的なソリューションにはある程度の考えが必要です。 192のユニークなペアがあります...
それらは良いアイデアです。ソートの質問があるのはどうですか?
数字の配列をソートすることも良い考えかもしれません。なぜなら、すべてが異なるパフォーマンス特性を持つアルゴリズム(挿入、選択、クイック、ヒープなど)がたくさんあるからです。また、これにより、学生はBig-O Notationなどについて学ぶ機会を与えます。