nakts pārdomas
Uzdevums.
dots
2 tabulas
1) items
customer_id, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, amount
count(*) = n
2) item_groups
group_id, A1_from, A1_to, A2_from, A2_to, ..., A10_from, A10_to
count(*) = m
jāiegūst saraksts:
customer_id, group_id, sum(amount)
acīmredzamais risinājums:
SELECT customer_id, group_id, sum(amount)
FROM items, item_groups
WHERE A1 BETWEEN A1_from AND A1_to
AND A2 BETWEEN A2_from AND A2_to
..
AND A10 BETWEEN A10_from AND A10_to
GROUP BY customer_id, group_id;
Sarežģītība O(m*n), kas nav nekas neparasts (gadījums, kad katrs items iekrīt savā grupā). Sliktā lieta ir tā, ka ar šo SELECT arī o(n*m). Un pie lieliem n un m tas nemaz nav patīkami.
Bet kā ir, ja ņem vērā šo - count(distinct A1, A2, ... ,A10) = n/15 ?
Un to, ka konktrēts items iekritīs vienā vai divās grupās?
Man nāk prātā kaut kas uz šo pusi: n*logn + m*logm + distinct(A1..A10)*logm*logn
It īpaši, ja ņem vērā, ka pirmie n*logn + m*logm patiesībā n + m (indekss).