草庐IT

java - 估计实现的实际(非理论)运行时复杂性

coder 2024-03-08 原文

计算机科学的任何人都知道 HeapSort 在理论上是 O(n log n) 最坏情况，而 QuickSort 是 O(n^2) 最坏情况。然而，在实践中，一个良好实现的 QuickSort(具有良好的启发式)将在每个数据集上优于 HeapSort。一方面，我们几乎观察不到最坏的情况，另一方面，例如CPU 缓存行、预取等在许多简单任务中产生巨大差异。而例如QuickSort 可以在 O(n) 中处理预排序数据(具有良好的启发式)，HeapSort 将始终在 O(n log n) 中重新组织数据，因为它不会利用现有结构。

对于我的玩具项目 caliper-analyze ，我最近一直在研究根据基准测试结果估算算法的实际平均复杂度的方法。特别是，我尝试了使用不同多项式拟合 Lawson 和 Hanson 的 NNLS。

但是，它还不太好用。有时我会得到有用的结果，有时我不会。我认为做更大的基准测试可能会有所帮助，尤其是尝试更多参数。

以下结果用于对 Double 对象进行排序，采用具有 10% 随机性的 SAW 模式。这次运行的 n 最多只有 500，因此对于实际使用来说并不是很有代表性……这些数字是估计的运行时对大小的依赖性。输出是手动编辑和手动排序，因此它不反射(reflect)工具当前提供的内容!

BubbleSortTextbook       LINEAR: 67.59  NLOG2N:  1.89  QUADRATIC: 2.51
BubbleSort               LINEAR: 54.84                 QUADRATIC: 1.68
BidirectionalBubbleSort  LINEAR: 52.20                 QUADRATIC: 1.36
InsertionSort            LINEAR: 17.13  NLOG2N:  2.97  QUADRATIC: 0.86
QuickSortTextbook                       NLOG2N: 18.15
QuickSortBo3             LINEAR: 59.74                 QUADRATIC: 0.12
Java                     LINEAR:  6.81  NLOG2N: 12.33
DualPivotQuickSortBo5                   NLOG2N: 11.28
QuickSortBo5             LINEAR:  3.35  NLOG2N:  9.67

您可以看出，虽然在此特定设置中(通常它根本无法令人满意)，但结果在很大程度上与已知行为一致:冒泡排序的成本确实很高，而 QuickSort 上的良好启发式算法要好得多。然而，例如例如，具有三中值启发式的快速排序以 O(n + n^2) 估计结束，而其他 QuickSort 的估计为 O(n + n log n)

现在回答我的实际问题:

  • 您是否知道从基准数据执行运行时复杂性分析的算法/方法/工具，以预测哪种实现(正如您在上面看到的，我对比较相同 算法!)在真实数据上表现最佳？
  • 您是否知道与此相关的科学文章(估计实现的平均复杂性)？
  • 您是否知道有助于在此处获得更准确估算值的稳健拟合方法？例如。 NNLS 的正规化版本。
  • 您是否知道需要多少样本才能获得合理估计的经验法则？ (特别是，该工具何时应避免给出任何估计，因为无论如何它都可能不准确？)

让我再次强调，我对理论的复杂性或形式分析不感兴趣。我有兴趣了解实现(理论上什至相同的算法)如何在真实 CPU 上对基准数据执行...我对常见范围的数值因素很感兴趣，更多比渐近行为。 (不，从长远来看，这不仅仅是时间复杂度和排序。但我对索引结构和其他参数感兴趣。卡尺还可以测量内存消耗，如果我没记错的话)另外，我是在 java 中工作。仅调用 Matlab 内置函数的方法对我没有用，因为我不生活在 matlab 世界中。

如果我有时间，我会尝试使用更多的尺寸重新运行其中一些基准测试，以便获得更多的数据点。也许它会起作用......但我相信有更强大的回归方法可以用来获得更好的估计，即使是从较小的数据集中。另外，我想检测样本何时太小而根本无法进行任何预测!

最佳答案

如果你想要实际的复杂性，你最好测量它。在没有测量的情况下试图猜测程序将如何执行是非常不可靠的。

同一个程序在不同机器上的表现可能大相径庭。例如一种算法在一台机器上可能更快，但在另一台机器上可能更慢。

您的程序可能会变慢，具体取决于机器正在做什么，因此看起来不错但大量使用缓存等资源的算法可能会变慢，并且在必须共享这些资源时会使其他程序变慢。

在机器上单独测试算法比尝试在真实程序中使用它快 2-5 倍。

Do you know rules-of-thumb of how many samples one needs to get a reasonable estimate? (in particular, when should the tool refrain from giving any estimate, as it will likely be inaccurate anyway?)

要确定像 90% 或 99% 这样的百分位数，您需要 1/(1-p)^2，即对于 99% 的分位数，您在预热后至少需要 10,000 个样本。对于 99.9% 的瓷砖，您需要一百万。

关于java - 估计实现的实际(非理论)运行时复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17493629/

java估计code的sectioncomplexity-theorybenchmarkingcalipermicrobenchmark

有关java - 估计实现的实际(非理论)运行时复杂性的更多相关文章

  1. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  2. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  3. ruby - 如何每月在 Heroku 运行一次 Scheduler 插件？ - 2

    在选择我想要运行操作的频率时，唯一的选项是“每天”、“每小时”和“每10分钟”。谢谢!我想为我的Rails3.1应用程序运行调度程序。 最佳答案 这不是一个优雅的解决方案，但您可以安排它每天运行，并在实际开始工作之前检查日期是否为当月的第一天。 关于ruby-如何每月在Heroku运行一次Scheduler插件？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/8692687/

  4. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  5. ruby - 无法运行 Rails 2.x 应用程序 - 2

    我尝试运行2.x应用程序。我使用rvm并为此应用程序设置其他版本的ruby​​:$rvmuseree-1.8.7-head我尝试运行服务器，然后出现很多错误:$script/serverNOTE:Gem.source_indexisdeprecated,useSpecification.Itwillberemovedonorafter2011-11-01.Gem.source_indexcalledfrom/Users/serg/rails_projects_terminal/work_proj/spohelp/config/../vendor/rails/railties/lib/r

  6. ruby - Sinatra:运行 rspec 测试时记录噪音 - 2

    Sinatra新手；我正在运行一些rspec测试，但在日志中收到了一堆不需要的噪音。如何消除日志中过多的噪音？我仔细检查了环境是否设置为:test，这意味着记录器级别应设置为WARN而不是DEBUG。spec_helper:require"./app"require"sinatra"require"rspec"require"rack/test"require"database_cleaner"require"factory_girl"set:environment,:testFactoryGirl.definition_file_paths=%w{./factories./test/

  7. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  8. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  9. ruby-on-rails - 无法让 rspec、spork 和调试器正常运行 - 2

    GivenIamadumbprogrammerandIamusingrspecandIamusingsporkandIwanttodebug...mmm...let'ssaaay,aspecforPhone.那么，我应该把“require'ruby-debug'”行放在哪里，以便在phone_spec.rb的特定点停止处理？(我所要求的只是一个大而粗的箭头，即使是一个有挑战性的程序员也能看到:-3)我已经尝试了很多位置，除非我没有正确测试它们，否则会发生一些奇怪的事情:在spec_helper.rb中的以下位置:require'rubygems'require'spork'

  10. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

随机推荐