启发式排序系统的质量评估

Question

我有一个程序，它使用启发式方法将元素排序到几个桶中。

我有另一个程序，它做同样的事情，但精确地计算每个元素应该去哪里。

当我比较这两个结果时，我发现有些元素在正确的位置，而有些则不是。如果我要估计启发式方法的质量，我会怎么做呢？

我是应该用启发式方法将正确放置的元素的数量除以元素的总数，还是有更好的方法？你会怎么做？

Answer 1

http://m.wikihow.com/Calculate-a-Test-Grade

这和给考试打分没什么不同。如果你知道每个水桶的最大“分数”，那么当你与实际的“分数”比较时，你应该能够找到你的“分数”。

Answer 2

什么维度对你的客户来说最重要？

您可以通过将正确放置的元素数除以总元素数来评定精度。如果这是唯一关心的事情，那就这么简单。

您可以通过计时算法完成所需时间来对速度进行分级。您可能需要运行多次并取平均值，因为挂钟运行时随运行时间的不同而不同。如果您的客户只关心速度，这将是您想要的措施。

如果你的客户同时关心速度和准确性，你需要对分数进行加权。速度与准确性相比有多重要？如果它是50/50，你可以给更快的算法一个点和更精确的算法一个点，看看一个明显更好，或他们是否被打成平局。如果一个因素比另一个因素更重要，你会想要适当地衡量分数，也许两个分数的准确性和一个的速度。

如果您关注的是另一个度量，如CPU使用、文件大小或内存使用，则需要对其进行度量，并在最终的加权算法中加以考虑。您可能想要创建一个评分算法，例如accuracy + (speed in seconds)/2 + filesize*10，然后根据最终得分对这两种方法进行排序。同样，这在很大程度上取决于每个因素在总体质量评估中的重要性。