Золотая середина. Поиск медианного элемента потока входных чисел
В этой статье мы рассмотрим следующую задачу: поиск и поддержание медианы среди целых чисел, которые последовательно попадают на обработку. В этом посте мы поставим задачу, разберём все необходимые вводные, предложим и оценим сложность решения.
Постановка задачи
На вход алгоритму подаётся поток целых чисел, т.е. количество чисел может быть неизвестно, но мы будем считать, что массив задан наперёд и его длина очень большая. Требуется разработать алгоритм, который определяет медиану текущего массива, т.е. считанного из исходного к данному моменту. При этом требуется, чтобы сложность такого алгоритма была
Медиана ряда чисел
Начнём с базовых понятий. Медианой называется число, стоящее в упорядоченном ряде чисел посередине. Например в ряду: 1, 2, 3, 7, 9 — тройка является медианой. Если количество чисел чётное, то за медиану принимают среднее двух стоящих в центре чисел.
Либо можно выбирать элемент под номером , если чётное и если нечетное.
Наивный подход
Давайте обсудим бейзлайновое решение, при котором медиану можно получить за .
Пусть каждое новое число из потока мы будем вставлять в массив так, чтобы массив оставался упорядоченным. Затем будем выбирать элемент из середины и добавлять его в список медиан.
medians = [] items_read = [] with open('./Median.txt', 'r') as f: for line in f: num = int(line.strip()) for idx in range(len(items_read)): if num < items_read[idx]: items_read.insert(idx, num) break if len(items_read) % 2 == 0: median_pos = len(items_read) // 2 else: median_pos = len(items_read) + 1 // 2 medians.append(median_pos) Как упоминалось выше, этот алгоритм будет иметь квадратичную сложность, поскольку для каждого из элементов потока, мы выполняем линейную работу по поиску места и вставке элемента в массив.
Улучшить этот результат нам поможет структура данных — куча.
Куча. Min-heap, max-heap
Рассмотрим кучу на примере min-heap. Min-heap — это бинарное дерево, обладающее двумя следующими свойствами:
- ключи любого узла этого дерева всегда меньше, чем ключи его двух дочерних узлов,
- такое дерево является полным, т.е. у него должны быть заполнены все уровни, за исключением последнего.
Пример кучи (источник)
Аналогично образом задаётся max-heap, нужно заменить «меньше» на «больше» в первом свойстве.
При решении задачи мы хотим воспользоваться операциями, которые благодаря построению кучи, могут быть выполнены быстрее, чем за линейное время.
Первая из этих операций: взятие минимума (максимума) и удаление
Работая с кучей, операцию взятия минимума можно осуществить за константное время. Поскольку минимум всегда хранится в корне дерева, то узнать его значение не составляет труда. Если же мы хотим удалить минимум и назначить на его место следующий по величине элемент, то нам потребуется вызвать метод extract, чья временная сложность тоже меньше линейной и равна .
Метод extract внутри себя запускает следующий процесс: сначала элемент с самого последнего уровня ставится в корень дерева, затем на корне дерева стартует метод bubble_down, который уровень за уровнем (а таких всего в полном дереве) опускает новый корневой узел.
Код реализации на языке Python смотри ниже.
Вторая операция: добавление элемента
Чтобы добавить произвольный элемент в кучу требуется выставить новый элемент на правильное место, не утратив 2 свойства кучи. Для этого новый элемент добавляется на последний уровень, а затем методом bubble_up поднимается в сторону корня, пока над ним не окажется элемент меньший него или он не станет корнем. Сложность этой операции также равна
Код, в котором мы определим необходимую функциональность с возможностью определения min и max-heap:
class Heap(object): def __init__(self, array, type): super(Heap, self).__init__() self.type = type self.data = [] self.heapify(array) def heapify(self, array): for item in array: self.insert(item) def bubble_down(self, array, index=0): left = 2 * index + 1 right = 2 * index + 2 size = len(array) least = index if self.type == 'min': if left < size and array[left] < array[least]: least = left if right < size and array[right] < array[least]: least = right if least != index: tmp_val = array[least] array[least] = array[index] array[index] = tmp_val self.bubble_down(array, index=least) else: if left < size and array[left] >array[least]: least = left if right < size and array[right] >array[least]: least = right if least != index: tmp_val = array[least] array[least] = array[index] array[index] = tmp_val self.bubble_down(array, index=least) def bubble_up(self, array, index): parent = (index - 1) // 2 if self.type == 'min': if array[index] < array[parent] and parent >= 0: tmp_val = array[parent] array[parent] = array[index] array[index] = tmp_val self.bubble_up(array, index=parent) else: if array[index] > array[parent] and parent >= 0: tmp_val = array[parent] array[parent] = array[index] array[index] = tmp_val self.bubble_up(array, index=parent) def extract(self): root = self.data.pop(0) self.data.insert(0, self.data.pop(-1)) self.bubble_down(self.data, 0) return root def insert(self, element): self.data.append(element) self.bubble_up(self.data, index=len(self.data)-1) if __name__ == "__main__": a = [3,99,4,88,0,5,1,2] b = Heap(a, type='max') print(b.data) Оптимальное решение
Теперь перейдем непосредственно к реализации алгоритма контроля медианы, основанном на использовании кучи. Мы будем использовать две кучи, одну минимальную, другую максимальную. Идея заключается в следующем: давайте разделим поток значений на верхнюю часть, содержащую большие значения и нижнюю, содержащую меньшие значения. Первую реализуем на основе min-heap, чтобы легко получать минимальный элемент, который лежит на разделе, а вторую на основе max-heap.
Всякий раз, когда мы читаем из потока очередное число, будем добавлять его в верхнюю часть, если оно больше наименьшего из этой половины и в нижнюю часть, если верно обратное. Затем, осуществив вставку, будем балансировать две части, чтобы они содержали по половине из введенных значений.
from heap import Heap top_nums = Heap([], 'min') bot_nums = Heap([], 'max') medians = [] with open('./Median.txt', 'r') as f: for line in f: num = int(line.strip()) if len(top_nums.data): top_smallest = top_nums.data[0] if num > top_smallest: top_nums.insert(num) else: bot_nums.insert(num) else: bot_nums.insert(num) while len(top_nums.data) > len(bot_nums.data): bot_nums.insert(top_nums.extract()) while len(top_nums.data) + 1 < len(bot_nums.data): top_nums.insert(bot_nums.extract()) medians.append(bot_nums.data[0]) Каждую итерацию внешнего цикла, мы делаем несколько шагов сложностью , посколько операции вставки и получения элемента из кучи ограничены этой сложностью. По этой причине итоговая сложность не превышает .
Заключение
В этой статье на примере задачи мы обсудили преимущества кучи по сравнению со списком. Познакомились с временной сложностью операций над этой структурой данных. Реализовали код этой структуры, необходимый для эффективного выполнения задачи по поиску медианного элемента в потоке чисел.
В преддверии старта курса «Алгоритмы и структуры данных» приглашаем всех желающих на бесплатный двухдневный интенсив по теме: Алгоритм сжатия данных — код Хаффмана.
- ЗАПИСАТЬСЯ НА ИНТЕНСИВ. ДЕНЬ 1
- ЗАПИСАТЬСЯ НА ИНТЕНСИВ. ДЕНЬ 2
- алгоритмы
- структуры данных
Научный форум dxdy
Последний раз редактировалось Eiktyrnir 24.03.2021, 19:17, всего редактировалось 2 раз(а).
Уважаемые корифеи и знатоки!
Медиана
В списке нечётное число элементов, при этом все элементы различны. Найдите медиану списка: элемент, который стоял бы ровно посередине списка, если список отсортировать.
При решении этой задачи нельзя модифицировать данный список (в том числе и сортировать его), использовать вспомогательные списки.
Программа должна вывести единственное число — значение медианного элемента в списке.
Первая строка содержит размер массива 
. Во второй строке через пробел задаются чисел – элементы массива. Гарантируется, что 
и – нечётное число.
Программа должна вывести одно число – медиану массива.
Примеры
Ввод
Вывод
При написании программного кода нельзя использовать
Вариант (ошибка кроется где-то но найти не можем)
Используется синтаксис Python
a = list ( map ( int , input ( ) . split ( ) ) )
for i in range ( len ( a ) ) :
count = 0
for j in range ( len ( a ) ) :
if a [ j ] < a [ i ] :
count+ = 1
if count == len ( a ) // 2 :
print ( a [ i ] )
break
Вариант (аналогично не можем понять в чём ошибка)
Используется синтаксис Python
a = list ( map ( int , input ( ) . split ( ) ) )
for elem in a:
count = 0
for x in a:
if x < elem:
count+ = 1
if count == len ( a ) // 2 :
print ( elem )
break
Posted automatically
24.03.2021, 17:49
- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы );
- используйте для кода тег подстветки синтаксиса.
Медиана
Медиана набора чисел — это число, которое находится в середине этого набора, если его упорядочить по возрастанию. То есть такое число, что половина из элементов набора не меньше него, а другая половина не больше.
Напишите функцию, которая будет принимать отсортированный список чисел и возвращать медиану. Если число дробное, его нужно округлить до десятых.
Примеры
median([1, 2, 4, 5, 6, 8, 8, 8, 10]) ➞ 6 median([2, 2, 6, 8, 8, 10, 10]) ➞ 8 median([1, 2, 2, 4, 7, 8, 9, 10]) ➞ 5.5
Варианты решения
def median(nums): m = len(nums) // 2 return (nums[-(m + 1)] + nums[m]) / 2
import statistics def median(nums): return statistics.median(nums)
def median(nums): count = len(nums) median = (nums[count // 2] + nums[(count - 1) // 2]) / 2 return round(median, 1)
Посчитать медиану списка по уникальным значениям
Нужно посчитать дельту x1, а потом от всех дельт всех медиану для каждой позиции из com - в примере только две. то есть на выходе нужно получить нечто такое:
com x1 delta median 1 5 -1 1 4 -1 -1 1 3 -1 -1 1 2 -1 -1 1 4 2 -1 2 5 1 2 6 1 1 2 8 2 1 2 3 -5 1 Пробовал через циклы, но опять же занимает очень много времени и выдает ошибку отсюда Ошибка в python pandas, "A value is trying to be set on a copy of a slice from a DataFrame"
Отслеживать
149k 12 12 золотых знаков 59 59 серебряных знаков 132 132 бронзовых знака
задан 28 янв 2019 в 11:03
851 3 3 золотых знака 11 11 серебряных знаков 20 20 бронзовых знаков
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Очень просто. Нужны 2 вещи: rolling , groupby и map . Итак.
Для начала, импортируем пандас и загрузим (распарсим Ваши данные):
import pandas as pd data = '''1 5 1 4 1 3 1 2 1 4 2 5 2 6 2 8 2 3''' data = [list(map(int, filter(lambda el: len(el) > 0, l.split(' ')))) for l in x.split('\n')] Вот что получается:
[[1, 5], [1, 4], [1, 3], [1, 2], [1, 4], [2, 5], [2, 6], [2, 8], [2, 3]] df = pd.DataFrame(data, columns=['com', 'x1']) df 
Используем rolling , чтобы посчитать дельту:
df['delta'] = df['x1'].rolling(window=2).apply(lambda x: x[1] - x[0], raw=True) 
В заключение, с помощью map заполним все значениия в колонке median :
df['median'] = df['com'] df['median'] = df['median'].map(df.groupby('com')['delta'].median().to_dict()) df 
Отслеживать
ответ дан 28 янв 2019 в 12:54
hedgehogues hedgehogues
9,411 8 8 золотых знаков 50 50 серебряных знаков 101 101 бронзовый знак
кстати, загружать данные из вопросов на SO можно проще: сначала набираем в iPython/Jupyter: df = pd.read_clipboard() , потом кладем в буфер обмена данные с именами столбцов из вопроса и нажимаем Enter 😉
28 янв 2019 в 15:51
In [24]: grp = df.groupby('com') In [25]: df['delta'] = grp['x1'].diff() In [26]: df['median'] = grp['delta'].transform('median') In [27]: df Out[27]: com x1 delta median 0 1 5 NaN -1.0 1 1 4 -1.0 -1.0 2 1 3 -1.0 -1.0 3 1 2 -1.0 -1.0 4 1 4 2.0 -1.0 5 2 5 NaN 1.0 6 2 6 1.0 1.0 7 2 8 2.0 1.0 8 2 3 -5.0 1.0 Если столбец delta нужен только для расчета медианного значения в группе, то можно все сделать за один шаг:
In [33]: df['median'] = df.groupby('com')['x1'].transform(lambda c: c.diff().median()) In [34]: df Out[34]: com x1 median 0 1 5 -1 1 1 4 -1 2 1 3 -1 3 1 2 -1 4 1 4 -1 5 2 5 1 6 2 6 1 7 2 8 1 8 2 3 1