草庐IT

java - Java中数组寻址的时间复杂度差异

coder 2024-03-23 原文

所以我在编码涉及时间复杂度的图像处理功能时有一个随机问题。以下是我的原始代码片段:

    long start = System.currentTimeMillis();

    for (int i = 0; i < newWidth; i++) {
        for (int j = 0; j < newHeight; j++) {

            double x = i * scaleX;
            double y = j * scaleY;

            double xdiff = x - (int) x;
            double ydiff = y - (int) y;

            int xf = (int) Math.floor(x);
            int xc = (int) Math.ceil(x);
            int yf = (int) Math.floor(y);
            int yc = (int) Math.ceil(y);

            double out = inputArray[xf][yf] * (1 - xdiff) * (1 - ydiff)
                    + inputArray[xc][yf] * xdiff * (1 - ydiff)
                    + inputArray[xf][yc] * (1 - xdiff) * ydiff
                    + inputArray[xc][yc] * xdiff * ydiff;

            outputArray[i][j] = (int) out;
        }
    }

    long elapsed = System.currentTimeMillis() - start;
    System.out.println("Time used: " + elapsed);

在得出该代码之后，我想知道不为下限值和上限值创建 4 个临时变量而是直接在数组索引中计算它们是否会更快。所以我这样修改:

    long start = System.currentTimeMillis();

    for (int i = 0; i < newWidth; i++) {
        for (int j = 0; j < newHeight; j++) {

            double x = i * scaleX;
            double y = j * scaleY;

            double xdiff = x - (int) x;
            double ydiff = y - (int) y;

            double out = inputArray[(int) Math.floor(x)][(int) Math.floor(y)] * (1 - xdiff) * (1 - ydiff)
                    + inputArray[(int) Math.ceil(x)][(int) Math.floor(y)] * xdiff * (1 - ydiff)
                    + inputArray[(int) Math.floor(x)][(int) Math.ceil(y)] * (1 - xdiff) * ydiff
                    + inputArray[(int) Math.ceil(x)][(int) Math.ceil(y)] * xdiff * ydiff;

            outputArray[i][j] = (int) out;
        }
    }

    long elapsed = System.currentTimeMillis() - start;
    System.out.println("Time used: " + elapsed);

我原以为后者会更快(因为您不必写入一个临时变量然后访问它)但事实证明后者至少比前者慢 2.5 倍。使用的测试用例是 1024x768 img 的 3 倍缩放。

原代码:使用时间:812 后来的代码:使用时间:2140

那么造成时差的原因是什么？

最佳答案

您在后面的代码中有 8 个 Math.floor()/Math.ceil() 计算而不是 4 个。这就是问题所在。

计算比为局部变量分配空间慢得多。

关于java - Java中数组寻址的时间复杂度差异，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7653537/

javaintMathinputArraytimecomplexity-theory

有关java - Java中数组寻址的时间复杂度差异的更多相关文章

  1. ruby - 将差异补丁应用于字符串/文件 - 2

    对于具有离线功能的智能手机应用程序，我正在为Xml文件创建单向文本同步。我希望我的服务器将增量/差异(例如GNU差异补丁)发送到目标设备。这是计划:Time=0Server:hasversion_1ofXmlfile(~800kiB)Client:hasversion_1ofXmlfile(~800kiB)Time=1Server:hasversion_1andversion_2ofXmlfile(each~800kiB)computesdeltaoftheseversions(=patch)(~10kiB)sendspatchtoClient(~10kiBtransferred)Cl

  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 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  4. ruby-on-rails - 将 Ruby 中的日期/时间格式化为 YYYY-MM-DD HH :MM:SS - 2

    这个问题在这里已经有了答案:Railsformattingdate(4个答案)关闭4年前。我想格式化Time.Now函数以显示YYYY-MM-DDHH:MM:SS而不是:“2018-03-0909:47:19+0000”该函数需要放在时间中.现在功能。require‘roo’require‘roo-xls’require‘byebug’file_name=ARGV.first||“Template.xlsx”excel_file=Roo::Spreadsheet.open(“./#{file_name}“,extension::xlsx)xml=Nokogiri::XML::Build

  5. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

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

  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. 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)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

随机推荐