Гуру-тест: хитрая задача на SQL (считайте, олимпиадная)

Форум Программирование Общие вопросы программирования (Dev)

1. fixin 4253 19.02.18 00:19 Сейчас в теме

Интересная задачка есть у меня для разминки Ваших мозгов. В моём ЖЖ её никто решить не смог, что странно, давайте среди 1сников устроим челлендж, докажем, что мы умнее сишников. Чтобы веселее было думать, добавляю приз 1 см.

Есть таблица проходов через проходную с полями: Сотрудник, Время (уникальное) , Вход (истина - вход, ложь - выход).

За день могут входить-выходить много раз.

Нужно SQL запросом выдать таблицу: Сотрудник, Время прихода, Время ухода, Секунд внутри. Запись таблицы по каждой последовательной паре приход - уход.

Фишка в том, что нельзя использовать Group By, агрегатные функции Min/Max/..., конструкцию IN. Нужно использовать только один запрос без временных таблиц и пользоваться только JOIN.

Думаем!

Вознаграждение за ответ

Сумма: 0 $m

Добавили:
fixin (1.00 $m)

Получили:

ildarovich (1 $m)

Показать полностью

Найденные решения

7. ildarovich 7865 20.02.18 01:18 Сейчас в теме +1 $m

Вот, кажется, подходящее решение:

ВЫБРАТЬ
	Приходы.Сотрудник,
	Приходы.Время КАК ВремяПрихода,
	Уходы.Время КАК ВремяУхода
ИЗ
	Дано КАК Приходы
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Дано КАК Уходы
		ПО Приходы.Сотрудник = Уходы.Сотрудник
			И Приходы.Время < Уходы.Время
		ЛЕВОЕ СОЕДИНЕНИЕ Дано КАК Вставки
		ПО (Вставки.Сотрудник = Приходы.Сотрудник)
			И Приходы.Время < Вставки.Время
			И (Вставки.Время < Уходы.Время)
ГДЕ
	Приходы.Вход
	И НЕ Уходы.Вход
	И Вставки.Время ЕСТЬ NULL

Показать

Вариант для проверки в консоли:

ВЫБРАТЬ
	"Иванов" КАК Сотрудник,
	ДАТАВРЕМЯ(2018, 2, 19, 23, 0, 0) КАК Время,
	ИСТИНА КАК Вход
ПОМЕСТИТЬ Дано

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Иванов",
	ДАТАВРЕМЯ(2018, 2, 19, 23, 59, 59),
	ЛОЖЬ

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Иванов",
	ДАТАВРЕМЯ(2018, 2, 20, 0, 0, 0),
	ИСТИНА

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Иванов",
	ДАТАВРЕМЯ(2018, 2, 20, 8, 0, 0),
	ЛОЖЬ
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Приходы.Сотрудник,
	Приходы.Время КАК ВремяПрихода,
	Уходы.Время КАК ВремяУхода
ИЗ
	Дано КАК Приходы
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Дано КАК Уходы
		ПО Приходы.Сотрудник = Уходы.Сотрудник
			И Приходы.Время < Уходы.Время
		ЛЕВОЕ СОЕДИНЕНИЕ Дано КАК Вставки
		ПО (Вставки.Сотрудник = Приходы.Сотрудник)
			И Приходы.Время < Вставки.Время
			И (Вставки.Время < Уходы.Время)
ГДЕ
	Приходы.Вход
	И НЕ Уходы.Вход
	И Вставки.Время ЕСТЬ NULL

Показать

Ответить

Остальные ответы

Подписаться на ответы Инфостарт бот

Свернуть все

2. Cooler 22 19.02.18 00:21 Сейчас в теме

(1)

добавляю приз 1 см

Малавата будет!

3. fixin 4253 19.02.18 07:01 Сейчас в теме

(2) да ну? Ггг

4. fessya 19.02.18 08:51 Сейчас в теме

как-то так?

sel ect 
	table_in.id as id,
	table_in.time as time_in,
	table_out.time as time_out,
	datediff(ss, table_in.time, table_out.time) AS datedif

fr om timetable as table_in	
left join timetable as table_out 
	on table_out.id = table_in.id
	and table_out.state = 0
	and table_out.time = (
							select top 1
								t.time
							fr om timetable as t
							where t.state = 0
								and t.id = table_in.id
								and t.time > table_in.time
							order by t.time
						  )

where table_in.state = 1

Показать

6. fixin 4253 19.02.18 19:18 Сейчас в теме

(4) (5) нет, никаких селект из селект, чисто используя JOIN

5. fessya 19.02.18 09:04 Сейчас в теме

Ну или так, вообще без joina

sel ect
t.id,
t.time_in,
t.time_out,
datediff(ss, t.time_in, t.time_out) AS datedif
fr om (
	sel ect 
		table_in.id as id,
		table_in.time as time_in,
		(select top 1
			t.time
		 fr om timetable as t
		 where t.state = 0
			and t.id = table_in.id
			and t.time > table_in.time
		 order by t.time) as time_out
fr om timetable as table_in	
wh ere table_in.state = 1) as t

Показать

7. ildarovich 7865 20.02.18 01:18 Сейчас в теме +1 $m

Вот, кажется, подходящее решение:

ВЫБРАТЬ
	Приходы.Сотрудник,
	Приходы.Время КАК ВремяПрихода,
	Уходы.Время КАК ВремяУхода
ИЗ
	Дано КАК Приходы
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Дано КАК Уходы
		ПО Приходы.Сотрудник = Уходы.Сотрудник
			И Приходы.Время < Уходы.Время
		ЛЕВОЕ СОЕДИНЕНИЕ Дано КАК Вставки
		ПО (Вставки.Сотрудник = Приходы.Сотрудник)
			И Приходы.Время < Вставки.Время
			И (Вставки.Время < Уходы.Время)
ГДЕ
	Приходы.Вход
	И НЕ Уходы.Вход
	И Вставки.Время ЕСТЬ NULL

Показать

Вариант для проверки в консоли:

ВЫБРАТЬ
	"Иванов" КАК Сотрудник,
	ДАТАВРЕМЯ(2018, 2, 19, 23, 0, 0) КАК Время,
	ИСТИНА КАК Вход
ПОМЕСТИТЬ Дано

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Иванов",
	ДАТАВРЕМЯ(2018, 2, 19, 23, 59, 59),
	ЛОЖЬ

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Иванов",
	ДАТАВРЕМЯ(2018, 2, 20, 0, 0, 0),
	ИСТИНА

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Иванов",
	ДАТАВРЕМЯ(2018, 2, 20, 8, 0, 0),
	ЛОЖЬ
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Приходы.Сотрудник,
	Приходы.Время КАК ВремяПрихода,
	Уходы.Время КАК ВремяУхода
ИЗ
	Дано КАК Приходы
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Дано КАК Уходы
		ПО Приходы.Сотрудник = Уходы.Сотрудник
			И Приходы.Время < Уходы.Время
		ЛЕВОЕ СОЕДИНЕНИЕ Дано КАК Вставки
		ПО (Вставки.Сотрудник = Приходы.Сотрудник)
			И Приходы.Время < Вставки.Время
			И (Вставки.Время < Уходы.Время)
ГДЕ
	Приходы.Вход
	И НЕ Уходы.Вход
	И Вставки.Время ЕСТЬ NULL

Показать

Ответить

8. fessya 20.02.18 06:58 Сейчас в теме

(7) Классное решение, мне понравилось.
Интересно оно будет быстрее чем "обычное" с группировками или нет?

10. nvv1970 20.02.18 08:15 Сейчас в теме

(8) тоже задумался над этим.
Если будет быстрее, то можно все срезы переделывать...
Пока есть сомнения, но как знать, как знать...
Побежал тестить))))
Но дело неприятно попахивает nested loop'ом ((

11. fessya 20.02.18 12:33 Сейчас в теме

(10) ну ты это, держи в курсе, у меня тоже есть куча мест где это может пригодится. Только проверять надо хотя-бы на 1кк строк.

13. nvv1970 20.02.18 20:47 Сейчас в теме

(11) в том числе, но не только.
Разные выборки - разные статистики - разные оценки - разные планы.
У меня меньше таблиц и не бывает))) базы измеряю сотнями гигов))
Сорри, ещё не добежал.

16. nvv1970 20.02.18 22:55 Сейчас в теме

Поржал сам с себя...
Какой тут NL? Не он страшен. Практически декартово произведение. Запрос вообще не работоспособен.
Взял навскидку табличку на 270к записей... и все... ssd стало жалко )

Чтобы примерить эту Идею - то я ведь правильно все понял?
1. Взяли все до @даты (табл Т1)
2.Присоединили все между периодом (Т1) и @датой - и исключили все что примоединилось
Результат в количестве и процентах на картинке(HM).
На второй картинке (NL) добавлен индекс по Field+Period.

PS: по сабжу - олимпиадные задачи такие олимпиадные. Нет чтобы соревноваться по оптимизации, краткости, интересных подходах. ))

Прикрепленные файлы:

14. alex_sh2008 4 20.02.18 21:09 Сейчас в теме

(8) В общем то с группировками будет быстрее. Можно это запрос ограничить по времени выборки, но то же вряд ли будет быстрее.

15. fessya 20.02.18 22:41 Сейчас в теме

(14) ну вообще если предположить что между входом и выходом бывает, например, не больше суток, то должно быть вообще шустро.

17. alex_sh2008 4 20.02.18 23:45 Сейчас в теме

(15) ну или так, на вскидку:
sel ect tin.id, tin.time as time_in, tout.time as time_out
fr om table as tin
left out join table as tout on tout.state = 0 and tin.id = tout.id and tin.time < tout.time
where tin.state = 1

9. Dream_kz 129 20.02.18 08:03 Сейчас в теме

(7) Блин, пытался придумать алгоритм выявления неправильных записей, а оказывается все просто, если между временем входа и временем выхода есть промежуточные состояния, то такие записи не верны. Браво

18. fixin 4253 26.02.18 19:35 Сейчас в теме

(7) да, именно этот вариант и был задуман! Молодцом!

12. herfis 499 20.02.18 12:46 Сейчас в теме

Только реальные задачи на вход-выход лучше на стейт-машинах решать.

Оставьте свое сообщение

E-mail: