草庐IT

Java PriorityQueue去除任意元素性能

coder 2024-03-18 原文

假设我有一个 java PriorityQueue(java 作为堆实现)，我迭代它以根据某些条件删除元素:

PriorityQueue q = new PriorityQueue();
...
Iterator it = q.iterator();
while(it.hasNext()){
    if( someCriterion(it.next()) )
        it.remove();
}

每个 remove() 操作需要多长时间？我不确定它是 O(log(n)) 还是 O(1)。

最佳答案

如果您使用的是 Sun 实现，它是 O(log(n))。 来自 Javadocs :

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

其他实现可能具有不同的复杂性。

编辑:Javadoc 没有介绍使用迭代器删除元素的性能，所以我不得不查找源代码。这都与 Sun 实现相关，并且可能在 Apple 的版本、GNU 类路径等方面有所不同。Sun 的源代码可用 here ;它也包含在 JDK 中，因此您可能已经安装了它。

在 PriorityQueue 的迭代器中，remove() 的默认情况是调用 PriorityQueue.removeAt(lastRet)，其中 lastRet 是 next() 最后返回的索引。 removeAt() 似乎是 O(log(n)) 最坏的情况(它可能必须筛选队列，但不必迭代)。

但是，有时会发生不好的事情。来自 removeAt() 的评论:

/**
 * Removes the ith element from queue.
 *
 * Normally this method leaves the elements at up to i-1,
 * inclusive, untouched.  Under these circumstances, it returns
 * null.  Occasionally, in order to maintain the heap invariant,
 * it must swap a later element of the list with one earlier than
 * i.  Under these circumstances, this method returns the element
 * that was previously at the end of the list and is now at some
 * position before i. This fact is used by iterator.remove so as to
 * avoid missing traversing elements.
 */

当 removeAt() 返回一个非空元素时，迭代器将它添加到一个特殊的队列中供以后使用:当迭代器用完队列中的元素时，它会遍历这个特殊的队列。当在迭代的第二阶段调用 remove() 时，迭代器调用 PriorityQueue.removeEq(lastRetElt)，其中 lastRetElt 是最后一个元素从特殊队列返回。 removeEq 被迫使用线性搜索来找到要删除的正确元素，这使其成为 O(n)。但是它可以使用 == 而不是 .equals() 检查元素，因此它的常数因子低于 PriorityQueue.remove(Object)。

因此，换句话说，使用迭代器删除在技术上是 O(n)，但实际上它应该比 remove(Object) 快很多。

关于Java PriorityQueue去除任意元素性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/756790/

PriorityQueue去除coderemovejavaperformancecollectionsqueue

有关Java PriorityQueue去除任意元素性能的更多相关文章

  1. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  2. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  3. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

  4. ruby-on-rails - 在 RSpec 中，如何以任意顺序期望具有不同参数的多条消息？ - 2

    RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)

  5. ruby - Hanami link_to 助手只呈现最后一个元素 - 2

    我是HanamiWorld的新人。我已经写了这段代码:moduleWeb::Views::HomeclassIndexincludeWeb::ViewincludeHanami::Helpers::HtmlHelperdeftitlehtml.headerdoh1'Testsearchengine',id:'title'hrdiv(id:'test')dolink_to('Home',"/",class:'mnu_orizontal')link_to('About',"/",class:'mnu_orizontal')endendendendend我在模板上调用了title方法。htm

  6. ruby - 将n维数组的每个元素乘以Ruby中的数字 - 2

    在Ruby中，是否有一种简单的方法可以将n维数组中的每个元素乘以一个数字？这样:[1,2,3,4,5].multiplied_by2==[2,4,6,8,10]和[[1,2,3],[1,2,3]].multiplied_by2==[[2,4,6],[2,4,6]]？(很明显，我编写了multiplied_by函数以区别于*，它似乎连接了数组的多个副本，不幸的是这不是我需要的)。谢谢! 最佳答案 它的长格式等价物是:[1,2,3,4,5].collect{|n|n*2}其实并没有那么复杂。你总是可以使你的multiply_by方法:c

  7. arrays - 计算数组中的匹配元素 - 2

    给定两个大小相等的数组，如何找到不考虑位置的匹配元素的数量？例如:[0,0,5]和[0,5,5]将返回2的匹配项，因为有一个0和一个5共同；[1,0,0,3]和[0,0,1,4]将返回3的匹配项，因为0有两场，1有一场；[1,2,2,3]和[1,2,3,4]将返回3的匹配项。我尝试了很多想法，但它们都变得相当粗糙和令人费解。我猜想有一些不错的Ruby习惯用法，或者可能是一个正则表达式，可以很好地回答这个解决方案。 最佳答案 您可以使用count完成它:a.count{|e|index=b.index(e)andb.delete_at

  8. Ruby 的数字方法性能 - 2

    我正在使用Ruby解决一些ProjectEuler问题，特别是这里我要讨论的问题25(Fibonacci数列中包含1000位数字的第一项的索引是多少？)。起初，我使用的是Ruby2.2.3，我将问题编码为:number=3a=1b=2whileb.to_s.length但后来我发现2.4.2版本有一个名为digits的方法，这正是我需要的。我转换为代码:whileb.digits.length当我比较这两种方法时，digits慢得多。时间./025/problem025.rb0.13s用户0.02s系统80%cpu0.190总计./025/problem025.rb2.19s用户0.0

  9. ruby - Ruby 性能中的计时器 - 2

    我正在寻找一个用ruby​​演示计时器的在线示例，并发现了下面的代码。它按预期工作，但这个简单的程序使用30Mo内存(如Windows任务管理器中所示)和太多CPU有意义吗？非常感谢deftime_blockstart_time=Time.nowThread.new{yield}Time.now-start_timeenddefrepeat_every(seconds)whiletruedotime_spent=time_block{yield}#Tohandle-vesleepinteravalsleep(seconds-time_spent)iftime_spent

  10. ruby - 使用 Nokogiri 和 Ruby 命名元素 "text" - 2

    我在尝试使用Nokogiri构建XML文档时遇到了一个小问题。我想将我的元素之一称为“文本”(请参阅​​下面粘贴代码的最底部)。通常，要创建一个新元素，我会执行类似以下的操作xml.text--但它似乎是.text是Nokogiri已经用来做其他事情的方法。因此，当我写这行时xml.textNokogiri没有创建名为的新元素但只是写了意味着成为元素内容的文本。我怎样才能让Nokogiri实际制作一个名为的元素？？builder=Nokogiri::XML::Builder.newdo|xml|xml.TEI("xmlns"=>"http://www.tei-c.org/ns/1.0"

随机推荐