各种算法的样本输入

9
我一直在阅读Cormen等人的《算法导论》的部分内容,并实现了其中的一些算法。
为了测试我的实现,我编写了一些粘合代码来进行文件io,然后手动制作了一些样例输入,并通过编写生成样例输入的程序制作了更多样例输入。
然而,我对自己的样例输入质量表示怀疑 -- 边界情况;我可能错过了更有趣的可能性;我可能计算输出不正确等等。
是否有一个收集各种算法的测试输入和输出的数据集可以在互联网上找到,以便我可以测试我的代码?我正在寻找与特定算法相当特定的测试数据,而不是通常涉及问题解决组件的竞赛问题。
我知道我可能需要根据收集的输入格式调整我的代码(例如,输入的各种限制;对于图形算法,图形的表示方式等),尽管我希望我需要进行的更改是相当简单的。
编辑:
我目前正在寻找一些特定的数据集:
数字列表
倾斜,以便快速排序表现不佳。
倾斜,以便斐波那契堆在特定操作中表现良好或不良。
图(高性能标记提供了许多有趣的参考)
稀疏图(具有特定的边界数限制)。
密集图。
由于我仍在阅读该书,如果您和我处于类似的情况,或者您觉得列表可以改进,请随时编辑该列表 -- 在不久的将来,我可能需要类似于您正在寻找的数据集。我不完全确定编辑特权如何工作,但如果我有任何发言权,我会尝试批准它。

1
你使用的是哪种编程语言?有些语言有可以自动生成测试数据的库,例如Haskell的QuickCheck。更多的库可以在http://news.ycombinator.com/item?id=3020132中找到。 - andrew cooke
@andrewcooke 我正在使用Python。QuickCheck和类似的库听起来很有趣--我一定会去看看的。 - math4tots
2
另一个有趣的测试工具是Korat(详见http://www.stanford.edu/class/cs295/papers/issta02.pdf),它实际上检查您的代码以构建详尽的测试用例,以在小输入上进行测试。虽然不是Python中的测试集合,但仍然是一个很酷的工具需要了解。 - templatetypedef
2个回答

6
我不知道有哪个资源可以为您提供Cormen等人涵盖的所有算法类型的示例输入,但是对于图形数据集,这里有几个参考资料:
- Knuth's Stanford Graphbase - Stanford Large Network Dataset Collection(在查找前者链接时偶然发现的) - 您可能也会对Matrix Market感兴趣
为什么不编辑您的问题并让SO知道您正在寻找哪些其他类型的输入呢?

3
我会添加稀疏矩阵集合。你可以轻松地从稀疏矩阵中获得图形。http://www.cise.ufl.edu/research/sparse/matrices/ - linello

0

我要冒昧地说,我不知道是否有这样的资源存在,而且我非常怀疑是否真的存在这样的资源。

正如你所知,算法可以应用于几乎任何类型的数据,因此提供示例数据是徒劳无功的。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接