Kaip apdoroti duomenų srautą medianai apskaičiuoti turint ribotą atmintį?

Skaičiuojant medianą duomenų sraute, kai atmintis yra ribota, naudojami algoritmai, kurie nereikalauja saugoti visus elementus. Vienas populiariausių būdų yra palaikyti dvi duomenų struktūras (pavyzdžiui, dvi krūvas):

• Didžiausia krūva apatinės pusės elementams
• Mažiausia krūva viršutinės pusės elementams

Kai įdedamas naujas skaičius, jis pridedamas į vieną iš krūvų, tada jų dydžiai subalansuojami taip, kad jų skirtumas nebūtų didesnis nei 1. Medianą sudaro arba didžiausios krūvos šaknies elementas (jei jis didesnis), arba abiejų krūvų vidurkis.

Šis metodas leidžia gauti medianą per O(log n) laiką kiekvienam elementui ir naudoti atmintį proporcingai elementų skaičiui, tačiau neįrašant viso srauto.

Pavyzdys Python kalba:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # maksimali krūva (invertuoti reikšmes)
        self.high = [] # minimali krūva

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Perkelti maksimalią iš low į high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Balansuoti dydžius
        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

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

Šis metodas yra efektyvus srautinio apdorojimo su ribota atmintimi atveju.