寻找好的奖金测验以测试效率(特别是与时间相关的效率)

Question

我每周都会做一次计算机科学实验室的入门课程.我希望在下一个实验结束时能够快速参加比赛.我想给他们一个像这样的代码块:

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之间的所有素数

我认为,为了在方法之间存在可衡量的性能差异,您必须多次执行某些操作.

Answer 1

同意"很多次"用于短期操作,但对于较长时间的操作,一次可能就足够了.

我建议查看Project Euler,这是一个很好的编程问题集合.最好的部分是问题的设计考虑了"一分钟规则",大多数问题应该花费不到一分钟的中等计算机来执行有效的算法来找到答案.这是一个很好的起点.:)

Answer 2

因为这是一门入门课程，而您的学生还没有涵盖排序，所以我认为很难想出一些足够简单的东西来完成，足够有趣以有几种不同的方法来完成它，并且足够复杂以实现它现代计算机上不同实现之间的速度存在明显差异。然而，你真正的问题是，任何简单到足以让他们尝试的东西都已经有了规范的实现，只需很短的谷歌搜索即可。

我的建议是扭转挑战。让你的学生竞相想出他们能想到的最粗糙、最慢、最占用内存的解决方案。我相信思考所有错误的做事方式与思考正确的做事方式一样具有教育意义，成为最坏的人与成为最好的人一样困难。主观地看到结果也更容易，因为糟糕的代码会非常慢。也没有谷歌搜索答案。最后，在我（无关紧要的）看来，这还有一个额外的好处，那就是让挑战变得更有趣。

像在另一个字符串中查找一个字符串之类的事情，做坏事比做好事更容易。也许让他们从 2kb 的随机字母数字字符字符串中提取所有素数。有很多方法可以解决这个问题。