Kā apstrādāt datu plūsmu, lai aprēķinātu mediānu ar ierobežotu atmiņu?

Aprēķinot mediānu datu plūsmā ar ierobežotu atmiņu, tiek izmantoti algoritmi, kas neprasa saglabāt visus elementus. Viens no populārākajiem pieejas veidiem ir uzturēt divas datu struktūras (piemēram, divas kaudzes):

• Maksimālā kaudze apakšējai pusei elementu
• Minimālā kaudze augšējai pusei elementu

Kad ienāk jauns skaitlis, tas tiek pievienots vienai no kaudzēm, pēc tam to izmērus līdzsvaro tā, lai to izmēru starpība nebūtu lielāka par 1. Mediāna ir vai nu maksimālās kaudzes saknes elements (ja tas ir lielāks), vai abu kaudžu vidējā vērtība.

Šī pieeja ļauj iegūt mediānu katram elementam ar O(log n) laiku un izmantot atmiņu proporcionāli elementu skaitam, bet bez visa plūsmas saglabāšanas.

Piemērs Python valodā:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # maksimālā kaudze (inversijas vērtības)
        self.high = [] # minimālā kaudze

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Pārvietot maksimālo no low uz high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Saskaņot izmērus
        if len(self.low) > len(self.high) + 1:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)
        elif len(self.high) > len(self.low):
            val = heapq.heappop(self.high)
            heapq.heappush(self.low, -val)

    def find_median(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        else:
            return (-self.low[0] + self.high[0]) / 2

# Lietošana:
finder = MedianFinder()
for num in [5, 15, 1, 3]:
    finder.add_num(num)
    print(finder.find_median())

Šī pieeja ir efektīva plūsmas apstrādei ar ierobežotu atmiņu.