| 最终修改于 : | 2008年04月09日 13:43 |
评级 |
|
摘自 Clay 于 2008 年 4 月的博客，如果想要参与讨论，请点击这里。
| 问答一： |
| 问题： |
| 我有一个问题，是关于“不可使用其他任何排序算法在归并排序算法的递归过程中制造‘短路’。因为应用程序会在执行过程中的某些时候合并相同大小的列表。”这一限制的。是否可以将归并排序算法（例如，四个元素组成的数组）展开成为线性顺序排列的比较交换运算，并对这些运算进行硬编码？ |
回答： |
|
不可以，按该问题的描述，禁止这样做。 |
| 问答二： |
| 问题： |
| 我有一个关于问题描述的问题。可以对算法做一些改进吗？例如，二分归并排序或多路归并排序。还有，N 的个数为多少？ |
回答： |
| 嗯，我们还没有考虑到这一点。但只要是归并排序算法，尤其是自身趋于并行时，就可以对它做一些改进。一定要将您选择的算法以及在源文件中编码的方法记录下来。 |
|
N 的最大值为 (2^28)-1。但您可以放心的是，这个数据一定适合该测试机的内存。 |
| 问答三： |
| 问题： |
| 由于传统的归并排序会占用数据设定的两倍空间，内存可以存得下所有的数据吗？ |
回答： |
|
可以，内存会为复制的数据备有足够的空间。 |
| 问答四： |
| 问题： |
| Knuth 在 TAOCP 中描述了许多不同的通过合并来排序的方法。例如，在 5.2.4 部分中的算法 S，该算法并没有使用问题描述中提到的堆栈。还有 Batcher 的通过合并交换排序（5.2.2 部分的算法 M）。这些合并排序的算法可用吗？如果可用，可以对它们进行合并吗？ |
回答： |
| 我有 TAOCP 第三册的初版（翻箱倒柜才找到），我们认为算法 S (5.2.4) 是传统的归并排序算法，是可用的。 |
| 算法 M (5.2.2) 也是可用的。考虑到已知例子的数据的比较和运转，我们可以看到正在合并的排序列表（尽管它们并非在同一物理位置上）。 |
摘自 Clay 于 2007 年 12 月 5 日的博客，如果想要参与讨论，请点这里。
让我先来解释一下这个问题集中执行分数与时间分数的计算方法吧。
对于运行的每个数据集，每位参赛选手都将获得一个执行时间排名和一个最终 TD 排名。时间越短，排名越高；TD分数越低，排名也越高。数字越小表示排名越“高”。TD分数的排名将先乘以三（3），然后再加到执行时间的排名上。所有数据集的排名总合将加在一起，最终生成一个净分数（Net Score）。净分数最低的参赛者将获得 100 分，净分数第二低的参赛者将获得 99 分，以此类推。（举例如下）
我们使用乘数的目的是为了更好地进行分组。此举试图避免程序只是简单地读取数据、在同组作品的基础上稍做改动，便输出自己的结果。这种程序可能会实现最低的执行时间，但是也将有可能得到最差的 TD 最终分数。另一方面，虽然用完 120 秒的程序可获得最佳的最终 TD 分数，但他将在执行时间中排名最低。如果第三位参赛选手使用了 50 秒，并获得了一个TD 分数，接近最佳得分（由另一位用满 2 分钟的选手获得），那么我们认为他更应该获得一个很好的最终总分。
我们采用这种计分方法，是为了让所有参赛选手都能思考一下：花费更多时间以求提高最终 TD 分数，以及花费较短时间来获得相近得分（通过线程）之间的利弊权衡。
举例:
| 程序 | 时间排名 | TD 排名 | 净分数 | 总分数 |
| A | 4 | 2 | 10 | 99 |
| B | 1 | 4 | 13 | 98 |
| C | 2 | 5 | 17 | 96 |
| D | 5 | 3 | 14 | 97 |
| E | 3 | 1 | 6 | 100 |
摘自 Clay 于 2007 年 11 月 15 日的博客，如果想要参与讨论，请点这里。
为了尽可能多地为那些希望深入了解评价平台的人们提供更多信息，我们在此提供了一些关于目标处理器及编译器软件的系统和软件信息。遗憾地是，由于恰巧赶上系统（这些系统在我开始撰写本消息前，刚刚断电）迁移前的周末，因此目前我们无法为您提供所有的较小版本号。下面是我们记录的有关系统信息的一个列表。一旦机器恢复运行，我们将获得更多详情，并在这里发布。
（请注意：这些规范会随着硬件或软件的升级而有所更改，届时不会发出警告。）
- 操作系统（OS）版本：Microsoft Windows Server 2003 64 位企业版 Service Pack 2
- Visual Studio 2005 (8.0.x) and .NET Framework 2.0.x
- 英特尔® 编译器 10.0.x （包括 64 位和 32 位两种版本）
- 英特尔® 线程构建模块（2.0 版）
- Sun Java version 6.0
- 处理器应与 Linux 系统上所用系统相同（2.667 GHz、4GB 内存）。
如果您对提交信息所用的编译器有任何特殊要求，请务必明确标注在您的构建说明中。评委将尽全力满足您的要求。
摘自 Clay 于 2007 年 11 月 15 日的博客，如果想要参与讨论，请点这里。
为了向那些希望深入了解评价平台的人们提供更多信息，我们将在下文中列举一些常见查询命令中出现的有关目标处理器及编译器软件的具体规范。（请注意：这些规范会随着硬件或软件的升级而有所更改，届时不会发出警告。）
Linux XXXXX-YY-ZZZZZZ 2.6.9-42.ELsmp #1 SMP Wed Jul 12 23:32:02 EDT 2006 x86_64 x86_64 x86_64 GNU/Linux
[user17 ~]$ g++ -v
Reading specs from /usr/lib/gcc/x86_64-redhat-linux/3.4.6/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --disable-checking --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-java-awt=gtk --host=x86_64-redhat-linux
Thread model: posix
gcc version 3.4.6 20060404 (Red Hat 3.4.6-3)
[user17 ~]$ icc –V
Intel(R) C Compiler for applications running on Intel(R) 64, Version 10.1 Build 20070913 Package ID: l_cc_p_10.1.008 Copyright (C) 1985-2007 Intel Corporation. All rights reserved.
[user17 ~]$ tail -n 24 /proc/cpuinfo
processor : 7
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Genuine Intel(R) CPU @ 2.66GHz
stepping : 5
cpu MHz : 2666.723
cache size : 4096 KB
physical id : 1
siblings : 4
core id : 7
cpu cores : 4
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm syscall lm pni monitor ds_cpl est tm2 cx16 xtpr
bogomips : 5332.64
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:
此外，还提供（至少）32 位版本的英特尔® 编译器。安装的英特尔® 线程构建模块（TBB）为最新的 2.0 版。
如果您对提交信息所用的编译器有任何特殊要求，请务必明确标注在您的构建说明中。评委将尽全力满足您的要求。
