草庐IT

Java:允许重复的排序集合，内存效率高并提供快速插入+更新

coder 2023-05-19 原文

具体来说，我需要一个集合，它使用一个字段 A 进行访问，并使用一个不同的字段(字段 S)进行排序，但是一个接受重复的排序集合就足够了。

我经常遇到这种情况，我需要这个集合，而 TreeMap 不是一个选项，因为它不允许重复。所以现在是时候在这里问了。 stackoverflow here 上指出了几种解决方法和 here - 即有:

  • PriorityQueue:更新慢(remove(Object) + add(Object))，原始键装箱
  • 斐波那契堆:内存浪费 (?)
  • TreeMap<Field_S, List<Value>> :对我来说问题是列表的内存开销和原始键的装箱
  • 排序列表或数组:问题是插入和删除速度慢 -> 我应该实现一个分段排序列表吗？
  • TreeMultimap来自 Guava (docs):外部依赖和可能内存效率低下(？)

谁有更好的建议？或者我应该扮演我自己的排序数据结构(哪一个？)？其他来源(Java、开源、带有单元测试和小型 deps)也会很好。

更新

目前有关我的用例的更多详细信息(尽管我上次也有类似的需求)。我有一个集合(数百万)我希望能够使用的引用文献

  • 轮询或获取有关字段 S 的最小元素
  • 并在字段 A 的帮助下更新字段 S
  • 可能会出现字段 S 的相同值。字段 A 实际上是一个指向另一个数组的整数
  • 我想要的唯一依赖项是 trove4j。如果需要，我可以使用不同的 mahout 集合。但不是 Guava ，因为虽然是一个不错的库，但集合并没有调整为内存效率(装箱/拆箱)。

所以所有人都在呼唤斐波那契堆，但我担心每个元素的开销太大 -> 这就是我考虑使用内存效率更高的“排序+分段数组”解决方案的原因。

最佳答案

当你需要一个排序的集合时，你应该仔分割析你的需求。
如果大多数操作是 inserting 并且只有少数是要搜索的，那么使用排序集合，即保持集合中的元素不断地排序，这不是一个好的选择(由于在插入时保持元素排序的开销，这将是最常见的操作)。
在这种情况下，最好保留一个 unsorted 集合并仅在需要时进行排序。 IE。在搜索之前。您甚至可以使用简单的 List 并在需要时对其进行排序(使用 Collections.sort 即合并排序)。但我建议谨慎使用，因为为了高效，假设您在处理大数据。在非常小的数据中，即使是线性搜索也足够好。

如果大多数操作是搜索，那么您可以使用排序集合，从我的角度来看，有数据结构可供选择(您已经提到了一些)，您可以进行基准测试以查看哪一个适合您的需要。

关于Java:允许重复的排序集合，内存效率高并提供快速插入+更新，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12827595/

并提Javastrongsectionstackoverflowdata-structures

有关Java:允许重复的排序集合，内存效率高并提供快速插入+更新的更多相关文章

  1. ruby-on-rails - Ruby net/ldap 模块中的内存泄漏 - 2

    作为我的Rails应用程序的一部分，我编写了一个小导入程序，它从我们的LDAP系统中吸取数据并将其塞入一个用户表中。不幸的是，与LDAP相关的代码在遍历我们的32K用户时泄漏了大量内存，我一直无法弄清楚如何解决这个问题。这个问题似乎在某种程度上与LDAP库有关，因为当我删除对LDAP内容的调用时，内存使用情况会很好地稳定下来。此外，不断增加的对象是Net::BER::BerIdentifiedString和Net::BER::BerIdentifiedArray，它们都是LDAP库的一部分。当我运行导入时，内存使用量最终达到超过1GB的峰值。如果问题存在，我需要找到一些方法来更正我的代

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  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-on-rails - Ruby 中的内存模型 - 2

    ruby如何管理内存。例如:如果我们在执行过程中采用C程序，则以下是内存模型。类似于这个ruby如何处理内存。C:__________________|||stack|||------------------||||------------------|||||Heap|||||__________________|||data|__________________|text|__________________Ruby:? 最佳答案 Ruby中没有“内存”这样的东西。Class#allocate分配一个对象并返回该对象。这就是程序

  5. ruby-on-rails - RSpec:避免使用允许接收的任何实例 - 2

    我正在处理旧代码的一部分。beforedoallow_any_instance_of(SportRateManager).toreceive(:create).and_return(true)endRubocop错误如下:Avoidstubbingusing'allow_any_instance_of'我读到了RuboCop::RSpec:AnyInstance我试着像下面那样改变它。由此beforedoallow_any_instance_of(SportRateManager).toreceive(:create).and_return(true)end对此:let(:sport_

  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. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

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

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

随机推荐