5

週に 1 回、コンピュータ サイエンス入門のラボを行っています。次のラボの終わりに簡単なコンテストを開催したいと思っていました。次のようなコードのブロックを提供したいと思います。

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.  
    }

}

彼らはdoSomethingメソッドを実装し、最速のコードを持つ人は一握りのボーナスマークを獲得します.

問題は、質問がやや単純である必要があることです。学生は、ループ、if/else、文字列、追加、配列などをよく理解しています。

質問が何であるかについての私の考えは次のとおりです。

  • 1 から 1,000,000 までの完全数をすべて見つけてください。(完全数とは、数のすべての因数を合計するとその数になる数です。つまり、6 = 3 + 2 + 1)
  • 1 から 1,000,000 までのすべての素数を見つける

メソッド間のパフォーマンスに測定可能な違いがあるためには、何かを何度も行う必要があると思います。

4

5 に答える 5

7

短い操作の場合は「何度も」で合意しましたが、長い操作の場合は 1 回で十分かもしれません。

プログラミングに関する質問の優れたコレクションであるProject Eulerを調べることをお勧めします。最良の部分は、問題が「1 分ルール」を念頭に置いて設計されていることです。ほとんどの問題は、答えを見つけるための効率的なアルゴリズムを実行するのに、適度なコンピューターで 1 分もかからないはずです。ですから、始めるのに最適な場所です。:)

于 2011-01-23T02:18:19.827 に答える
4

2つのこと。

まず、効率は実行時間以上のものです。また、メモリ使用量、メモリ アクセス、ファイル システム/リソース アクセスなどについても言及されています。効率化につながる要素はたくさんあります。したがって、実行時間が最短のルーチンを探していることを明示してください。それ以外の場合は、混合メッセージを送信しています...

第二に、私は約 15 年前にこの問題を聞いたことがありますが、忘れることはできません。

合計が になるすべての 5 桁の数字のペアのリストを作成し121212ます。ただし、2 つの数字のどちらも 10 進数を繰り返すことはできません。したがって1、どちらの番号にも 1 回しか表示できません。したがって、結果ペアの例は98167 + 23045です。かなりの数があり、ブルート フォース ソリューションを構築するのは簡単ですが、効率的なソリューションを作成するには、ある程度の検討が必要です。192 のユニークなペアがあります...

于 2011-01-23T02:28:59.657 に答える
1

これは入門クラスであり、生徒はまだ並べ替えについて説明していません。簡単な方法、いくつかの異なる方法を使用できる興味深い方法、複雑な方法を考え出すのは非常に難しいと思います。は、最新のコンピューターのさまざまな実装間の速度のかなりの違いです。しかし、あなたの本当の問題は、彼らが試すのに十分単純なものは、Googleで検索するだけで標準的な実装がすでにあるということです。

私の提案は、挑戦を逆転させることです。生徒たちに、考えられる最も恐ろしく、最も遅く、最も記憶を奪う解決策を考え出すために競争させます。私は、正しいことを考えるのと同じように、何かをするためのすべての間違った方法を考えることは教育的に価値があると信じています。悪いコードは本当に遅いので、主観的にも結果を見るのは簡単です。答えをグーグルすることもありません。最後に、私の（無関係な）意見では、これにはチャレンジをより楽しくするという追加のボーナスがあります。

別の文字列内で文字列を見つけるようなものは、良いよりも悪い方が簡単です。たぶん、ランダムな英数字の2kbの文字列からすべての素数を抽出してもらいます。その問題の豚耳を作る方法はたくさんあります。

于 2011-01-28T18:50:42.537 に答える
0

それらは良いアイデアです。並べ替えの質問はどうですか？

于 2011-01-23T02:17:01.767 に答える
0

数値の配列をソートすることも良い考えかもしれません。これには、さまざまなパフォーマンス特性を持つ多数のアルゴリズム (挿入、選択、クイック、ヒープなど) があるためです。これにより、学生は Big-O 記法などについて学ぶ機会にもなります。

于 2011-01-23T02:17:37.027 に答える