|
Задавайте вопросы, мы ответим
Вы не зашли.
Страниц: 1
CREATE TABLE `tbl` (
`id` int(11) unsigned NOT NULL,
...
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
Таблица заполнена числами, нужно найти минимальное отсутствующее в ней.
Примеры:
0,1,2,4,5,9 - минимальное свободное: 3
4,1 - минимальное: 0
10,0,2 - минимальное: 1
Сейчас делаю полную выборку с сортировкой, и в приложении перебираю индексы:
int id = indexes[0];
for(size_t i=0;i<indexes.size();++i) {
if(id!=indexes[i]) break;
++id;
}
Можно это дело оптимизировать до одного запроса, без полной выборки всей таблицы и последующей обработки?
Неактивен
Создайте проиндексированную табличку t2 с числами от 1 до максимального и сделайте LEFT JOIN Вашей таблицы WHERE t2.num IS NULL limit 1;
Неактивен
А как создать заполненную таблицу?
Неактивен
Ну первое что идет в голову - таблицу с автоинкрементнрым полем сделать, вставить туда одно значение.
Далее нужное количество раз
Неактивен
Одним запросом сложновато будет.
Вот нашел на просторах:
SELECT t1.id+1 AS Missing
FROM tbl AS t1
LEFT JOIN tbl AS t2 ON t1.id+1 = t2.id
WHERE t2.id IS NULL
ORDER BY t1.id LIMIT 1;
Работает, но не соображу каким образом
Отредактированно gif-t (19.01.2017 16:48:31)
Неактивен
не работает, попробуйте для случая:
4,1 - минимальное: 0
deadka, дал правильный совет, только в вашем случае вспомогательная таблица должна быть заполнена начиная с 0. Это будет самый простой вариант.
Неактивен
Да, берутся все числа, увеличенные на 1. Т.е. поиск начинается с минимального в таблице.
Неактивен
vasya, совет правильный, только ума не приложу, как сделать одним запросом?
Неактивен
Неактивен
Мне кажется если union'ом прилепить к выборке 0, будет самый оптимальный рабочий вариант...
Неактивен
Спасибо, завтра попробую
Неактивен
Оцените пожалуйста данный запросик:
SELECT `Missing` FROM (SELECT id+1 AS Missing
FROM `tbl`
UNION
SELECT 0 AS id) AS t1
LEFT JOIN `tbl` AS t2 ON t1.Missing = t2.id
WHERE t2.id IS NULL
ORDER BY t1.Missing LIMIT 1;
Здесь выбираются все id, увеличенные на 1, и добавляется еще 0. Т.е. на таблице
10,3,4,5 будет 4,5,6,11,0. отсутствующие: 0,11
0,2,3,4 будет 1,3,4,5,0. отсутствующие: 1,5
1,2,6,4 будет 2,3,5,7,0. отсутствующие: 0,3,5,7
4,1 будет 5,2,0. отсутствующие: 0,2,5
Запрос LEFT JOIN'ом выберет все следующие от присутствующих отсутствующие числа. Далее сортировочка и выборка первого из них.
Неактивен
оценить с какой позиции?
если с т.з. производительности, то вариант, предложенный deadka, лучше
Неактивен
Да я вот думаю, что-то он действительно не шустрый. Но насчет отдельной теблицы я так и не понял. Я же не могу предсказать какое может быть максимальное значение? Там же могут быть миллионы. Не брать же размерность int'а!? И потом если я сгенерирую таблицу на 4294967296 строк, это, мне кажется, будет еще медленнее работать...
Я вижу еще 2 возможных решения:
- проход в процедуре.
- сделать доп. столбец, в котором хранить значения на 1 больше, и применить этот же алгоритм. Как я понял, затык именно в инкременте всех значений?
Неактивен
табличка на размерность int конечно не нужна
есть разные решения, например, отдельно хранить и вычислять нужное значение при изменении данных
для чего вообще нужна эта задача?
Неактивен
Страниц: 1
