План атаки
- Проецируйте каждый диапазон элементов на числовую линию, «отбрасывая тень», где она находится
- Проанализируйте проекцию, чтобы найти ребра, а затем пронумеруйте каждыйнепрерывная «тень» в виде столбца
- Сопоставьте каждый элемент с номером его столбца, затем проанализируйте карту
Сначала создайте «числовую строку» из целых чисел, охватывающую доменвходных данных (ниже 0-255)
create table integers as
select
bit1.n+bit2.n+bit3.n+bit4.n+bit5.n+bit6.n+bit7.n+bit8.n as n
from
(select 0 n union all select 1) bit1
cross join (select 0 n union all select 2) bit2
cross join (select 0 n union all select 4) bit3
cross join (select 0 n union all select 8) bit4
cross join (select 0 n union all select 16) bit5
cross join (select 0 n union all select 32) bit6
cross join (select 0 n union all select 64) bit7
cross join (select 0 n union all select 128) bit8
;
Затем для каждого section_id возьмите проекцию диапазона (abs_left, abs_right) на числовую строку и сохраните во временной таблице
create table temp_item_distribution (
is_start_of_column int
, column_number int
, primary key (section_id, n)
) as
select
section_id
, n
, sum(is_match) as matches
from
(
select
section_id
, n
, 0 as is_match
from
(select distinct section_id from items) s
cross join integers
union all
select
section_id
, n
, 1
from
items i
inner join integers z
on z.n between i.abs_left and i.abs_right
) t
group by
section_id
, n;
Теперь найдите и пометьте крайний левый край каждого столбца
update
temp_item_distribution r
left join temp_item_distribution l
on l.section_id = r.section_id
and l.n = r.n - 1
set
r.is_start_of_column = case when coalesce(l.matches, 0) = 0 and r.matches > 0 then 1 else 0 end
;
Теперь, используя эту метку, мы можем нумеровать и пометить сами столбцы
update
temp_item_distribution t
inner join (
select
r.section_id
, r.n
, sum(l.is_start_of_column) as column_number
from
temp_item_distribution l
inner join temp_item_distribution r
on l.section_id = r.section_id
and l.n <= r.n
group by
r.section_id
, r.n
) s
on t.section_id = s.section_id
and t.n = s.n
set
t.column_number = s.column_number
where
t.matches > 0
;
Теперь мы можем отобразить элементы обратно на столбцы
create table temp_items_in_columns as
select
i.section_id
, i.abs_left
, i.abs_right
, t.column_number
from
items i
inner join temp_item_distribution t
on i.section_id = t.section_id
and i.abs_left = t.n
;
Теперь мы можем ответить на вопрос (..!)
select
section_id
, max(column_number) as number_of_columns
from
temp_items_in_columns
group by
section_id
;
+------------+-------------------+
| section_id | number_of_columns |
+------------+-------------------+
| 1 | 3 |
| 3 | 8 |
| 4 | 7 |
+------------+-------------------+
И края:
select
section_id
, column_number
, min(abs_left) as far_left
, round(avg(abs_left) - stddev(abs_left),1) as 1_sigma_left
, round(avg(abs_right) + stddev(abs_right),1) as 1_sigma_right
, max(abs_right) as far_right
from
temp_items_in_columns
group by
section_id
, column_number
;
+------------+---------------+----------+--------------+---------------+-----------+
| section_id | column_number | far_left | 1_sigma_left | 1_sigma_right | far_right |
+------------+---------------+----------+--------------+---------------+-----------+
| 1 | 1 | 0 | 0.0 | 4.0 | 4 |
| 1 | 2 | 8 | 8.0 | 12.0 | 12 |
| 1 | 3 | 40 | 40.3 | 63.9 | 65 |
| 3 | 1 | 0 | 0.0 | 15.0 | 15 |
| 3 | 2 | 58 | 58.6 | 73.4 | 73 |
| 3 | 3 | 82 | 82.0 | 87.0 | 87 |
| 3 | 4 | 96 | 96.0 | 104.0 | 104 |
| 3 | 5 | 114 | 114.0 | 122.0 | 122 |
| 3 | 6 | 129 | 129.0 | 137.0 | 137 |
| 3 | 7 | 143 | 143.0 | 151.0 | 151 |
| 3 | 8 | 165 | 165.0 | 175.0 | 175 |
| 4 | 1 | 4 | 4.2 | 39.9 | 43 |
| 4 | 2 | 55 | 55.0 | 64.0 | 64 |
| 4 | 3 | 70 | 71.8 | 84.4 | 84 |
| 4 | 4 | 93 | 93.4 | 101.1 | 101 |
| 4 | 5 | 104 | 104.0 | 116.0 | 116 |
| 4 | 6 | 123 | 123.0 | 130.0 | 130 |
| 4 | 7 | 139 | 138.4 | 147.0 | 147 |
+------------+---------------+----------+--------------+---------------+-----------+
(с использованием интервала 1 стандартного отклонения, который составляет около 68% для нормальногоразмером взносов.Смотри: http://en.wikipedia.org/wiki/Standard_deviation)