按间隔对对象进行有效索引的结构

Question

我目前正在研究一些工作中的想法，我有一个想法需要帮助。

我有一堆函数对象（想想像神经网络这样昂贵的东西）。它们以不同的间隔应用于线性缓冲区（比如一个由浮点或字节组成的数组）。所以它们看起来是这样的（把Start和End想象成“将对象应用到buf[开始：结束]”）：

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

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

• 时间间隔变化很大（这是一个机器学习训练循环）

这些任务可归纳如下：

1. 按索引查询：返回间隔和与间隔关联的对象

• 将间隔作为关键点进行映射。这是个坏主意，因为我必须知道某个给定的索引是否在某个时间间隔内发生了更改
• 线性结构，用于跟踪启动。当我意识到可能存在跳过时，立即发现了一个bug
• 带有“孔”的线性结构，用于跟踪起点。这就像一根绳子
• 绳索和跳绳清单。最终将我所拥有的重构到了适用于字符串的skiprope包中。更多的牦牛剃须。耶
• 间隔/分段树。实施是一个婊子。我还尝试了一个具体的gods/augmentedtree变体，但实际上无法让回拨正常工作来评估它

有没有我遗漏的好数据结构可以让这些任务变得更简单？

我错过了什么显而易见的东西吗？

一位朋友建议我查找增量编译方法，因为它很相似。使用的一个类比是，Roslyn将以一种范围广泛的方式解析/重新解析文本片段。这与我的问题非常相似——只需将浮点的线性缓冲区替换为令牌的线性缓冲区。

问题是我找不到任何关于罗斯林是如何做到的可靠有用的信息。

Answer 1

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

>

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

保留一个整数s的切片，它始终与您的浮点数缓冲区大小相同；它将缓冲区中的特定索引映射到函数切片中的“函数索引”。您可以使用-1表示不属于任何区间的数字。

保留一段（int，int）对间隔，以便间隔[i]包含存储在funcs[i]中的函数的开始-结束索引。

我相信这可以让您轻松实现所需的功能。例如，要按索引查询，请查找s[i]，然后返回funcs[s[i]和interval[s[i]。当缓冲区发生更改时，也要更改s，在s和间隔切片之间进行交叉引用，以确定相邻间隔是否受到影响。我很乐意更详细地解释这一部分，但我不完全理解间隔更新的要求。（当您执行间隔插入时，它是否与基础缓冲区中的插入相对应？或者您只是在更改哪些缓冲区元素与哪些函数关联？在这种情况下，插入是否会导致在下一个间隔开始时删除？大多数方案应该可以工作，但它会更改过程。）