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).