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

Question

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

最小问题

我有一堆函数对象(想想像神经网络这样昂贵的东西)。它们被应用到线性缓冲区(想想 float 或 byte 的数组)，但间隔不同。所以它们看起来像那样(将 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 如何做到这一点。

Answer 1

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

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，在 s 和 intervals slice 之间进行交叉引用，以确定相邻间隔是否受到影响.我很乐意更详细地解释这部分，但我并不完全理解间隔更新的要求。 (当你做一个间隔插入时，它是否对应于底层缓冲区中的插入？或者你只是改变哪些缓冲区元素与哪些函数相关联？在这种情况下，插入是否会在下一个间隔开始时导致删除? 大多数方案应该有效，但它改变了程序。)