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

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，String，添加，数组等等。

以下是我对这个问题的看法：

• 找出1到1,000,000之间的所有完美数字。(十全十美的数字是指该数字的所有因素加在一起的数字。Ie: 6=3+2+ 1)
• 查找1到1,000,000之间的所有素数

我认为，为了使方法之间的性能有可衡量的差异，您必须做很多次的事情。

Answer 1

因为这是一门入门课，你的学生还没有涉及排序，我认为很难想出一些简单的东西来做，有趣到有几种不同的方法，而且复杂到在现代计算机上不同的实现速度之间会有明显的差异。然而，你真正的问题是，任何简单到足以让他们尝试的东西，只要离谷歌搜索很短的时间，就已经有了一个规范的实现。

我的建议是扭转这一挑战。让你的学生想出他们能想到的最粗糙、最慢、最浪费记忆的解决方案。我认为，在教育上，思考所有错误的做事方式，就像思考正确的方法一样，是很有教育价值的，做最坏的人和做最好的人一样困难。主观地看结果也更容易，因为糟糕的代码会非常慢。也不能在谷歌上搜索答案。最后，在我(不相关)的意见，这有额外的好处，使挑战更有趣。

像在另一个字符串中找到一个字符串这样的事情比在另一个字符串中查找字符串容易得多。也许让他们从一个2kb的随机字母数字字符串中提取所有素数。有很多方法可以让猪知道这个问题。

Answer 2

对于短期行动，同意“多次”，但就较长时间而言，单凭一次就足够了。

我建议查看Euler项目，这是一个优秀的编程问题集合。最重要的是，这些问题的设计考虑了“一分钟规则”，大多数问题应该用一台中等的计算机不到一分钟来执行一种有效的算法来找到答案。所以是个很好的开始。:)

Answer 3

两件事。

首先，效率不仅仅是执行时间。它还涉及内存使用、内存访问、文件系统/资源访问等。因此，请明确表示，您正在寻找运行时间最短的例程。否则你会发出混合信息..。

第二，我15年前听过这个问题，我不能忘记：

生成与121212相加的所有5位数字对的列表.然而，这两个数字都不能重复一个十进制数字。因此，1只能在任何数字中出现一次。因此，一个示例结果对是98167 + 23045。有一个公平的数目，这是很容易建立一个蛮力的解决方案，但一个有效的解决方案需要一些思考。有192对独特的..。