როგორ დავამუშავოთ მონაცემთა ნაკადი მედიანის გამოთვლისთვის შეზღუდული მეხსიერებით?

მეტადანობის გამოთვლისთვის ნაკადი მონაცემებში, სადაც მეხსიერება შეზღუდულია, იყენებენ ალგორითმებს, რომლებიც არ საჭიროებს ყველა ელემენტის შენახვას. ერთ-ერთი პოპულარული მიდგომაა ორი მონაცემთა სტრუქტურის შენარჩუნება (მაგალითად, ორი ქუა):

• მაქსიმალური ქუა ქვედა ნახევრის ელემენტებისთვის
• მინიმალური ქუა ზედა ნახევრის ელემენტებისთვის

როდესაც ახალი რიცხვი შემოდის, მას ერთ-ერთ ქუაში სვამენ, შემდეგ კი ქუების ზომებს ბალანსირებენ ისე, რომ მათი ზომები არ განსხვავდებოდეს 1-ით მეტით. მედიანა ან ქუების ძირითადი ელემენტია (თუ ის მეტია), ან ორივე ქუის საშუალო მნიშვნელობა.

ეს მეთოდი საშუალებას აძლევს მიიღოთ მედიანა O(log n) დროს თითოეულ ელემენტზე და გამოიყენოს მეხსიერება პროპორციული რაოდენობის ელემენტების რაოდენობაზე, მაგრამ არ ინახავს მთელ ნაკადს.

პითონის მაგალითი:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # მაქსიმალური ქუა (მოახერხებს მნიშვნელობების ინვერტირებას)
        self.high = [] # მინიმალური ქუა

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # მაქსიმალური ელემენტის გადატანა 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)

        # ზომების ბალანსირება
        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())

ეს მეთოდი ეფექტურია ნაკადიანი დამუშავებისთვის შეზღუდული მეხსიერებით.