Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Интересная задачка. Поиск отсутствующего уникального значения.  (Прочитано 33052 раз)
0 Пользователей и 1 Гость смотрят эту тему.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« : 16-06-2008 20:09 » 

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

Такую задачку с тем же академическим интересом я решил в далеком 2002-м и записал на бумагу, а тут мне эта задача попалась и я обнаружил в ней ошибку. Стал разбираться детальнее и оказалось, что не все так просто...

Данную задачку я решаю в MySQL, но думаю, что она примерно одинаково выглядит в любой другой СУБД.



Предположим, что есть некая таблица и в ней столбец, содержащий уникальные целые числа.
Код: (SQL)
CREATE TABLE test (id TINYINT UNSIGNED NOT NULL PRIMARY KEY); -- беззнаковое целое размеров один байт

Таблица может иметь три ключевых состояния:
1. пустая;
2. полная (значения id покрывают весь диапазон типа);
3. промежуточное состояние (в нее еще что-то можно вставить без ошибки).

Нужно сделать такой запрос (можно и не один запрос, а целый SQL-блок), который даст на выходе либо одно из свободных чисел, либо как-то сигнализирует об ошибке.



Это был первый вариант решения.
Код: (SQL)
SELECT (t1.id + 1) res
INTO id
FROM test t1
        LEFT JOIN test t2 ON (t2.id = t1.id + 1)
WHERE t2.id IS NULL
HAVING res BETWEEN 0 AND 255
LIMIT 1;
Если убрать "LIMIT 1", то запрос вернет начальные значения в пустующих окнах диапазона.
Особенности запроса:
1. таблица пуста - запрос ничего не вернет;
2. таблица не пуста, но других окон, кроме начинающегося с ноля, нет - вернет 256, которое отвергнет условие в HAVING, и в итоге - ничего.
3. таблица полная - аналогично п.2.

Попробуем в другую сторону...
Код: (SQL)
SELECT (t1.id - 1) res
INTO id
FROM test t1
        LEFT JOIN test t2 ON (t2.id = t1.id - 1)
WHERE t2.id IS NULL
HAVING res BETWEEN 0 AND 255
LIMIT 1;
Теперь болезнь немного изменилась: таже трабла с диапазоном - кончающимся значением 255.

Логично было бы состыковать оба запроса по UNION. Это решает проблему п.2., но не помогает различить ситуации, когда таблица пустая или полная. Решаю усложнением кода - переходом от одиночного оператора к блоку.

Код: (SQL)
DECLARE id INT;

SELECT COUNT(*)
INTO id
FROM test;

IF id = 0 THEN
        SET id = 1;
ELSEIF id = 256 THEN
        SET id = NULL;
ELSE
        SELECT (t1.id - 1) res
        INTO id
        FROM test t1
                LEFT JOIN test t2 ON (t2.id = t1.id - 1)
        WHERE t2.id IS NULL
        HAVING res BETWEEN 0 AND 255
        LIMIT 1;

        IF id IS NULL THEN
                SELECT (t1.id + 1) res
                INTO id
                FROM test t1
                        LEFT JOIN test t2 ON (t2.id = t1.id + 1)
                WHERE t2.id IS NULL
                HAVING res BETWEEN 0 AND 255
                LIMIT 1;
        END IF;
END IF;



А может можно как-нибудь проще решить задачу?
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #1 : 17-06-2008 03:17 » 

Для оракла пишу наугад, днем проверю, если не забуду.
Select min(t.id+1) from test t where not exists (Select 1 from test tt where tt.id=t.id+1) and t.id<254
Записан

Удачного всем кодинга! -=x[PooH]x=-
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 17-06-2008 03:30 » 

PooH, у тебя точно тот же алгоритм, только через подзапрос (MySQL до 4.1 не поддерживала подзапросов и надо было извращаться с LEFT JOIN). Траблы остаются теже: пустая таблица и окно с началом в ноле.

t.id<254

Наверно все таки - 255...
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #3 : 17-06-2008 06:50 » 

... ну ё моё =) список ограничений в студию! =)
Записан

Удачного всем кодинга! -=x[PooH]x=-
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 17-06-2008 07:01 » 

Улыбаюсь Никаких ограничений - просто хотелось бы узнать о других алгоритмах. И твой, и мой запросы приведутся оптимизатором к одному виду.
Кстати, у него есть серьезный недостаток - одна "таблица" пойдет в full scan. Для примера я выбрал очень маленький тип, ну, а если будет что-то по больше, то скорость по мере заполнения таблицы будет быстро падать.



Смысл в этой задаче все же есть - использование малых типов дает выйгрыш, если его потом надо использовать в нескольких индексах в нескольких таблицах: индекс меньше, скорость поиска выше. Только вот выделение id какое-то гиморное получается...
« Последнее редактирование: 17-06-2008 07:04 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #5 : 17-06-2008 07:03 » 

Цитата
если будет что-то по больше, то скорость по мере заполнения таблицы будет быстро падать
можно еще придумать вариант с аналитическим функциями - просмотр вперед/назад
Записан

Удачного всем кодинга! -=x[PooH]x=-
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 17-06-2008 09:35 » 

Академические задачки и full-scan - вещи несовместимые Улыбаюсь Индекса таблицы как математического понятия нет.

А вообще разрывы в упорядоченной последовательности целых чисел можно определять через разность соседних номеров. Где она больше 1, там разрыв. И на сколько она больше 1, столько там свободных мест. Но конец таблицы это не обрабатывает, всегда придётся задавать максимум.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #7 : 17-06-2008 10:40 » 

Если диапазон чисел 0-255 (если диапазон больше, то кол-во единиц в CUBE д.б. равно спепени 2), то в оракле можно сделать "финт ушами" =)
Код:
SELECT MIN(s.cnt)
  FROM x_test t,
       (SELECT 1, (row_number() over(ORDER BY 1)) - 1 cnt
          FROM dual
         GROUP BY CUBE(1, 1, 1, 1, 1, 1, 1, 1)) s
 WHERE t.id(+) = s.cnt
 AND t.ID IS NULL

ну или
Код:
SELECT MIN(s.cnt)
  FROM x_test t,
       (SELECT xcnt - 1 cnt
          FROM (SELECT LEVEL xcnt FROM dual CONNECT BY LEVEL < 256)) s
 WHERE t.id(+) = s.cnt
       AND t.id IS NULL
« Последнее редактирование: 17-06-2008 11:31 от PooH » Записан

Удачного всем кодинга! -=x[PooH]x=-
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #8 : 17-06-2008 12:22 » 

dimka, любая академическая задачка имеет шанс стать практической Ага

Как ты видишь подобное в SQL? Есть идеи?

PooH, зачем порезал - интересно было, хоть и не совсем то. А последнее я пока не понял - нужно мозг подключить...  Здесь была моя ладья...
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #9 : 17-06-2008 12:54 » 

RXL, там явный косяк был... =)
а про последнее... там генерится ряд натуральных цисел и к нему приклеиваются существующие... ну и соответственно находится наименьшее натуральное для которого нет пары.
Записан

Удачного всем кодинга! -=x[PooH]x=-
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #10 : 17-06-2008 14:04 » 

Цитата: RXL
Как ты видишь подобное в SQL? Есть идеи?
Я эту или очень близкую к ней задачу решал в 2003-м году именно через разности. Увы, сейчас не могу выделить пару часиков, чтобы восстановить. Но сразу предупреждаю, что запрос там был далёк от оптимальности и избегания full scan.

Можно посчитать разности между номером текущей строки и ID (считая, что номера строк и ID - целые числа от 1 до N). Для монотонно возрастающих номеров разность будет фиксированной (сначала 0). В месте первого разрыва она возрастает и потом опять сохраняет своё значение до следующего разрыва.
Код:
ID RowNumber Diff
1  1         0
2  2         0
4  3         1
5  4         1
6  5         1
9  6         3
10 7         3
Это была центральная идея решения. Затем группировки по разностям и определение диапазонов, заполненных номерами, через min и max для группы... Потом не помню...

Идея была почерпнута из курса "Вычислительной математики", когда там аналитические производные заменялись на численные разности, и на этом основании что-то там искалось. Положительное или отрицательное постоянное значение первой производной означает равномерное возрастание или убывание значения функции ID(RowNumber).

На код сейчас нет времени.
« Последнее редактирование: 17-06-2008 14:15 от dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #11 : 17-06-2008 16:15 » 

PooH, очень интересно.

Упростил выражение:
Код: (SQL)
SELECT LEVEL - 1 cnt FROM dual CONNECT BY LEVEL < 257
Одним подзапросом меньше.

Вариант с CUBE работает медленнее. Для генерации 256 значений потрачено 450мс, а на 65536 - более двух минут (не стал ждать).

Переписал немного в привычную форму с LEFT JOIN. Знаю, что функционал у нее в Oracle меньше, чем у конструкции "(+)", но это зато переносимо и логически понятнее.

Код: (SQL)
SELECT MIN(s.cnt)
FROM (SELECT LEVEL - 1 cnt FROM DUAL CONNECT BY LEVEL < 257) s
        LEFT JOIN test t ON (t.id = s.cnt)
WHERE t.id IS NULL

-- или

SELECT MIN(s.cnt)
FROM test t, (SELECT LEVEL - 1 cnt FROM DUAL CONNECT BY LEVEL < 257) s
WHERE t.id (+) = s.cnt
        AND t.id IS NULL

Запрос сильно зависим по скорости от предела диапазона: для 0..255 - мгновенно, для 0..65535 - 0.4-0.6 с, на больший диапазон задумывается надолго. Видимо, первый запрос выполняется полностью, прежде чем начнутся поиски строк в таблице test.
Очень интересный вариант. Осталось найти ему аналог в MySQL...

dimka, пока читаю...
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #12 : 17-06-2008 16:49 » 

dimka, вот реализация твоей идеи. Нужно найти только одно любое значение, не присутствующее в таблице.

Код: (SQL)
SELECT s.rn
FROM (
        SELECT t.id, ROWNUM - 1 rn
        FROM test t
        ORDER BY t.id
) s
WHERE s.id != s.rn
        AND ROWNUM = 1

Работает Улыбаюсь Но не обрабатывает диапазон (MAX(t.ID) + 1)...255 и пустую таблицу. Значит, требуется дополнительный запрос и условие. При попытке объединить запросы по UNION Oracle мне заявил, что типы столбцов в таблицах не совпадают (NULL и NUMBER).
Кроме того, есть затраты на full scan и сортировку. На таблице из 4 значений это не заметно совсем.

Надо подумать еще...
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #13 : 17-06-2008 17:09 » 

Самым тупым и скоростным способом стало создание таблицы из одного столбца, содержащей все значения ID, с последующим LEFT JOIN с таблицей test. Для 2^8 значений - пустяк, для 2^16 - 128кБ минимум. Тут тоже возможны вариации: сортировать или нет перед объединением (соотв. - нужен или нет первичный ключ).
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #14 : 18-06-2008 03:14 » 

Тут фишки есть - сам по себе запрос с connect by level возвращает не более 100 значений, чтобы вернулись все нужен внешний запрос. Ты правильно изменил - я его оставил чтоб по в глаза бросился Ага. Для генерации ряда есть менее надежный способ - выборка из большой системной таблицы, например, all_objects.

Чтобы совпадали типы нужно явное преобразование to_number(null)
Записан

Удачного всем кодинга! -=x[PooH]x=-
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #15 : 18-06-2008 03:16 » 

Можно сделать функцию для генерации таблицы в памяти.

Вот тема на sql.ru  про генерацию ряда чисел: http://www.sql.ru/forum/actualthread.aspx?bid=3&tid=34821&pg=1
« Последнее редактирование: 18-06-2008 05:05 от PooH » Записан

Удачного всем кодинга! -=x[PooH]x=-
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #16 : 18-06-2008 04:55 » 

А может следует делать всё наоборот?
Заполнить таблицу свободными номерами и по мере использования их удалять? Дёшево и сердито. просто берёшь любой ну или минимальный.
Записан

Странно всё это....
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #17 : 18-06-2008 05:00 » 

вот еще вариант решения (вроде работает)
Код:
SELECT nvl(MIN(tt.id) + 1, 0) res
  FROM x_test t,
       (SELECT -1 id
          FROM dual
        UNION
        SELECT id
          FROM x_test
        UNION
        SELECT 255 FROM dual) tt
 WHERE t.id(+) = tt.id + 1
       AND t.id IS NULL
Записан

Удачного всем кодинга! -=x[PooH]x=-
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #18 : 18-06-2008 06:12 » 

в продолжение идеи PooH
Код:
SELECT t.id res
  FROM        (SELECT id
          FROM xtest
        UNION
        SELECT max(id)+1
          FROM x_test
       ) t,
       (SELECT min(id)-1 id
          FROM xtest
        UNION
        SELECT id
          FROM x_test
       ) tt
 WHERE (t.id- tt.id)>2
« Последнее редактирование: 18-06-2008 06:14 от Sla » Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #19 : 18-06-2008 07:19 » 

Sla, если в таблице только 1,2 то возвращается 3, а должно 0
Если в таблице только одно значение, то запрос ничего не возвращает.
Записан

Удачного всем кодинга! -=x[PooH]x=-
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #20 : 18-06-2008 07:36 » 

PooH, я не проверял, но чуть попозже проверю
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #21 : 18-06-2008 08:58 » 

Мне кажется, что поиск отсутствующих значений всегда означает перебор всех имеющихся. Каким образом можно избежать full scan (исключая случай обработки самого большого или самого маленького значения)?
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #22 : 18-06-2008 09:09 » 

 а идея была следующая
создать две псевдотаблицы, а потом их связать
в Oracle их можно связать по rownum
усложнив запрос
Код:
SELECT t.id res
  FROM  ( select rownum r, id
      from     (SELECT id
          FROM xtest
        UNION
        SELECT max(id)+1
          FROM x_test
       ) ) t,
       (select rownum r, id
         from (SELECT min(id)-1 id
          FROM xtest
        UNION
        SELECT id
          FROM x_test
       )) tt
 WHERE t.r=tt.r and (t.id- tt.id)>2
если не запутался в скобках Улыбаюсь

Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #23 : 18-06-2008 09:54 » 

Sla, когда в таблице только одно значение у тебя (t.id- tt.id)>2 не выполнится... также использую min и max у тебя не обозначен диапазон, то есть, если в таблице минимальное значение например 10, у тебя 0 не вернется в запросе.
Записан

Удачного всем кодинга! -=x[PooH]x=-
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #24 : 18-06-2008 10:25 » 

согласен, не дочитал условия
Поиск отсутствующего уникального значения.

нету оракла под рукой, есть mssql
а тем более 10-ки
как я понял
SELECT LEVEL xcnt FROM dual ...
генерит порядковые номера

ушел мысль думать Улыбаюсь


Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #25 : 18-06-2008 10:36 » 

Sla, хм... ну по поставленным условиям 0 и не обязан возвращаться, если минимальное в таблице 10... а вот если в таблице только одно значение (причем есть разница 0 это или не 0, я об это споткнулся), то Min-1 и Max+1 не пройдут по условиям
Записан

Удачного всем кодинга! -=x[PooH]x=-
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #26 : 18-06-2008 11:27 » 

Код:
select tt.id from
  test2 tt
  left join test1 t on (tt.id=t.id)
where t.id is null

test2 - сгенерированная таблица от необходимого минимального значения до максимального значения в test1
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #27 : 18-06-2008 18:36 » 

Можно сделать функцию для генерации таблицы в памяти.

Вот тема на sql.ru  про генерацию ряда чисел: http://www.sql.ru/forum/actualthread.aspx?bid=3&tid=34821&pg=1
Интересная тема. Жаль, что ссылки на oracle magazine и т.п. говорят not found...

Вот еще одна загадочная штука Oracle из той темы:
Код: (SQL)
SELECT Y FROM DUAL
MODEL
        DIMENSION BY (0 AS X) MEASURES (0 AS Y)
        RULES ITERATE (65535)
        (Y[ITERATION_NUMBER + 1] = ITERATION_NUMBER + 1);

Выдает последовательность 0..65535 за 1 с.
Скорость MODEL не линейная: 100к значений выдает за 2-3 секунды, 200к - почти минуту.



LogRus, можно, но тогда идут расходы на содержание таблицы. Когда база промышленного масштаба, то лишний "метр" не жалко, а вообще - жалко. Ну, и просто не кошерный способ - слишком легко Ага



PooH, запрос работает Улыбаюсь

Код:
SELECT nvl(MIN(tt.id) + 1, 0) res
  FROM x_test t,
       (SELECT -1 id
          FROM dual
        UNION
        SELECT id
          FROM x_test
        UNION
        SELECT 255 FROM dual) tt
 WHERE t.id(+) = tt.id + 1
       AND t.id IS NULL


На таблице, где первое значение - 1 (377 разрозненных значений), потрачено 16 мс.
На таблице, где первое - 20000 (332865 значений), потрачено 2 с.
На пустой странице сработало за 16 мс.
На почти полной (0..65534) - 125 мс, на полностью полной - 216 мс.

Это оказался самый скоростной запрос для умеренных по размеру таблиц (~100000 строк).

Одна странность: таблицы с PK для id обрабатываются в 2-2.5 раза медленнее, чем таблицы без индекса.

« Последнее редактирование: 18-06-2008 18:56 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #28 : 19-06-2008 03:07 » 

Думаю время тратится на чтение индекса, надо план смотреть. Думаю на такой таблице индекс только мешает. Ещё не помешало бы статистику по таблице собрать.
Записан

Удачного всем кодинга! -=x[PooH]x=-
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #29 : 19-06-2008 03:39 » 

По плану индексы посмотреть забыл, но по другим вариантам смотрел. Статистика вдвое снижает стоимость (COST) full scan.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines