5

我每周做一次计算机科学入门实验室。我希望在下一个实验室结束时能有一场快速的比赛。我想给他们这样的代码块：

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

同意“多次”进行短期操作，但对于较长时间的操作，一次可能就足够了。

我建议研究Project Euler，这是一个很好的编程问题集合。最好的部分是设计问题时考虑了“一分钟规则”，即大多数问题应该花费一台中等计算机不到一分钟的时间来执行一个有效的算法来找到答案。所以一个很好的起点。:)

于 2011-01-23T02:18:19.827 回答
4

两件事情。

首先，效率不仅仅是执行时间。它还与内存使用、内存访问、文件系统/资源访问等有关。有很多事情会影响效率。所以请明确表示您正在寻找运行时间最短的例程。否则，您将发送混合消息...

二、大约15年前听说过这个问题，至今难忘：

生成总和为 的所有 5 位数字对的列表121212。但是，这两个数字中的任何一个都不能重复十进制数字。所以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

对一组数字进行排序也可能是一个好主意，因为它有一大堆算法（插入、选择、快速、堆等），它们都有不同的性能特征。这也将使学生有机会学习大 O 符号等。

于 2011-01-23T02:17:37.027 回答