草庐IT

algorithm - 实时显示一段时间内最常见/重复的元素

coder 2023-06-29 原文

我有用户生成的字符串以未定义的速率传入，其中一些是重复数据，我想实时保留前 20 个最常见重复项的计数，在给定的固定时间段内(例如，在过去一小时内)，在 Go 中。

唯一字符串的数量不受任何限制，因此，为了避免 DoS，数据结构可能必须定义最多元素的大小(例如，top-10k-elements 和/或1MB 整体大小)，并删除最近最少插入的元素(如果它们还没有任何重复项)(但永远不要删除任何新传入的元素!)。

我的理解是这正是ngx_http_limit_req_module.c是implemented , 此方法在 documentation 中被引用然而，作为“漏桶”，wikipedia页面似乎表明它是将从队列中删除的新数据，而不是旧数据，因此不确定该概念是否适用。

无论如何，我尝试在 Golang 中寻找“漏桶”实现，到目前为止，我找到的最受欢迎的结果是 uber-go/ratelimit ，它的 API 似乎根本不符合我的问题陈述——它只是实现了一些实际的速率限制队列，而不是实时的前 X 超过最后 Y 计数。

任何人都可以为我正在寻找的东西建议适当的名称，以及实现这一目标的最佳方法，最好是在 Go 中吗？

最佳答案

这是两个问题。

  1. 记录您选择记录的姓名。
  2. 注意不在您要跟踪的列表中的热门名称。

对于第一个问题，我建议跟踪每个名称、每分钟有多少个。当他们完成时，将它们添加到运行总数中，并添加到要在一小时内减去的事物队列中。这为每个名称提供 60 个小对象，并且在运行的基础上，您将保持哈希运行。

第二个问题更具挑战性。为此，我会使用概率方法。这个想法是每个名字都用一个唯一的 id 进行散列，并且你只保留你在一分钟内看到的千个最小的散列值(和相关的名字)。 (我会在一分钟内给出一个算法。)你的散列值应该独立于名字均匀分布在最大的 2^64 中，所以普通名字最终会出现在这个列表中。当他们这样做时，你开始数他们! (您将丢失前几个，但是通过更多的工作，您可以估计您错过了多少。尽管如此，这种优化可能需要做更多的工作。)

现在我们如何保留千个最小的哈希值？您使用优先级队列，它通常通过堆 实现，以创建可更新的数据结构，在其中很容易提取最大的哈希值。因此，您运行以下伪代码。

create your priority queue of (hash, name)
for each name:
   hash hash of name and unique new id
   entry = (hash, name)
   if queue size < 1000:
       insert entry
   else if hash is smaller than the current max in the queue
      insert entry
      remove the largest entry

关于algorithm - 实时显示一段时间内最常见/重复的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45948719/

algorithm实时sectionhttpnoreferrernginxgodata-structures

有关algorithm - 实时显示一段时间内最常见/重复的元素的更多相关文章

  1. ruby-on-rails - Rails 编辑表单不显示嵌套项 - 2

    我得到了一个包含嵌套链接的表单。编辑时链接字段为空的问题。这是我的表格:Editingkategori{:action=>'update',:id=>@konkurrancer.id})do|f|%>'Trackingurl',:style=>'width:500;'%>'Editkonkurrence'%>|我的konkurrencer模型:has_one:link我的链接模型:classLink我的konkurrancer编辑操作:defedit@konkurrancer=Konkurrancer.find(params[:id])@konkurrancer.link_attrib

  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. ruby-on-rails - 使用 Sublime Text 3 突出显示 HTML 背景语法中的 ERB？ - 2

    所以我在关注Railscast，我注意到在html.erb文件中，ruby代码有一个微弱的背景高亮效果，以区别于其他代码HTML文档。我知道Ryan使用TextMate。我正在使用SublimeText3。我怎样才能达到同样的效果？谢谢! 最佳答案 为SublimeText安装ERB包。假设您安装了SublimeText包管理器*，只需点击cmd+shift+P即可获得命令菜单，然后键入installpackage并选择PackageControl:InstallPackage获取包管理器菜单。在该菜单中，键入ERB并在看到包时选择

  4. ruby-on-rails - link_to 不显示任何 rails - 2

    我试图在索引页中创建一个超链接，但它没有显示，也没有给出任何错误。这是我的index.html.erb代码。ListingarticlesTitleTextssss我检查了我的路线，我认为它们也没有问题。PrefixVerbURIPatternController#Actionwelcome_indexGET/welcome/index(.:format)welcome#indexarticlesGET/articles(.:format)articles#indexPOST/articles(.:format)articles#createnew_articleGET/article

  5. ruby-on-rails - 如何在 Rails View 上显示错误消息？ - 2

    我是rails的新手，想在form字段上应用验证。myviewsnew.html.erb.....模拟.rbclassSimulation{:in=>1..25,:message=>'Therowmustbebetween1and25'}end模拟Controller.rbclassSimulationsController我想检查模型类中row字段的整数范围，如果不在范围内则返回错误信息。我可以检查上面代码的范围，但无法返回错误消息提前致谢 最佳答案 关键是您使用的是模型表单，一种显示ActiveRecord模型实例属性的表单。c

  6. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  7. ruby-on-rails - 将 Ruby 中的日期/时间格式化为 YYYY-MM-DD HH :MM:SS - 2

    这个问题在这里已经有了答案:Railsformattingdate(4个答案)关闭4年前。我想格式化Time.Now函数以显示YYYY-MM-DDHH:MM:SS而不是:“2018-03-0909:47:19+0000”该函数需要放在时间中.现在功能。require‘roo’require‘roo-xls’require‘byebug’file_name=ARGV.first||“Template.xlsx”excel_file=Roo::Spreadsheet.open(“./#{file_name}“,extension::xlsx)xml=Nokogiri::XML::Build

  8. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  9. 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([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  10. ruby-on-rails - 复数 for fields_for has_many 关联未显示在 View 中 - 2

    目前，Itembelongs_toCompany和has_manyItemVariants。我正在尝试使用嵌套的fields_for通过Item表单添加ItemVariant字段，但是使用:item_variants不显示该表单。只有当我使用单数时才会显示。我检查了我的关联，它们似乎是正确的，这可能与嵌套在公司下的项目有关，还是我遗漏了其他东西？提前致谢。注意:下面的代码片段中省略了不相关的代码。编辑:不知道这是否相关，但我正在使用CanCan进行身份验证。routes.rbresources:companiesdoresources:itemsenditem.rbclassItemi

随机推荐