草庐IT

java - 性能:循环遍历 ArrayList 数百次与将 Arraylist 转换为 HashMap 并返回？

coder 2024-03-12 原文

我有两个大型(1000 多个对象)ArrayList，需要比较和操作。我基本上需要从 ArrayList A 中获取一个值，在 ArrayList B 中寻找一个匹配的对象，然后操作 B 中的对象。我需要在 A 的所有对象中执行此操作。我需要在应用程序中经常执行此操作。订单未知，尺寸会有所不同。

(pseudocode)
ArrayList<myObject> A
ArrayList<myObject> B

我可以遍历 B 中的每个项目，为 A 中的每个实体寻找与 A 中的实体匹配的项目。这看起来效率很低。

(pseudocode)
for (each object in A){loop through all of B and find it}

是否值得将 B 转换为 HashMap(使用我正在比较的特定值作为键，使用对象作为值)，然后以这种方式搜索 B，然后在我将临时 HashMap 转换回 ArrayList 时m 完成处理了吗？

(pseudocode)
convert B to HashMap<myObject.myValue,myObject> C
for (each object in A){look up the value in C}
convert C back to an ArrayList

这是个好主意吗？或者这是过早/不必要的优化？谢谢。

(背景:数据作为 ArrayList 从服务传给我 - 前端需要一个 ArrayList 用于 View 层。我试图使这个中间层处理更高效 - 但入口和导出对象必须是 ArrayList (或其他一些列表))

最佳答案

是的，对于大数，HashMap 是有益的。

您的初始算法将花费很长时间，在嵌套的 for 循环中遍历两个列表。这是一个 O(n2) 算法。即使假设 A 和 B 中各有 1000 个项目，并假设比较两个单独项目的成本为 1，一个来自 A，一个来自 B，您正在查看 500k 比较(避免比较每个项目两次)。经常这样做会导致性能下降。

假设您有一个很好的对象哈希码算法，从 HashMap 中查找一个值是 O(1) 访问。您仍然会花费 O(n) 的时间来构建它，但如果您有大量项目，这与 O(n2) 相比算不了什么。

使用“B”中的数据构造您的HashMap“C”一次并多次使用它，只要B 的信息没有改变。如果您“需要经常这样做”，那么性能会更好，因为 HashMap 已经构建——只需重用它。

如果需要维护顺序，将B列表索引作为值存储在hash map中。

您不需要“将该临时 HashMap 转换回数组列表”，因为创建 HashMap“C”不会破坏原始列表“B”。需要注意的一件事是，如果列表 B 中的对象发生变化，则强制更新 HashMap 以保持一致。另一件需要注意的事情是你对非常大的列表的内存使用——你能把对象、列表和散列映射保存在内存中吗？

你的伪代码:

for each index in B:
    get object b
    put in hash map C values (b, index)

for each a in A:
    if found in hash map C: do something with found object

对于较小的数字，O(n2) 的性能时间将足够小以致于构建 HashMap 是不值得的。这是您需要做出的决定 - 您需要确定列表何时足够大以构建 HashMap 并使用它值得 HashMap 构建成本.

关于java - 性能:循环遍历 ArrayList 数百次与将 Arraylist 转换为 HashMap 并返回？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56351188/

ArrayListcodeHashMapjavaperformance

有关java - 性能:循环遍历 ArrayList 数百次与将 Arraylist 转换为 HashMap 并返回？的更多相关文章

  1. ruby - 树顶语法无限循环 - 2

    我脑子里浮现出一些关于一种新编程语言的想法，所以我想我会尝试实现它。一位friend建议我尝试使用Treetop(Rubygem)来创建一个解析器。Treetop的文档很少，我以前从未做过这种事情。我的解析器表现得好像有一个无限循环，但没有堆栈跟踪；事实证明很难追踪到。有人可以指出入门级解析/AST指南的方向吗？我真的需要一些列出规则、常见用法等的东西来使用像Treetop这样的工具。我的语法分析器在GitHub上，以防有人希望帮助我改进它。class{initialize=lambda(name){receiver.name=name}greet=lambda{IO.puts("He

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

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

  5. ruby - RuntimeError(自动加载常量 Apps 多线程时检测到循环依赖 - 2

    我收到这个错误:RuntimeError(自动加载常量Apps时检测到循环依赖当我使用多线程时。下面是我的代码。为什么会这样？我尝试多线程的原因是因为我正在编写一个HTML抓取应用程序。对Nokogiri::HTML(open())的调用是一个同步阻塞调用，需要1秒才能返回，我有100,000多个页面要访问，所以我试图运行多个线程来解决这个问题。有更好的方法吗？classToolsController0)app.website=array.join(',')putsapp.websiteelseapp.website="NONE"endapp.saveapps=Apps.order("

  6. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  7. ruby - Ruby 中的隐式返回值是怎么回事？ - 2

    所以我开始关注ruby​​，很多东西看起来不错，但我对隐式return语句很反感。我理解默认情况下让所有内容返回self或nil但不是语句的最后一个值。对我来说，它看起来非常脆弱(尤其是)如果你正在使用一个不打算返回某些东西的方法(尤其是一个改变状态/破坏性方法的函数!)，其他人可能最终依赖于一个返回对方法的目的并不重要，并且有很大的改变机会。隐式返回有什么意义？有没有办法让事情变得更简单？总是有返回以防止隐含返回被认为是好的做法吗？我是不是太担心这个了？附言当人们想要从方法中返回特定的东西时，他们是否经常使用隐式返回，这不是让你组中的其他人更容易破坏彼此的代码吗？当然，记录一切并给出

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

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

  10. ruby-on-rails - ruby 日期方程不返回预期的真值 - 2

    为什么以下不同？Time.now.end_of_day==Time.now.end_of_day-0.days#falseTime.now.end_of_day.to_s==Time.now.end_of_day-0.days.to_s#true 最佳答案 因为纳秒数不同:ruby-1.9.2-p180:014>(Time.now.end_of_day-0.days).nsec=>999999000ruby-1.9.2-p180:015>Time.now.end_of_day.nsec=>999999998

随机推荐