Ինչպե՞ս մշակել տվյալների հոսքը՝ միջին արժեքը հաշվելու համար սահմանափակ հիշողությամբ։

Մեդիան հաշվարկելու համար տվյալների հոսքում սահմանափակ հիշողությամբ օգտագործվում են ալգորիթմներ, որոնք չեն պահանջում պահել բոլոր տարրերը։ Մեկ հայտնի մոտեցում է պահել երկու տվյալների կառուցվածքներ (օրինակ՝ երկու հողեր)

• Մեծագույն հող՝ ստորին կեսի տարրերի համար
• Մինիմալ հող՝ վերին կեսի տարրերի համար

Երբ նոր թիվ է գալիս, այն ավելացվում է մեկ հողում, ապա դրանց չափերը հավասարակշռվում են, որպեսզի տարբերությունը չգերազանցի 1-ը։ Մեդիան այն է՝ կամ մեծագույն հողի արմատը (եթե այն մեծ է), կամ երկու հողերի արմատների միջին արժեքը։

Այս մեթոդը թույլ է տալիս յուրաքանչյուր տարրին հասնել O(log n) ժամանակում և օգտագործել հիշողությունը՝ համեմատաբար մեծ թվով տարրերի, առանց ամբողջ հոսքը պահելու։

Python-ում օրինակ՝

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # մեծագույն հող (հակառակ արժեքներով)
        self.high = [] # մինիմալ հող

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # տեղափոխել ամենամեծը ստորին հողից վերև
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # հավասարակշռել չափերը
        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

# Օգտագործում՝
finder = MedianFinder()
for num in [5, 15, 1, 3]:
    finder.add_num(num)
    print(finder.find_median())

Այս մեթոդը արդյունավետ է սահմանափակ հիշողությամբ տվյալների հոսքերը մշակելու համար։