Модуль: Математическая шкатулка_Обучение


10. Stat_2-10 Поиск медианы по группам чисел


 Stat_2-1_ Поиск медианы по группам чисел
Задача 52155

Постановка проблемы
Существуют статистические характеристики выборки данных:
  • объем выборки,
  • размах выборки, максимальное и минимальное значения,
  • среднее арифметическое,
  • мода,
  • медиана
В этой тетради рассмотрим вопросы, связанные с определением медианы выборки.
По определению, для нахождения медианы надо:
  • отсортировать выборку (например, по возрастанию)
  • выбрать средний (по индексу) элемент. Если в выборке четное кол-во элементов, то можно:
    • взять первый из второй половины (максимальный)
    • взять последний из первой половины (минимальный)
    • проводить сортировку без последнего/первого элемента
    • и т.п., только так, чтобы медиана была элементом выборки 
Если N - объём выборки, то :
  • трудоемкость такого процесса будет \(O(N\cdot logN)\)
  • при добавлении элементов в выборку необходимо  проводить новую сортировку
  • не видно динамики  изменения медианы (если выборка имеет временной характер)

А как искали медиану "без компьютеров" 
Опишем один из способов. 
  • Выборку разбивали на группы длины m (слева направо, m - нечётное число, обычно брали m=5). 
  • Для каждой группы находили медиан и записывали его в новый массив (список). 
  • Для последней группы, в которой могло оказаться чётное количество чисел,
    применяли "договоренность" (будем считать, что это первое число из второй половины)
  • Операцию повторяли для нового массива медиан
Пример.
Положим m=5 и определим медиану для набора
909, 4, 4, 7, 9, 12, 77, 45, 1, 4, 90, 65, 3, 2, 22, 40, 65, 80, 93, 21, 100, 9, 12, 20, 3
  • 909, 4, 4, 7, 9 -> 7 ; 12, 77, 45, 1, 4 -> 12;   90, 65, 3, 2, 22 -> 22;  40, 65, 80, 93, 21 -> 65; 100, 9, 12, 20, 3 -> 12
    следовательно, после 1 прохода получим последовательность  77,12,22,65,12
  • 77,12,22,65,12 -> 22 
Таким образом, мы нашли медиан = 22. Настоящая медиана  равна 20, а число 22 стоит  в отсортированном массиве на две позиции правее.
Можно также заметить, что если бы мы добавили к массиву число  a  (a>22), то оно бы и стало медианой.
На практике "хвост"  добавляли к последней  группе.

Почему этот способ может быть интересен сейчас?
Обычно исследуется выборка случайной величины, значит медиана это тоже случайная величина.
Тогда точное значение медианы выборки можно заменить некоторой оценкой этой величины. 
Это и делает приведенный алгоритм. Оценим его трудоемкость.
Пусть N - объём выборки, M - длина группы.
Для удобства рассчётов будем считать, что N=Mk
Нахождение медианы через сортировку массива можно оценить как \(O(N\cdot logN)=O(M^k\cdot k\cdot logM)\)
Оценим сложность "алгоритма по группам", положив сложность поиска медианы группы в \(M\cdot logM\) 
  • Алгоритм по группам на 1 этапе даст сложность в \(\frac{N}{M}\cdot (M\cdot logM)=N\cdot logM=M^k\cdot logM\) 
    и размер массива сократиться до \(\frac{N}{M}\)
  • на втором этапе получим сложность в \(\frac{N}{M}\cdot logM=M^{k-1}\cdot logM\) 
  • Общая сложность  будет равна \( logM\cdot (M^k+M^{k-1}+\cdots +1)= logM\cdot\frac{M^{k+1}-1}{M-1}=logM\cdot\frac{M\cdot N-1}{M-1}\)
    Таким образом сложность можно оценить как \(\frac{M}{M-1}\cdot logM\cdot N\ \ \ \ \ \ (1)\)
Можно считать, что "алгоритм по группам" имеет сложность O(N) и при больших N будет эффективнее,
чем поиск медианы через сортировку.
Далее опишем условие задачи, алгоритм поиска и сравним различные результаты.  
Если оценить формулу (1), то наименьшее её значение будет при M=3, однако реальные подсчеты дадут другое число.

Stat_2-01 Оценка значения медианы методом разбиения на группы
2-01  Оценка значения медианы методом разбиения на группы

Эта задача требует многократного поиска медианы в списке положительных целых чисел, пока не останется одно число - оценка медианы набора.
Дан набор из N натуральных чисел и нечётное натуральное число M - размер группы для разбиения. 
Необходимо написать функцию, выполняющую следующий алгоритм:
  • разбить список на N//M групп по M элементов в каждой (в последней группе будет M+N%M элементов)
  • для каждой группы, используя сортировку, найти "точную" медиану (в "чётных" группах брать максимальное значение)
  • из полученных медиан составить новый список и вернуть его
Используя рекусию, получить оценку медианы 
Ваша задача написать функцию, которая получает значение M, список с числами и возвращает оценку медианы
В табл. 2.01 показаны ожидаемые результаты для некоторых входных данных.
Таблица 2.10. Некоторые ожидаемые результаты для задачи вычисления медианы в тройке медиан
Длина группы, Список Ожидаемый результат
3
909, 4, 4, 7, 9, 12, 77, 45, 1		 9
3
909, 4, 4, 7, 9, 12, 77, 45		 12
3
909, 4, 4, 7, 9, 12, 77		 12
5
1, 4, 90, 65, 3, 2		 4
3
22, 40, 65, 80, 93, 21		 80
5
100, 9, 12, 20, 3		 12



Сравнение алгоритмов
.Используя следующий блок для программ можно сравнить эффективность разных алгоритмов.
Программа получает на вход четыре числа - N,M,r0,r1 и выполняет следующие действия:
  • создает случайную выборку объема N c числами из отрезка [r0,r1] 
    ( если N - чётное число, то значение автоматически увеличивается на 1)
  • находит x - "точная" медиана выборки, полученная с помощью сортировки; tx - затраты процессора на получение x
  • находит y - оценка  медиана выборки, полученная предложенным методом; ty - затраты процессора на получение y;
    ky - разницу мест в отсортированном списке между y и x; отношение ky/N
    (метод использует рекурсию и не меняет исходный список, реализация без рекурсии работает быстрее) 
  • находит z - оценка  медиана выборки, полученная предложенным Вами методом; tz - затраты процессора на получение y
    kz - разницу мест в отсортированном списке между z и x; отношение kz/N
Можно получить результаты и без ввода своей программы
 

Стандартным считается способ, в котором используются не тройки, а пятерки.

Напишите программу def median_of_medians(items,m), которая:
  • получает список числе items
  • длину групп для разбиения - нечётное число m
  • возвращает одно число - оценку медиану списка
Введите N, M, r0, r1 (четыре числа в строку через пробел или запятую)
Если значение N>107, то оно автоматически будет обрезано до 107+1, чётные  значение N,M будут ,будут увеличены на 1.
Время работы фрагментов программы измеряется в "тактах" (это для удобства сравнения). 
В последней строке - общее время работы программы (с учетом времени на создание случайного массива)
 

time 20000 ms
memory 1024 Mb

Комментарий учителя

     

Обсуждения (0)
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Решения (0)

Решения:

Нет доступных решений