问题标签 [online-algorithm]

在线排序算法和外部排序算法有什么区别？它们是相同的还是不同的？

我正在寻找实施的在线学习时间序列算法。R、Python、MOA 或任何其他工具是否实现了这些算法？

蒂亚！

I'm trying to find a "dynamic" linear programming solver. A dynamic linear programming solver means that an LP solver supporting (very fast) insertions and deletions of the constraints.

I found a paper about a dynamic LP solver written by David Eppstein, but I cannot find any implementations.

Is there an implementation of Eppstein's algorithm or similar algorithm?

我正在寻找一种增量应用正则表达式模式的方法，即我正在寻找一个匹配器，我可以在输入字符时对其进行更新，并在每个字符上告诉我它是否仍然匹配。

这是代码中的一个插图（这MagicMatcherIAmLookingFor是我正在寻找的characterSource东西，是我可以查询新字符的东西InputStreamReader，就此说一个）：

我没有找到java.util.regex.Pattern像那样利用现有的方法，但也许我只是没有找到它。或者是否有提供此类功能的内置正则表达式的替代库？

我没有任何运气在网上搜索它 - 所有结果都完全淹没了如何首先使用 java 正则表达式。

我的目标是 Java 8+

我有一些问题要弄清楚为什么你需要从书中的 λ-return 算法的在线版本中重新审视每个地平线上的情节中的所有时间步骤：
Reinforcement Learning: An Introduction, 2nd Edition, Chapter 12, Sutton & Barto

这里所有的权重向量序列 W1, W2,..., Wh 对于每个地平线 h 都从 W0 开始（上一集结束时的权重）。然而，它们似乎并不依赖于前一阶段的回报/权重，并且可以独立计算。在我看来，这只是为了澄清起见，您只能在剧集结束时计算最终水平 h=T 的值。这将与算法的离线版本所做的相同，实际的更新规则是：

毫不奇怪，我在 19-states Random Walk 示例中得到了两种算法完全相同的结果：

书中提到，在线版本的性能应该稍好一些，在这种情况下，它应该具有与 True Online TD(λ) 相同的结果。在实施后者时，它确实优于离线版本，但我无法弄清楚简单而缓慢的在线版本。

任何建议将不胜感激。

谢谢

考虑一个整数序列A = a1, a2, a3, ... an。A的子序列B是一个序列B = b1, b2, .... ,bn ，它是通过删除一些元素但保持顺序从A创建的。给定一个整数序列A，目标是计算一个交替子序列B，即一个序列b1, ... bn使得对于 {2, 3, ... , m-1} 中的所有i，如果 b{i- 1} < b{i} 然后 b{i} > b{i+1} 如果 b{i-1} > b{i} 然后 b{i} < b{i+1}**

---

考虑该问题的在线版本，其中序列A是逐个元素给出的，并且每次都需要直接决定是否在子序列B中包含下一个元素。是否有可能实现恒定的竞争比率（通过使用确定性在线算法）？要么给出一个达到恒定竞争比的在线算法，要么表明不可能找到这样的在线算法。

假设序列 [9,8,9,8,9,8, .... , 9,8,9,8,2,1,2,9,8,9, ... , 8,9,8, 9,8,9]

我的论点：算法必须立即决定是否将传入的数字插入子序列。如果算法现在得到数字 1 然后 2 然后 2 它将最终确定它们是序列的一部分，因此非线性因子比 n-3 的最优解更差。

-> 没有恒定的竞争力！

这是一个适当的论证吗？

我正在寻找一种在线算法来处理比我可以合理存储的更多的数据。

我只想保留n值v[n]小于任何后续值的数据点。（数值通常在增加。）

这样做的明显方法（不是说唯一的方法，或正确的方法）是使用堆栈。对于每个新点，当它们的值大于当前点的值时，从堆栈中弹出点，然后将当前点压入堆栈。

但是数据非常稀疏。在快速测试中，每 TB 仅节省了大约 3 MB。

我是在线算法领域的新手。我看到大多数学术论文使用竞争比率的概念来衡量所提出的在线算法的效率。是否有可能为任何给定的在线算法找到这样的指标？