草庐IT

Java 选择递归函数

coder 2024-03-17 原文

我这里有两个不同的递归函数，用于在 Java 中反转字符串:

    Long ms1 = System.currentTimeMillis();
    String str1 = reverse1(str);
    ms1 = System.currentTimeMillis() - ms1;

    Long ms2 = System.currentTimeMillis();
    String str2 = reverse2(str);
    ms2 = System.currentTimeMillis() - ms2;

    System.out.println("Input: " + str);
    System.out.println("  Length: " + str.length());
    System.out.println("Reverse 1:");
    System.out.println("  " + herp + " function calls");
    System.out.println("  " + ms1 +  " milliseconds");
    System.out.println("Reverse 2:");
    System.out.println("  " + derp + " function calls");
    System.out.println("  " + ms2 +  " milliseconds");
}
public static String reverse1(String str){
    herp++;
    if(str.length() == 1) return str;
    return reverse1(str.substring(str.length()/2)) + reverse1(str.substring(0, str.length()/2));
}
public static String reverse2(String str){
    derp++;
    if(str.length() == 1) return str;
    return reverse2(str.substring(1)) + str.charAt(0);
}

给定一个长度为 5000 的字符串，这是程序的输出:

Input: ...
  Length: 5000
Reverse 1:
  9999 function calls
  16 milliseconds
Reverse 2:
  5000 function calls
  52 milliseconds

现在为什么函数调用速度翻倍了~3 倍？我应该如何构建我的递归函数以在 Java 中实现最大速度？

最佳答案

这是一个很好的旧算法分析问题。您的 reverse1 应该在 O(n logn) 时间内运行，而 reverse2 需要 O(n²) 时间，因此要反转的字符串越长，速度越快 reverse2 将是 reverse1。

资源使用率不是由调用次数决定的，而是由将字符复制到在每次字符串连接操作时创建的新 String 对象中花费的时间决定的。 reverse2 中的字符串连接平均比reverse1 中的字符串连接更长的字符串，因此它的总执行时间更长。

  • 在 reverse1 中，每个字符被复制 log2(n) 次(其中 n 是原始字符串的长度)，因为递归调用树的深度约为 log2(n ).

  • 在 reverse2 中，每个字符被复制的次数等于它在原始字符串中的位置(±1，我不关心)。这使得每个字符平均有 n/2 个副本。

对于大 n，log2(n) 远小于 n/2，因此 reverse1 往往更快。

关于Java 选择递归函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13255041/

Java选择reversecodeSystemstringrecursion

有关Java 选择递归函数的更多相关文章

  1. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  2. 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/

  3. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  4. ruby - 在 Ruby 中有条件地定义函数 - 2

    我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

  5. 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

  6. ruby - Rails 3 的 RGB 颜色选择器 - 2

    状态:我正在构建一个应用程序，其中需要一个可供用户选择颜色的字段，该字段将包含RGB颜色代码字符串。我已经测试了一个看起来很漂亮但效果不佳的。它是“挑剔的颜色”，并托管在此存储库中:https://github.com/Astorsoft/picky-color.在这里我打开一个关于它的一些问题的问题。问题:请建议我在Rails3应用程序中使用一些颜色选择器。 最佳答案 也许页面上的列表jQueryUIDevelopment:ColorPicker为您提供开箱即用的产品。原因是jQuery现在包含在Rails3应用程序中，因此使用基

  7. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  8. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  9. ruby - 在 Ruby 中按名称传递函数 - 2

    如何在Ruby中按名称传递函数？(我使用Ruby才几个小时，所以我还在想办法。)nums=[1,2,3,4]#Thisworks,butismoreverbosethanI'dlikenums.eachdo|i|putsiend#InJS,Icouldjustdosomethinglike:#nums.forEach(console.log)#InF#,itwouldbesomethinglike:#List.iternums(printf"%A")#InRuby,IwishIcoulddosomethinglike:nums.eachputs在Ruby中能不能做到类似的简洁？我可以只

  10. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

随机推荐