Hogyan kezeljük az adatfolyamot a medián számításához korlátozott memóriával?

Az adatok folyamatában a medián kiszámításához olyan algoritmusokat használnak, amelyek nem igénylik az összes elem tárolását. Egy népszerű megközelítés két adatszerkezet (például két halom) fenntartása:

• Egy maximális halom az alsó fél elemeire
• Egy minimális halom a felső fél elemeire

Amikor egy új szám érkezik, hozzáadják valamelyik halomhoz, majd kiegyensúlyozzák a méretüket, hogy ne különbözzenek több mint 1-gyel. A medián vagy a maximális halom gyökere (ha nagyobb), vagy mindkét halom gyökeinek átlaga.

Ez a módszer lehetővé teszi, hogy minden elemhez O(log n) idő alatt elérjük a mediánt, és a memóriát a elemek számával arányosan használja, anélkül, hogy az egész adatfolyamot tárolná.

Python példával:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # maximális halom (értékek fordítva)
        self.high = [] # minimális halom

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # A legnagyobb az alacsony halomból a magasba
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Méretek kiegyensúlyozása
        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

# Használat:
finder = MedianFinder()
for num in [5, 15, 1, 3]:
    finder.add_num(num)
    print(finder.find_median())

Ez a módszer hatékony a korlátozott memóriával rendelkező adatfolyamok feldolgozására.