如何在SQL中检测“conversation”模式？

Question

实际上，这与SQL无关，我怀疑"conversation pattern"也不是正确的名称，但我想不出更好的标题。

简化一下，想象一下你得到了一个巨大的整数流。 任务是检测 A.{1;max_n}A 模式：如果一个整数后面跟着 n (> 0) 其他整数，然后再次出现原始整数，则该整数满足模式，其中 n <= max_n。

例如：

...
1
4 <--
7 \
3  > n = 3
3 /
4 <--
2
...

这里，int型的4与3个任意的int型值交替出现，所以对于max_n <= 3，该模式适用于值4。

问题是，我如何检测在大量数据中哪些整数符合此模式？我主要关心算法本身，但SQL或C#示例也可以。

我想到的天真想法是首先收集所有不同整数的列表，然后对它们中的每一个以一种直接的方式检查模式，但这将导致性能瓶颈。

- mafu

---

也许可以使用数字表格？... - Mitch Wheat

抱歉，什么是数字表？ - mafu

SQL操作集合：它并不是为了比较输出集合中的行而设计的，因此对于这种类型的分析来说，它是一个糟糕的选择。 - Nick Johnson

@Nick Johnson，这是一个糟糕的选择，但不是因为你的论点，而是因为它进行通用优化并且偏向于二级存储器数据访问路径。没有什么规定说您不能基于某些属性选择集合的子集。表明SQL不适合工作的关键字是流数字，这表明需要内存结构并且需要/可能使用比您的标准SQL查询计划程序（和预定索引方法）更有效的算法。 - Unreason

我并没有说你不能基于元素的属性选择子集。我的观点是，他试图执行一项依赖于结果集中行之间关系的操作，而这不是 SQL 的设计初衷。 - Nick Johnson

Answer 1

你可以使用字典（C#）或映射（C++）结构来保存数字第一次出现的位置。

然后，对于每个数字，您应该检查它是否存在于映射中。如果是 - 您应该将其位置差与之前发生的最大位置差进行比较。否则，您应该在映射中保存数字及其位置。

- DixonD

---

你的想法可能是最简单的方法，但仍然非常有效。对我来说听起来大约是O(n * log n)。 - mafu

如果使用哈希表实现数据结构，则可以实现O(n)的复杂度。 - DixonD

确实，我的错误，使用合理的哈希函数它将是O(n)，这很好。 - mafu

Answer 2

嗯，SQL 不会以最优的方式执行，但如果列被索引，它可能不会太糟糕。

首先，在 SQL 中谈论顺序时，您应该有另一列。如果该列实际上等于行号，则可以：

SELECT DISTINCT
  t1.number
FROM 
  table t1, table t2
WHERE
  (t1.rownumber-t2.rownumber) <= @max_n AND
  (t1.rownumber-t2.rownumber) >=1 AND
  t1.number = t2.number AND

- Unreason