Как определить шаблон «разговора» в SQL?

Question

На самом деле, это не относится к SQL, и я сомневаюсь, что «шаблон разговора» - правильное имя, но я не мог придумать более подходящую подпись.

Для упрощения представьте, что вы получили огромный поток целых. Задача состоит в том, чтобы обнаружить шаблон A.{1;max_n}A: int удовлетворяет шаблону, если за ним следует n (> 0) других целых, затем снова исходное int, тогда как n <= max_n. </p>

Пример:

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

Здесь int 4 повторяется с 3 произвольными интервалами между ними, поэтому для max_n <= 3 шаблон удовлетворяется для значения <code>4.

Вопрос в том, как определить, какие целые числа в огромном дампе данных следуют этому шаблону? В основном меня интересует сам алгоритм, но пример с SQL или C # также приветствуется.

Наивная идея, которую я придумал, состоит в том, чтобы сначала собрать список или все отдельные целые, а затем проверить шаблон для каждого из них простым способом, но это приведет к узкому месту в производительности.

Answer 1

Вы можете хранить некоторую структуру словаря (C #) или карты (C ++), где будет сохранена позиция первого появления чисел.

Тогда для каждого номера вы должны проверить, присутствует ли он на карте. Если да - вы должны сравнить разницу положения с максимальной разницей положения, имевшей место ранее. В противном случае вам следует сохранить номер и его положение на карте.

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