草庐IT

algorithm - 按时间间隔对对象进行高效索引的结构

coder 2023-06-26 原文

我目前正在研究一些关于 CRF 的想法,我有一个想法需要帮助。

最小问题

我有一堆函数对象(想想像神经网络这样昂贵的东西)。它们被应用到线性缓冲区(想想 floatbyte 的数组),但间隔不同。所以它们看起来像那样(将 Start 和 End 视为“将对象应用于 buf[Start:End]”:

| Object | Start | End |
|--------|-------|-----|
| A      | 0     | 4   |
| B      | 4     | 10  |
| C      | 13    | 15  |

区间特征

  • 可能会有一些跳过(例如,查看 C 的开头与 B 的结尾)
  • 间隔肯定会发生变化,无论是正的还是负的(例如,B 可能从 [4:10] 变为 [4:12]
  • 发生这种情况时,可能必须重新应用与间隔关联的对象。
  • 如果间隔更改与另一个间隔重叠,则必须重新应用两个对象。例如,如果 B 从 [4:10] 更改为 [3:12],则必须将 A 应用于范围 [0:3] 和 B 必须应用于范围 [3:12]
  • 根据操作,下游间隔也必须更新,但不一定要重新应用对象。例如,如果插入改变了 B 的区间范围,那么 C 的区间范围也会增加 2,但不会触发 C 的重新应用。

项目特色

  • 间隔变化很大(这是一个机器学习训练循环)。
  • 支持的间隔更新形式有:插入、删除、左移、右移。后两者与插入/删除相同,但应用于间隔的末尾。
  • 间隔的更改通常以元组(索引和大小)或单个索引的形式出现。
  • 函数的应用是相当昂贵的操作并且受 CPU 限制。
  • 但是,由于我使用的是 Go,几个互斥体 + goroutine 解决了大部分问题(有一些更精细的点,但大范围可以忽略)。
  • 一个时期可以有 5-60 个区间对象对。
  • 缓冲区是线性的,但不一定连续。

任务

任务可以总结如下:

  1. 索引查询:返回区间和区间关联的对象
  2. 更新间隔:必要时还必须更新下游(这是大多数情况)
  3. 插入新的间隔:还必须更新下游

我尝试过的

  • 以区间为键映射。这是个坏主意,因为我必须知道更改的给定索引是否在某个时间间隔内
  • 跟踪开始的线性结构。当我意识到可能存在跳过时立即发现了一个错误。
  • 带有“孔”的线性结构以跟踪开始。结果证明这类似于绳索。
  • 绳索和跳表。最终将我所拥有的重构为 skiprope适用于字符串的包。更多的牦牛毛。是的。
  • 区间/线段树。实现是个婊子。我还尝试了 gods/augmentedtree 的具体变体但实际上无法让回叫正常工作以对其进行评估。

问题

是否有我遗漏的任何好的数据结构可以使这些任务更容易?

我是不是错过了一些非常明显的东西?

friend 建议我查一下增量编译的方法,因为都差不多。使用的类比是 Roslyn 将以一定范围的方式解析/重新解析文本片段。这与我的问题非常相似 - 只需将 float 的线性缓冲区替换为标记的线性缓冲区。

问题是我找不到任何可靠有用的信息来说明 Roslyn 如何做到这一点。

最佳答案

此解决方案的内存效率不是特别高,但如果我对您的理解正确,它应该允许相对简单地实现您想要的功能。

  1. 保留所有函数对象的数组或 slice funcs,以便它们每个都有一个规范的整数索引,并且可以通过该索引查找。

  2. 保留一个整数 s 的片段,它总是与你的 float 缓冲区大小相同;它将缓冲区中的特定索引映射到函数 slice 中的“函数索引”。您可以使用 -1 来表示不属于任何区间的数字。

  3. 保留一片 (int, int) 对 intervals 使得 intervals[i] 包含存储在 处的函数的开始和结束索引>funcs[i].

我相信这可以让您轻松实现所需的功能。例如,要按索引i 查询,查找s[i],然后返回funcs[s[i]]间隔[s[i]]。当缓冲区发生更改时,也更改 s,在 sintervals slice 之间进行交叉引用,以确定相邻间隔是否受到影响.我很乐意更详细地解释这部分,但我并不完全理解间隔更新的要求。 (当你做一个间隔插入时,它是否对应于底层缓冲区中的插入?或者你只是改变哪些缓冲区元素与哪些函数相关联?在这种情况下,插入是否会在下一个间隔开始时导致删除? 大多数方案应该有效,但它改变了程序。)

关于algorithm - 按时间间隔对对象进行高效索引的结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46873687/

有关algorithm - 按时间间隔对对象进行高效索引的结构的更多相关文章

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

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

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

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

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

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

  4. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过,我不想只删除标签,我想智能地保留尽可能多的格式。为插入换行符标签,检测段落并格式化它们等。输入非常简单,通常是格式良好的html(不是整个文档,只是一堆内容,通常没有anchor或图像)。我可以将几个正则表达式放在一起,让我达到80%,但我认为可能有一些现有的解决方案更智能。 最佳答案 首先,不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案,它会随着HTML的变化而崩溃,或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  5. 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(在整个项目的根目录中),然后当

  6. ruby-on-rails - 如何验证非模型(甚至非对象)字段 - 2

    我有一个表单,其中有很多字段取自数组(而不是模型或对象)。我如何验证这些字段的存在?solve_problem_pathdo|f|%>... 最佳答案 创建一个简单的类来包装请求参数并使用ActiveModel::Validations。#definedsomewhere,atthesimplest:require'ostruct'classSolvetrue#youcouldevencheckthesolutionwithavalidatorvalidatedoerrors.add(:base,"WRONG!!!")unlesss

  7. Ruby 写入和读取对象到文件 - 2

    好的,所以我的目标是轻松地将一些数据保存到磁盘以备后用。您如何简单地写入然后读取一个对象?所以如果我有一个简单的类classCattr_accessor:a,:bdefinitialize(a,b)@a,@b=a,bendend所以如果我从中非常快地制作一个objobj=C.new("foo","bar")#justgaveitsomerandomvalues然后我可以把它变成一个kindaidstring=obj.to_s#whichreturns""我终于可以将此字符串打印到文件或其他内容中。我的问题是,我该如何再次将这个id变回一个对象?我知道我可以自己挑选信息并制作一个接受该信

  8. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象,为什么它会起作用? - 2

    如果您尝试在Ruby中的nil对象上调用方法,则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而,有一个tryRails中的方法,如果它被发送到一个nil对象,它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常? 最佳答案 像Ruby中的所有其他对象

  9. ruby-on-rails - 未在 Ruby 中初始化的对象 - 2

    我在Rails工作并有以下类(class):classPlayer当我运行时bundleexecrailsconsole然后尝试:a=Player.new("me",5.0,"UCLA")我回来了:=>#我不知道为什么Player对象不会在这里初始化。关于可能导致此问题的操作/解释的任何建议?谢谢,马里奥格 最佳答案 havenoideawhythePlayerobjectwouldn'tbeinitializedhere它没有初始化很简单,因为你还没有初始化它!您已经覆盖了ActiveRecord::Base初始化方法,但您没有调

  10. 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][

随机推荐