难道我只是证明埃拉托色尼那筛比审判庭效率较低？ [英] Did I just prove that sieve of Eratosthenes is less efficient than trial division?

问题描述

我试图来比较两种算法的运行时速度：蛮力C程序打印质数（10,000号），并筛埃拉托色尼的C程序（也万素数）

I was trying to compare the run-time speed of two algorithms: A brute-force C program to print prime numbers (10,000 numbers), and a Sieve of Eratosthenes C program (also 10,000 prime numbers).

我测量的运行时间筛的算法是：0.744秒

My measured run-time for the sieve algorithm was: 0.744 seconds

我测量的运行时间蛮力算法是：0.262秒

My measured run-time for the brute-force algorithm was: 0.262 seconds

不过，我被告知，筛埃拉托色尼的算法比穷举法更有效率，所以我认为它会跑的更快的。所以，无论是我错了，还是我的程序是有缺陷的（我怀疑）。

However, I was told that the Sieve of Eratosthenes algorithm is more efficient than the brute-force method, and so I thought it would run faster. So either I'm wrong or my program is flawed (which I doubt).

所以，我的问题是：自从我得到了相反的结果比我预期的，这是否证明了埃拉托色尼的筛还真是的少的有效算法在速度方面，相比到审判庭？

Therefore, my question is: Since I got the opposite results than what I expected, does this prove that the Sieve of Eratosthenes really is the less efficient algorithm in terms of speed, compared to the trial division?

我不知道这是什么关联，但我使用的是开发的C ++编译器和Windows 7。

I'm not sure if it is of any relevance, but I'm using the Dev C++ compiler and Windows 7.

推荐答案

TL; DR：的比较code的速度变的只是一个输入大小毫无意义的;比较的增长的实证订单的真正体现的算法的的code性质，会在不同的测试平台一致的，输入的尺寸相同的测试范围。比较绝对速度值是唯一有意义的表现出相同的渐近或至少局部生长行为code变种。

TL;DR: comparing the speed of code variants at just one input size is meaningless; comparing empirical orders of growth truly reflects algorithmic nature of the code and will be consistent across different test platforms, for the same test range of input sizes. Comparing absolute speed values is only meaningful for code variants which exhibit same asymptotic or at least local growth behaviour.

这是不够的，衡量你的两个实现的速度只是在一个输入大小。通常几个数据需要点，以评估运行时我们$增长经验订单C $ C（因为code可以与不同的输入尺寸运行）。已发现，作为运行时间的比率的对数，在输入尺寸的比值的基

It is not enough to measure speed of your two implementations just at one input size. Usually several data points are needed, to assess the run time empirical orders of growth of our code (because the code can be run with varying input sizes). It is found as the logarithm of the ratio of run times, in base of the ratio of input sizes.

所以，即使在某些输入 code_1 的运行速度比 code_2 10 的时间code>，但是其运行时的双打的与输入规模每增加一倍，而对于 code_2 只成长，如 1.1倍的，很快 code_2 将变得更加显着快于 code_1 。

So even if at some input code_1 runs 10 times faster than code_2, but its run time doubles with each doubling of the input size, whereas for code_2 it only grows as 1.1x, very soon code_2 will become much much faster than code_1.

所以的算法效率的真正衡量尺度是它运行时间复杂度（和复杂性它即内存需求空间）。而当我们经验衡量，我们只衡量是否为特定的code在眼前（输入大小的一个特定的范围内），而不是为的算法的本身，即理想的实现它。

So the real measure of an algorithm's efficiency is its run time complexity (and the complexity of its space i.e. memory requirements). And when we measure it empirically, we only measure if for the particular code at hand (at a particular range of input sizes), not for the algorithm itself, i.e. the ideal implementation of it.

在特别审判庭的理论复杂度为O（n ^ 1.5 /（log n）的^ 0.5）中的 N 的素数生产的，通常被视为〜N ^ 1.40..1.45 增长的实证顺序（但它可以是〜N ^ 1.3 最初，对于较小的输入尺寸）。对于埃拉托色尼的筛是 O（N日志的n log（日志N）），通常被视为〜N ^ 1.1..1.2 。但是，当然有两个审判庭和埃拉托色尼的，在运行筛〜N ^ 2.0 更糟糕的次优的实现。

In particular, the theoretical complexity of trial division is O(n^1.5 / (log n)^0.5), in n primes produced, usually seen as ~ n^1.40..1.45 empirical order of growth (but it can be ~n^1.3 initially, for smaller input sizes). For the sieve of Eratosthenes it is O(n log n log (log n)), seen usually as ~ n^1.1..1.2. But there certainly are sub-optimal implementations of both the trial division and the sieve of Eratosthenes that run at ~n^2.0 and worse.

所以的没有的，这证明什么。一个数据点是没有意义的，至少有三个的都需要得到一个大局，即要能的 predict 的一些确定性的运行时间和frasl;需要空间更大的投入规模。

So no, this proves nothing. One datapoint is meaningless, at least three are needed to get a "big picture" i.e. to be able to predict with some certainty the run time ⁄ space needed for bigger input sizes.

prediction 的已知的确定的是什么的的科学方法的是一回事。

Prediction with known certainty is what the scientific method is all about.

BTW你的运行时间很长。 10000素数的计算应该是几乎瞬时的，远远小于1 /百分之一秒为在快速中运行一个C程序。也许你测量打印时间也是如此。别。 ：）

BTW your run times are very long. The calculation of 10,000 primes should be nearly instantaneous, much less than 1/100th of a second for a C program run on a fast box. Perhaps you're measuring printing time as well. Don't. :)

这篇关于难道我只是证明埃拉托色尼那筛比审判庭效率较低？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！