草庐IT

java - 新的 BigInteger(String) 性能/复杂性

coder 2023-09-02 原文

我想知道使用 new BigInteger(String) 构造函数构造 BigInteger 对象的性能/复杂性。

考虑以下方法:

  public static void testBigIntegerConstruction()
  {
    for (int exp = 1; exp < 10; exp++)
    {
      StringBuffer bigNumber = new StringBuffer((int) Math.pow(10.0, exp));
      for (int i = 0; i < Math.pow(10.0, exp - 1); i++)
      {
        bigNumber.append("1234567890");
      }

      String val = bigNumber.toString();
      long time = System.currentTimeMillis();
      BigInteger bigOne = new BigInteger(val);
      System.out.println("time for constructing a 10^" + exp
          + " digits BigInteger : " + ((System.currentTimeMillis() - time))
          + " ms");
    }
  }

此方法创建 BigInteger 字符串对象，10^x 个数字，其中 x=1 开始，并且随着每个数字增加迭代。它测量并输出构造相应的 BigInteger 对象所需的时间。

在我的机器上(Intel Core i5 660，JDK 6 Update 25 32 位)输出是:

time for constructing a 10^1 digits BigInteger : 0 ms
time for constructing a 10^2 digits BigInteger : 0 ms
time for constructing a 10^3 digits BigInteger : 0 ms
time for constructing a 10^4 digits BigInteger : 16 ms
time for constructing a 10^5 digits BigInteger : 656 ms
time for constructing a 10^6 digits BigInteger : 59936 ms
time for constructing a 10^7 digits BigInteger : 6227975 ms

虽然忽略了 10^5 行(由于(处理器)缓存效应​​、JIT 编译等可能引入的失真)，我们可以清楚地看到 O(n^2) 的复杂度 这里。 请记住，由于不变性，BigInteger 上的每个操作都会创建一个新操作，这是对大数字的主要性能惩罚。

问题:

  • 我错过了什么吗？

  • 为什么会这样？

  • 这在最近的 JDK 中是否已修复？

  • 还有其他选择吗？

更新:

我做了进一步的测量，我可以从一些答案中证实这个说法:
BigInteger 似乎针对后续的数值运算进行了优化，但代价是大量的构建成本更高这对我来说似乎是合理的。

最佳答案

从 source 简化某种程度上，这是因为在“传统的”字符串解析循环中

for each digit y from left to right:
  x = 10 * x + y

您遇到的问题是，10 * x 的时间不可避免地与 x 的长度呈线性关系，并且该长度会或多或少地增长一个常数因子每一个数字，也是不可避免的。

(实际的实现比这更聪明——它试图一次解析一个 int 的二进制数字，因此循环中的实际乘数更有可能是 1 或20 亿——但是，是的，它总体上仍然是二次方。)

就是说，10^6 位的数字至少是一个 googol，这比我听说过的任何用于加密目的的数字都大。您正在解析一个占用 2 MB 内存 的字符串。是的，这需要一段时间，但我怀疑 JDK 作者没有看到针对这种罕见用例进行优化的意义。

关于java - 新的 BigInteger(String) 性能/复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14757086/

BigIntegerStringcodestrongjavaperformancecomplexity-theory

有关java - 新的 BigInteger(String) 性能/复杂性的更多相关文章

  1. ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

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

  4. ruby - 字符串文字中的转义状态作为 `String#tr` 的参数 - 2

    对于作为String#tr参数的单引号字符串文字中反斜杠的转义状态，我觉得有些神秘。你能解释一下下面三个例子之间的对比吗？我特别不明白第二个。为了避免复杂化，我在这里使用了'd'，在双引号中转义时不会改变含义("\d"="d")。'\\'.tr('\\','x')#=>"x"'\\'.tr('\\d','x')#=>"\\"'\\'.tr('\\\d','x')#=>"x" 最佳答案 在tr中转义tr的第一个参数非常类似于正则表达式中的括号字符分组。您可以在表达式的开头使用^来否定匹配(替换任何不匹配的内容)并使用例如a-f来匹配一

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

  6. ruby - 从 String#split 返回的零长度字符串 - 2

    在Ruby1.9.3(可能还有更早的版本，不确定)中，我试图弄清楚为什么Ruby的String#split方法会给我某些结果。我得到的结果似乎与我的预期相反。这是一个例子:"abcabc".split("b")#=>["a","ca","c"]"abcabc".split("a")#=>["","bc","bc"]"abcabc".split("c")#=>["ab","ab"]在这里，第一个示例返回的正是我所期望的。但在第二个示例中，我很困惑为什么#split返回零长度字符串作为返回数组的第一个值。这是什么原因呢？这是我所期望的:"abcabc".split("a")#=>["bc"

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

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

  8. ruby-on-rails - 如何在发布新的 Ruby 或 Rails 版本时收到通知？ - 2

    有人知道在发布新版本的Ruby和Rails时收到电子邮件的方法吗？他们有邮件列表，RubyonRails有一个推特，但我不想听到那些随之而来的喧嚣，我只想知道什么时候发布新版本，尤其是那些有安全修复的版本。 最佳答案 从therailsblog获取提要.http://weblog.rubyonrails.org/feed/atom.xml 关于ruby-on-rails-如何在发布新的Ruby或Rails版本时收到通知？，我们在StackOverflow上找到一个类似的问题：

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

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

  10. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

随机推荐