草庐IT

Java:优化哈希集以进行大规模重复检测

coder 2024-03-03 原文

我正在处理一个处理大量推文的项目；目标是在我处理它们时删除重复项。我有推文 ID，它们以 "166471306949304320" 格式的字符串形式出现

我一直在使用 HashSet<String>为此，它可以正常工作一段时间。但是当我处理到大约 1000 万个项目时，我彻底陷入困境并最终得到一个 GC 错误，大概是由于重新散列。我尝试用

定义更好的尺寸/负载

tweetids = new HashSet<String>(220000,0.80F);

这让它走得更远，但仍然非常慢(处理大约 1000 万时需要 3 倍的时间)。我该如何优化呢？鉴于我大致知道到最后集合中应该有多少项目(在这种情况下，大约 20-22 百万)，我应该创建一个只重新散列两次或三次的 HashSet，还是这样的开销设置招致太多的时间惩罚？如果我不使用 String，或者如果我定义一个不同的 HashCode 函数(在这种情况下，对于 String 的特定实例，我不确定该怎么做)，事情会更好吗？这部分实现代码如下。

tweetids = new HashSet<String>(220000,0.80F); // in constructor
duplicates = 0;
...
// In loop: For(each tweet)
String twid = (String) tweet_twitter_data.get("id");
// Check that we have not processed this tweet already
if (!(tweetids.add(twid))){
    duplicates++;
    continue; 
}

解决方案

感谢您的建议，我解决了它。问题是散列表示所需的内存量；首先，HashSet<String>简直是巨大而不必要的，因为String.hashCode()对于这个规模来说太贵了。接下来我尝试了一个 Trie，但它在刚刚超过 100 万个条目时崩溃了；重新分配阵列是有问题的。我用了 HashSet<Long>效果更好，几乎成功了，但是速度下降了，最终在处理的最后一段(大约 1900 万)崩溃了。解决方案来自标准库并使用 Trove .它完成 2200 万条记录的速度比根本不检查重复项快几分钟。最终实现很简单，看起来像这样:

import gnu.trove.set.hash.TLongHashSet;
...
    TLongHashSet tweetids; // class variable
... 
    tweetids = new TLongHashSet(23000000,0.80F); // in constructor
...
    // inside for(each record)
    String twid = (String) tweet_twitter_data.get("id");
    if (!(tweetids.add(Long.parseLong(twid)))) {
        duplicates++;
        continue; 
    }

最佳答案

您可能希望超越 Java 集合框架。我做了一些内存密集型处理，你会面临几个问题

  1. 大型散列图和散列集的桶数将达到 造成大量开销(内存)。您可以通过使用来影响这一点 某种自定义哈希函数和模数，例如50000
  2. 字符串在 Java 中使用 16 位字符表示。对于大多数脚本，您可以通过使用 utf-8 编码的字节数组来减半。
  3. HashMaps 通常是非常浪费的数据结构，而 HashSets 基本上只是它们的一个薄包装。

鉴于此，请查看 trove 或 Guava 以寻找替代品。此外，您的 ID 看起来像多头。它们是 64 位的，比字符串表示形式小很多。

您可能要考虑的替代方法是使用布隆过滤器(guava 有一个不错的实现)。布隆过滤器会告诉您某物是否绝对不在集合中，并且可以合理确定(小于 100%)是否包含某物。结合一些基于磁盘的解决方案(例如数据库、mapdb、mecached 等)应该可以很好地工作。您可以缓冲传入的新 ID，分批写入它们，并使用布隆过滤器检查您是否需要在数据库中查找，从而在大多数情况下避免昂贵的查找。

关于Java:优化哈希集以进行大规模重复检测，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16693408/

大规JavacodeStringsectionoptimizationhashsetduplicate-removal

有关Java:优化哈希集以进行大规模重复检测的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby-on-rails - 按天对 Mongoid 对象进行分组 - 2

    在控制台中反复尝试之后，我想到了这种方法，可以按发生日期对类似activerecord的(Mongoid)对象进行分组。我不确定这是完成此任务的最佳方法，但它确实有效。有没有人有更好的建议，或者这是一个很好的方法？#eventsisanarrayofactiverecord-likeobjectsthatincludeatimeattributeevents.map{|event|#converteventsarrayintoanarrayofhasheswiththedayofthemonthandtheevent{:number=>event.time.day,:event=>ev

  3. ruby - 使用 C 扩展开发 ruby​​gem 时，如何使用 Rspec 在本地进行测试？ - 2

    我正在编写一个包含C扩展的gem。通常当我写一个gem时，我会遵循TDD的过程，我会写一个失败的规范，然后处理代码直到它通过，等等......在“ext/mygem/mygem.c”中我的C扩展和在gemspec的“扩展”中配置的有效extconf.rb，如何运行我的规范并仍然加载我的C扩展？当我更改C代码时，我需要采取哪些步骤来重新编译代码？这可能是个愚蠢的问题，但是从我的gem的开发源代码树中输入“bundleinstall”不会构建任何native扩展。当我手动运行rubyext/mygem/extconf.rb时，我确实得到了一个Makefile(在整个项目的根目录中)，然后当

  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 - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  6. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  7. 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("

  8. ruby - 即使失败也继续进行多主机测试 - 2

    我已经构建了一些serverspec代码来在多个主机上运行一组测试。问题是当任何测试失败时，测试会在当前主机停止。即使测试失败，我也希望它继续在所有主机上运行。Rakefile:namespace:specdotask:all=>hosts.map{|h|'spec:'+h.split('.')[0]}hosts.eachdo|host|begindesc"Runserverspecto#{host}"RSpec::Core::RakeTask.new(host)do|t|ENV['TARGET_HOST']=hostt.pattern="spec/cfengine3/*_spec.r

  9. ruby - 如何在 Grape 中定义哈希数组？ - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

  10. ruby - 是否可以覆盖 gemfile 进行本地开发？ - 2

    我们的git存储库中目前有一个Gemfile。但是，有一个gem我只在我的环境中本地使用(我的团队不使用它)。为了使用它，我必须将它添加到我们的Gemfile中，但每次我checkout到我们的master/dev主分支时，由于与跟踪的gemfile冲突，我必须删除它。我想要的是类似Gemfile.local的东西，它将继承从Gemfile导入的gems，但也允许在那里导入新的gems以供使用只有我的机器。此文件将在.gitignore中被忽略。这可能吗？ 最佳答案 设置BUNDLE_GEMFILE环境变量:BUNDLE_GEMFI

随机推荐