估算程序运行时间的算法

我需要找到通过不同输入执行程序的总时间。该程序读取一些数据并将其写入另一个文件。数据值和数据大小每次都不相同。估算程序运行时间的算法

我想知道一般情况下需要多长时间才能处理所有大小的数据。

算法是根据单个执行程序的总计时来找到它的算法吗？

例如，如果我知道

for single execution 
a.program - execution time 1.2sec 
      - its create file 100 kb file

我能知道它需要多长时间n个执行，在不同的数据量？

来源

2009-07-07 joe

我不太明白你的问题，但我相信你要问的是如何在运行程序之前弄清楚程序的执行时间。

这与halting problem有关。停止问题是棘手的。

道歉，如果我误解你的问题。

编辑：为了回应您的说明，extrapolating运行时没有通用运算法则，用于较小输入的运行时较大输入。 Analysis of algorithms是非常棘手的业务。有启发式，你可以使用。例如，您可以计算不同“大小”（例如10,100,1000,10000）的输入的运行时间，并尝试将函数“size” - > runtime的曲线拟合。

来源

2009-07-07 14:51:37 jason

@ onebyone.livejournal.com当算法没有线性增长（即O（n））时，这也会失败。例如，如果算法是O（n^2），那么对于1,000个项目所花费的时间长度比对于10个项目花费的时间长度要长10,000倍。 – 2009-07-07 16:55:45

1，停机问题是棘手的，即使你有数据和程序，也无法告诉（！在一般情况下！）运行它需要多长时间。 2，停止问题中的'程序'意味着完整的状态，例如你的程序+它处理的数据。

所以这两次棘手:)

来源

2009-07-07 14:55:21 emvy

有这个不完美的算法，这将是充满变数 - 第一次运行可能会很慢，但第二次运行将是自从数据更快磁盘被缓存在内存中。

您可以使用各种输入来测量您的程序，并尝试构建与执行时间相比较的输入大小/复杂度模型，然后使用其结果估计执行时间。

来源

2009-07-07 15:00:19 Michael

如果我正确理解你，你想知道一个过程需要多长时间来执行。

如果是这种情况，那么使用Benchmark模块。

使用此功能，您可以在不同的地点进行计时，并判断程序不同部分的计时。

来源

2009-07-07 15:00:29 Xetius

从这个问题，我不知道你正在试图计算执行时间之前运行此程序，或记录脚本运行所需的时间。如果你试图预先计算，我同意其他答案，说这是不可能的。

如果您想记录执行时间，只需将2个全局日期变量添加到您的程序中，在执行开始时立即将当前日期和时间存储在一个中，然后在终止时将时间存储在第二个变量中。使用日期差异功能为您提供秒数（或所需的时间单位）。

来源

2009-07-07 15:00:38

确实很难知道，但我不认为这是暂停问题的一个版本。（或者至少，它可以被简化，所以它不是）。

我想，你只是要求估计值关于一系列读写操作需要多长时间......但读写量不同。

最简单的方法是做一些经验测量（越多越好），并使用这些测量来估计未来运行需要多长时间。如果您发现读取10 MB数据需要10秒钟，那么您可以估计100 MB可能需要大约100秒。（当然，这是假设你正在看一个O（n）算法......如果没有，你将不得不相应地进行调整。）

当然，这样会容易出错，因为系统上正在发生的其他事情......但是，根据你的需要，它可能会给你足够好的估计。

当然，如果您可以在阅读/写作时更新估算值，则可以改进它们。

来源

2009-07-07 15:03:44 Beska

如果知道算法的渐近运行时间，例如，知道排序算法是n * log（n），那么可以在小输入上运行它并计算（尽管可能只有一个范围）它将是什么更大的投入。问题在于分析大多数算法非常困难。否则，您可以在较小的输入上运行几次，并执行某种类型的regression（可能是非线性的）来发现/近似算法的性能特征的等式，并使用该等式计算较大的输入。

来源

2009-07-07 15:04:20

如果您在询问实际的解决方案，然后使用Benchmark模块或其他记录时间的过程。然后根据大量输入的输入大小绘制执行时间并插值（但要小心外推，as this xkcd cartoon demonstrates）。

如果你想了解理论，你需要了解“computational complexity”这是一个很好的搜索条件，让你开始。

例如，如果您运行一次数据，那么通常两倍的数据将花费大约两倍的时间。最好的搜索算法通常采用O（NlnN），因此两倍的数据量将会稍多于两倍。但即使这些只会给你时间长度的限制，常量将取决于磁盘访问，内存，其他程序运行等事情。

来源

2009-07-07 15:06:52

你必须知道你的程序是否暂停。它不能自动被需要，但你可以确定你是否知道它的设计。那么你必须知道你的程序至少是渐近复杂的。如果你知道真正的复杂度公式，那就更好。然后，您可以对适当的输入集进行基准测试。然后你可以插入你的数据来实现常量。最后，将常数置于方程式并进行计算。很简单，不是吗？ ;-)

来源

2009-07-07 15:08:01

如果你可以重新执行你的程序。你可以使用unix“time”命令来计时。如果没有，你需要保存系统时间，然后再在程序结束时打印出来？

来源

2009-07-07 15:09:58

有一个计算机科学专门为此的整个分支：Algorithmic Complexity。简而言之，您将分析代码以确定其具有的性能特征，例如，大多数良好的排序算法的平均运行时间为O(n log n)，其中n是要排序的数组的大小。这意味着对100项目进行排序的时间长度为100 * ln 100/ln 2 * x或664x，其中x是运行一条指令所需的时间量。

来源

2009-07-07 16:51:55

估算程序运行时间的算法

回答

相关问题