草庐IT

【Java数据结构及算法实战】系列003:程序性能的两种表示方式

_waylau 2023-06-05 原文

本节是《Java数据结构及算法实战》系列的第3节,主要介绍程序性能的两种表示方式。

评价一个程序好坏的指标非常多,比如易用性、稳定性、可维护性等等,但一个最为重要的评价指标是性能。性能是其他评价指标的基础。

比如,在Web网站响应时间方面,业界的评判标准是主样的:

  • 在2秒之内给客户响应被用户认为是“非常有吸引力”的用户体验。
  • 在5秒之内给客户响应被用户认为是“比较不错”的用户体验。
  • 在10秒之内给客户响应被用户认为是“糟糕”的用户体验。
  • 如果超过10秒还没有得到响应,那么大多数用户会认为这次请求是失败的。

由此我们可以得出结论,Web网站的性能越好,处理时间越短,响应时间越短,则会有更好的用户体验。

所谓程序性能(Program Performance),是指运行一个程序所需要的内存大小和时间。有两个专业的术语来代表程序在运行时所要占用的内存大小和时间,那就是空间复杂度时间复杂度

1. 空间复杂度

程序的空间复杂度(Space Complexity)是指运行完一个程序所需要的内存大小。对一个程序的空间复杂度感兴趣的主要原因如下:

  • 如果程序将要运行在一个多用户计算机系统中,可能需要指明分配给该程序的内存大小。
  • 对任何一个计算机系统,想提前知道是否有足够可用的内存来运行该程序。
  • 一个问题可能有若干个内存需求各不相同的解决方案。比如,对于某类应用程序有两个不同的版本,这两个版本分别回占用的内存空间为1G和2G不同的版本,占用内存越大运行速度越快。如果当前的计算机少于2G的内存,则只能选择1G的版本。如果计算机大于2G的内存,则只可选择2G的版本。
  • 可以利用空间复杂度来估算一个程序所能解决的问题的最大规模。例如,在“学生信息管理系统”中,一个Student类型的对象可能占用1K字节的内存。当可利用的内存总量为1024K字节,那么最大可以处理1024个学生的信息。

2. 时间复杂度

程序的时间复杂度(Time Complexity)是指运行完该程序所需要的时间。需要关注程序的时间复杂度的原因有以下几点:

  • 有些系统需要用户提供运行时间的上限,一旦达到这个上限,客户端程序将被强制结束。比如,数据库的客户端连接会话往往会设置一个超时时间,当客户端的执行时间大于会话的超时时间时,该会话会被终止。这种办法可以避免某个客户端长时间占用系统资源而导致整个系统不可用。
  • 交互式程序往往要求实时响应。比如,访问Web网站,用户总是期望网页能够及时响应。
  • 如果一个问题有多种解决方案,那么具体采用哪种方案,主要根据这些方案的性能差异。对于各种方案的时间和空间的性能,需要权衡考虑。比如,在一个实时性要求比较高的场景下,往往会将经常访问的数据缓存在内存中(比如Redis),从而提升查询的效率,这就是一个典型的牺牲空间性能换取时间性能的场景。

简言之,空间复杂度和时间复杂度越小的程序,其性能越高。如果空间复杂度和时间复杂度两者不可兼得,则需要权衡。

参考引用

有关【Java数据结构及算法实战】系列003:程序性能的两种表示方式的更多相关文章

  1. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过,我不想只删除标签,我想智能地保留尽可能多的格式。为插入换行符标签,检测段落并格式化它们等。输入非常简单,通常是格式良好的html(不是整个文档,只是一堆内容,通常没有anchor或图像)。我可以将几个正则表达式放在一起,让我达到80%,但我认为可能有一些现有的解决方案更智能。 最佳答案 首先,不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案,它会随着HTML的变化而崩溃,或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么,使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作,但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式,例如使用这个yaml文件,它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

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

  4. ruby - Ruby 有 `Pair` 数据类型吗? - 2

    有时我需要处理键/值数据。我不喜欢使用数组,因为它们在大小上没有限制(很容易不小心添加超过2个项目,而且您最终需要稍后验证大小)。此外,0和1的索引变成了魔数(MagicNumber),并且在传达含义方面做得很差(“当我说0时,我的意思是head...”)。散列也不合适,因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题,但我很想知道:Ruby标准库是否已经带有这样一个类? 最佳

  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 - 是否有用于序列化和反序列化各种格式的对象层次结构的模式? - 2

    给定一个复杂的对象层次结构,幸运的是它不包含循环引用,我如何实现支持各种格式的序列化?我不是来讨论实际实现的。相反,我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby,我想解析XML和JSON数据以构建复杂的对象层次结构。此外,应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗?在任何提到的情况下,我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好,这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  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 - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

  10. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用,HOOPSPlatform组件都可以为您提供弹性的3D集成架构,同时,由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台(桌面/WEB/APP,而且某些客户端是“瘦”客户端)快速、方便地将数据接入到3D应用系统的解决方案,并且当访问数据时,在各个平台上的性能和用户体验保持一致,HOOPSPlatform将帮助您完成。利用HOOPSPlatform,您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品,HOOPSSDK包含的技术有:快速且准确的CAD

随机推荐