Первый разрыв в auto_increment последовательности.

← →
Eraser © (2008-01-24 16:56) [0]

Добрый вечер.
Задали тут задачку такую на собеседовании "выбрать первый разрыв в auto_increment последовательности", СУБД MySql.
Кроме как перебором и сравнением текущего идентификатора с предыдущим на ум ничего не пришло.
Есть ли более красивое решение?

← →
Ega23 © (2008-01-24 16:58) [1]

первое, что пришло в голову:
сумма арифметической прогрессии + половинное деление.

← →
Павел Калугин © (2008-01-24 17:03) [2]

Есть на вскидку не вспомню. делается в один запрос

← →
Mystic © (2008-01-24 17:06) [3]

Первое что пришло в голову (сложность O(n^2)):

SELECT T1.ID + 1 AS FirstIdInGap, MIN(T2.ID) - T1.ID - 1 GapSize FROM IDS T1, IDS T2 WHERE 1=1 AND T1.ID < T2.ID GROUP BY T1.ID HAVING MIN(T2.ID) > T1.ID + 1

← →
Desdechado © (2008-01-24 17:10) [4]

MIN среди разницы двух множеств - исследуемого и полного.

← →
ANB © (2008-01-24 17:12) [5]

Ну или примерно так :

select * from X$files T
where not exists(select 1 from X$files T1 where T1.XF$Code = T.XF$Code - 1)
and T.XF$Code > 0

← →
Bless © (2008-01-24 17:24) [6]

SELECT t1.id FROM t1 LEFT JOIN t2 ON t2.id=t1.id-1 WHERE t2.id IS NULL

вернет все id, на которых начинаются пропуски. Правда я синтаксиса MySql не знаю, это T-SQL, но я думаю, перевести не трудно

← →
Bless © (2008-01-24 17:26) [7]

ой, у ANB по сути то же самое.

← →
Bless © (2008-01-24 17:28) [8]

ашипка
SELECT t1.id FROM myTable t1 LEFT JOIN myTable t2 ON t2.id=t1.id-1 WHERE t2.id IS NULL

думаю [6] это именно то, что нужно.. где то про способ с left join мне в литературе попадалось, но вспомнить никак не мог.

спасибо всем, удивляюсь своему тугодумству )

> Первый разрыв в auto_increment последовательности.
> Eraser © (24.01.08 16:56)

Интересно :) 6 лет назад народ такая же фигня интересовала. Вот из истории:

************************************************************
Определить первый свободный ID [D6, IB6.x, ] S_King © (04.12.01 10:18) Мастера помогите как определить в хранимой процедуре 1-й свободный №? Имеем таблицу с заполненым полем (1,2,4,5...),т.е. процедура должна выдать 3. ----------------------------------------------------------------------------- Vadim © (04.12.01 10:51) Только "криво" - перебором строк, или при помощи вспомогательной таблицы. Может, можно задачу по-другому поставить? ----------------------------------------------------------------------------- Владислав © (04.12.01 10:57) Сделай выборку, отсортированную по возрастанию. Пробегись по всем записям (ну не по всем, а до тех пор, пока не найдешь нужный номер) найди то, что нужно и используй. Только если ты хочешь получить уникальный номер, это не самый лучший вариант (а может быть и самый худший). Представь, что получиться, если два пользователя будут одновременно получать такой номер. ----------------------------------------------------------------------------- Yuvich (04.12.01 16:11) Если задача стоит именно так, то чтобы исключить ситуацию, описанную Владиславом ("Представь, что получиться, если два пользователя будут одновременно получать такой номер."), надо применить то что предлагает Vadim ("при помощи вспомогательной таблицы"). Вспомогательная таблица ведет список "дыр" в номерах. Как дыра образовалась - ее вставили в эту таблицу; как нужно заполнить дыру - прочитали из этой таблицы минимальный номер и удалили этот номер из этой таблицы. Все делается в триггерах и при блокировках "таблицы дыр", поэтому два пользователя никогда не прочитают один номер. Если используется метод исчисления, то нужно блокировать всю "целевую таблицу" - а это плохо для других пользователей, которые могут просто читать данные. ----------------------------------------------------------------------------- S_King © (04.12.01 16:43) Все это понятно, но может быть можно прокрутить цикл от 1 до max(Id) в хран. процедуре? P/S: Извените, может быть плохо формулирую вопрос. ----------------------------------------------------------------------------- Vadim © (04.12.01 16:52) Можно, но есть "но": при этом не гарантируется, что два пользователя одновременно не начнут "крутить цикл" и не наткнутся на одну и ту же "дыру" (я лично такую вероятность оцениваю как очень высокую). Если по условию задачи это допустимо - в путь, если нет, см. выше. ----------------------------------------------------------------------------- dmitryK (04.12.01 17:12) Если пользуешься SQL сервером, то логично решать такие задачи SQL-запросом, т.е. примерно так select min(t1.ID)+1 from tabX t1 left join tabX t2 on t1.ID=t2.ID+1 where where t2.ID is NULL будет работать все-таки быстрее чем программный перебор. А еще можно это реализовать с помощью журнала удаленных записей. Вешаешь триггер на удаление записи (бефоре) и сохраняешь все ID удаленных записей в отдельную таблицу. В таком случае при добавлении новых записей фактически нет потери времени на поиск (критично при одновременном добавлении большого количества записей). А что бы два пользователя не захватывали один ID поиск и добавление записи произодишь в одной транзакции.

> Вешаешь триггер на удаление записи (бефоре) и сохраняешь
> все ID удаленных записей в отдельную таблицу. В таком случае
> при добавлении новых записей фактически нет потери времени
> на поиск (критично при одновременном добавлении большого
> количества записей). А что бы два пользователя не захватывали
> один ID поиск и добавление записи произодишь в одной транзакции.
>

Хреновая идея. Как и идея применять сабж на практике (как тест - поканает). ИД должны генерится генераторами и плевать на дырки.
Есть узкий случай, когда поиск дырок необходим, но он с ИД не связан.

> ANB © (28.01.08 18:21) [11]

> Есть узкий случай, когда поиск дырок необходим, но он с
> ИД не связан.

Нормальные генераторы иногда и дырки умеют юзать.

Первый разрыв в auto_increment последовательности. Найти похожие ветки