Найти все непрерывные диапазоны длины N
От: Sinclair Россия https://github.com/evilguest/
Дата: 18.10.10 07:29
Оценка:
Что-то я стал туповат. Задача:
1. Есть таблица, в которой хранится, допустим, поле Value. И, допустим, уникальный идентификатор ID.
2. Есть задача: найти блок из N непрерывных значений.
3. Точнее, найти все такие блоки. (Очевидно, достаточно найти голову или хвост блока — остальные значения получаются тривиально).

То есть, из таблички 1, 2, 3, 4, 6, 7, 8, 9 должны получаться вот такие ответы:
Для N = 1: сама табличка
Для N = 2: (1, 2), (2, 3), (3, 4), (6, 7), (7, 8), (8, 9)
Для N = 3: (1, 2, 3), (2, 3, 4), (6, 7, 8), (7, 8, 9)
Для N = 4: (1, 2, 3, 4), (6, 7, 8, 9)
Для N = 5 блоков нет

Решение нужно для MS SQL (2005 и выше) и для Postgres.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Найти все непрерывные диапазоны длины N
От: _FRED_ Черногория
Дата: 18.10.10 08:32
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Что-то я стал туповат. Задача:

S>1. Есть таблица, в которой хранится, допустим, поле Value. И, допустим, уникальный идентификатор ID.
S>2. Есть задача: найти блок из N непрерывных значений.
S>3. Точнее, найти все такие блоки. (Очевидно, достаточно найти голову или хвост блока — остальные значения получаются тривиально).

Как использовать "уникальный идентификатор ID" — зачем он дан? Решение требуется, конечно же, без курсоров, запросом?

S>То есть, из таблички 1, 2, 3, 4, 6, 7, 8, 9 должны получаться вот такие ответы:


Данные — только целые числа? Или может быть что угодно + функция a-la GetNext(current)?
Help will always be given at Hogwarts to those who ask for it.
Re: Для MS SQL
От: _d_m_  
Дата: 18.10.10 09:09
Оценка: 58 (1)
Здравствуйте, Sinclair, Вы писали:

S>3. Точнее, найти все такие блоки. (Очевидно, достаточно найти голову или хвост блока — остальные значения получаются тривиально).


Ну дак это не проблема. Нахождение "голов" блока:

create table _tt(
    val int not null
);
GO
insert
    _tt
select 1
union all select 2
union all select 3
union all select 4
union all select 6
union all select 7
union all select 8
union all select 9
;


SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
create function [dbo].[_func](
    @valBegin int
) returns int
as begin
    declare @retval int;

    with cte as(
        select
            t.val,
            1 as RowNum
        from
            _tt t
        where
            val = @valBegin
        union all
        select
            t1.val,
            ctePrev.RowNum + 1
        from
            _tt t1
                inner join
            cte ctePrev
                    on
                        ctePrev.val + 1 = t1.val
    )
    select
        @retval = max(RowNum)
    from
        cte
    ;

    return @retval;
end


select
    *
from
    _tt
where
    dbo._func(_tt.val) >= 3
;
Re[2]: Для MS SQL
От: _d_m_  
Дата: 18.10.10 09:12
Оценка:
Здравствуйте, _d_m_, Вы писали:

___>
___>select
___>    *
___>from
___>    _tt
___>where
___>    dbo._func(_tt.val) >= 3
___>;
___>


N = 3
Re[2]: Найти все непрерывные диапазоны длины N
От: Sinclair Россия https://github.com/evilguest/
Дата: 18.10.10 10:27
Оценка:
Здравствуйте, _FRED_, Вы писали:
_FR>Как использовать "уникальный идентификатор ID" — зачем он дан?
Использовать не обязательно.
_FR> Решение требуется, конечно же, без курсоров, запросом?
Да, конечно
S>>То есть, из таблички 1, 2, 3, 4, 6, 7, 8, 9 должны получаться вот такие ответы:

_FR>Данные — только целые числа? Или может быть что угодно + функция a-la GetNext(current)?

Можно считать, что целые числа.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Найти все непрерывные диапазоны длины N
От: ZAMUNDA Земля для жалоб и предложений
Дата: 18.10.10 10:40
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Что-то я стал туповат.

Ну вот... туповатое конешно... но вродь работае
  приборы и материалы
CREATE TABLE Ranges
    (Id INT    PRIMARY KEY)
    
GO
DELETE FROM Ranges

DECLARE @Id AS INT    

SET @Id = 0

WHILE @Id < 100
BEGIN
    INSERT INTO Ranges (Id) VALUES (@Id)    
    SET @Id = @Id + 1 + RAND() * 2
END


SELECT    *
FROM    dbo.Ranges r

DECLARE @N AS INT

SET @N = 3 -- <<< длина диапазона.

DECLARE    @TBL TABLE
    (Id INT    PRIMARY KEY)
DECLARE    @k AS INT

SET @k = 0

WHILE @k < @N 
BEGIN
    INSERT INTO @TBL (Id) VALUES (@k)
    SET @k = @k + 1
END

SELECT
    first_id = r.id
    ,t.Id+r.id
FROM
    (    SELECT
            r.Id
        FROM    
            Ranges AS r
        INNER JOIN
            (    SELECT
                     r_.Id
                    ,rid = r_.Id - t_.Id
                FROM
                    Ranges AS r_
                    ,@TBL AS t_
            ) AS rr
        ON    rr.rid = r.id
        GROUP BY r.Id
        HAVING COUNT(rr.rid) = @N
    ) AS r
    ,@TBL AS t
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
Re: Найти все непрерывные диапазоны длины N
От: Mr. None Россия http://mrnone.blogspot.com
Дата: 18.10.10 10:46
Оценка: 157 (7)
Здравствуйте, Sinclair, Вы писали:

S>Что-то я стал туповат. Задача:


S>Решение нужно для MS SQL (2005 и выше) и для Postgres.


Для всех:

SELECT n.number AS _beg, n.number + (N - 1) AS _end
FROM numbers n
WHERE (
 SELECT count(1) FROM numbers
 WHERE numbers.number Between n.number AND n.number + (N - 1)) = N;


Компьютер сделает всё, что вы ему скажете, но это может сильно отличаться от того, что вы имели в виду.
Re: Найти все непрерывные диапазоны длины N
От: MasterZiv СССР  
Дата: 18.10.10 11:10
Оценка: -1
On 18.10.2010 11:29, Sinclair wrote:

> 1. Есть таблица, в которой хранится, допустим, поле Value. И, допустим,

> уникальный идентификатор ID.
> 2. Есть задача: найти блок из N /непрерывных значений/.
> 3. Точнее, найти /все/ такие блоки. (Очевидно, достаточно найти голову или хвост
> блока — остальные значения получаются тривиально).

> Решение нужно для MS SQL (2005 и выше) и для Postgres.


Во-первых, нужен критерий сортировки обязательно для постановки такой задачи,
а во-вторых, задачу такую надо решать не на SQL, т.е. курсором. Бежишь
по курсору (отсортированному) и отмечаешь начало и конец диапазона.
Получается за O( N ).
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Найти все непрерывные диапазоны длины N
От: Sinclair Россия https://github.com/evilguest/
Дата: 18.10.10 11:33
Оценка:
Здравствуйте, MasterZiv, Вы писали:
MZ>Во-первых, нужен критерий сортировки обязательно для постановки такой задачи,
сортировка — по value.
MZ>а во-вторых, задачу такую надо решать не на SQL, т.е. курсором. Бежишь
MZ>по курсору (отсортированному) и отмечаешь начало и конец диапазона.
MZ>Получается за O( N ).
Не, курсором нельзя. Увы.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Найти все непрерывные диапазоны длины N
От: Flying Dutchman Украина  
Дата: 18.10.10 11:46
Оценка: 120 (3)
Здравствуйте, Sinclair, Вы писали:

S>Что-то я стал туповат. Задача:

S>1. Есть таблица, в которой хранится, допустим, поле Value. И, допустим, уникальный идентификатор ID.
S>2. Есть задача: найти блок из N непрерывных значений.
S>3. Точнее, найти все такие блоки. (Очевидно, достаточно найти голову или хвост блока — остальные значения получаются тривиально).

S>То есть, из таблички 1, 2, 3, 4, 6, 7, 8, 9 должны получаться вот такие ответы:

S>Для N = 1: сама табличка
S>Для N = 2: (1, 2), (2, 3), (3, 4), (6, 7), (7, 8), (8, 9)
S>Для N = 3: (1, 2, 3), (2, 3, 4), (6, 7, 8), (7, 8, 9)
S>Для N = 4: (1, 2, 3, 4), (6, 7, 8, 9)
S>Для N = 5 блоков нет

S>Решение нужно для MS SQL (2005 и выше) и для Postgres.


Это известная проблема в SQL известная как "Islands and Gaps". Решение для SQL Server приведено здесь.
Re[2]: Найти все непрерывные диапазоны длины N
От: Flying Dutchman Украина  
Дата: 18.10.10 11:53
Оценка:
Здравствуйте, Flying Dutchman, Вы писали:


FD>Это известная проблема в SQL известная как "Islands and Gaps". Решение для SQL Server приведено здесь.


Еще одна ссылка.
Re[2]: Найти все непрерывные диапазоны длины N
От: avpavlov  
Дата: 18.10.10 18:07
Оценка:
MN> SELECT count(1) FROM numbers

я бы даже написал select count(distinct numbers.number) и получил бы решение, которому пофиг на повторы значений.
Re[2]: Найти все непрерывные диапазоны длины N
От: Sinclair Россия https://github.com/evilguest/
Дата: 19.10.10 04:10
Оценка:
Здравствуйте, Flying Dutchman, Вы писали:

FD>Это известная проблема в SQL известная как "Islands and Gaps". Решение для SQL Server приведено здесь.

Это не совсем она.
Применение методов, описанных по приведённым вами ссылкам, даст ровно два диапазона длины 4 для таблицы из моего примера. А мне нужно уметь находить и более короткие диапазоны. Предельный случай — в непрерыыном списке длиной 101 должно найтись 100 диапазонов длины 2. А не один длиной 101.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.