2011-01-23 7 views
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のメソッドを実装し、最速のコードを持つ人はボーナスマークの一握りを取得します。

問題は多少単純である必要があるという問題です。学生はを十分に把握してい:、ループの場合/他、ストリングス、追加、配列など

ここ

は、質問は何ができるかについての私の考えです:

  • が1の間のすべての完全数を見つけます1,000,000人。
  • 私が順番に考える1および1,000,000

間のすべての素数を見つける:(。+ 1 + 2 = 3 6完全数はすべての数の要因が数まで追加すなわち数です)メソッド間でパフォーマンスに測定可能な差があるためには、何度も何度もやらなければなりません。

+0

この質問は、http://programmers.stackexchange.comの方が適切でしょうか? – user85461

+2

私はこの権利を読んでいますか?あなたはコースを教えているし、 "あなたは何か何度も何かをやらなければならない方法の間に、パフォーマンスの測定可能な違いがあると思う"と尋ねています。 –

+0

受け入れ可能なものについて厳格なガイドラインとパラメーターを指定するように注意する必要があります。私は完璧な素数のリストをハードコードして、それを印刷させます。コードはそれを打ち負かしません。間違いなく、私はボーナスポイントを獲得すべきではありません(私はクラスでは違うと主張したいと思いますが、いずれにせよ、誰かが試してみる前に*対処する必要があるものです)。 –

答えて

1

これは入門クラスであり、学生がソートをカバーしていないため、私はそれができるほど簡単なものを考え出すのは非常に難しいと思っています。近代的なコンピュータ上の異なる実装間には、速度においてかなりの差があるほど複雑である。実際の問題は、試してみるだけの単純なものであれば、短いGoogle検索で正式な実装を済ませていることです。

私の提案は、チャレンジを逆転させることです。あなたの生徒たちが、彼らが考えることができるもっともまばゆい、最も遅く、最も記憶力のあるホッギング・ソリューションを作り上げるように競争させます。私は、正しいことを考えているように何かをするという間違ったやり方について考えるのは教育的に価値があると信じており、それが最善であるように最悪になるのは難しいことです。悪いコードはとなるので、結果は主観的に見るのが簡単です。実際はです。回答もグーグルではありません。最後に、私の(無関係な)意見では、これは挑戦を楽しくするという追加のボーナスを持っています。

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

+0

興味深い問題に取り組んでください。受け入れられた答えとして選択する。 – sixtyfootersdude

0

これは良い考えです。並べ替えの質問はどうですか?

+0

ソートは良いアイデアですが、まだ並べ替えをカバーしていないので、あまりにも大きな質問を開くことは望ましくありません。並べ替えのための – sixtyfootersdude

0

数値の配列を並べ替えることは、すべてが異なるパフォーマンス特性を持つアルゴリズム(挿入、選択、クイック、ヒープなど)がたくさんあるので、良い考えかもしれません。これはまた、学生にビッグオーモ表記などを学ぶ機会を与えるでしょう。

+0

、あなたはCollections.sort()の使用をあまりにも簡単に禁止しますか? –

+0

@Scott W-ええ、あなたはおそらくそれをしなければならないでしょう。それはちょうど不正行為です。 :-) – templatetypedef

7

短い操作では「何度も」合意しましたが、長い操作では1回で十分です。

私はProject Euler、プログラミングの質問の優れたコレクションを検討することをお勧めします。最も重要な点は、ほとんどの問題は効率的なアルゴリズムを実行して回答を見つけるのに1分未満の中程度のコンピュータが必要であるという「1分ルール」を考慮して問題が設計されていることです。それで始めるには素晴らしい場所です。 :)

4

2つのもの。

第1に、効率は実行時間以上です。また、メモリ使用量、メモリアクセス、ファイルシステム/リソースへのアクセスなどもあります。効率化のためにたくさんのことがあります。だから、最短の実行時間でルーチンを探していることを明示してください。そうしないとあなたが混在メッセージを送っている...

第二に、私は約15年前にこの問題を聞いて、私はそれを忘れることはできません。

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

+0

効率についての良い点は時間以上です。私はこれを知っていますが、私は質問を提示するときにそれについて明示するように注意します。 – sixtyfootersdude

関連する問題