1. import heapq
  3. def sort_log_streams(log_streams, max_memory):
  4. """
  5. Sorts records of log streams for backward compatibility with limited memory usage.
  7. Args:
  8. log_streams (list of lists): A list of log streams, where each stream is a list of records.
  9. max_memory (int): The maximum number of records that can be stored in memory at once.
  11. Returns:
  12. list: A sorted list of all records from all log streams.
  13. """
  15. sorted_records = []
  16. heap = [] # Use a min-heap to track the smallest elements
  18. for stream in log_streams:
  19. for record in stream:
  20. if len(heap) < max_memory:
  21. heapq.heappush(heap, record) # Add to heap if memory allows
  22. else:
  23. if record > heap[0]: # If current record is larger than the smallest in heap
  24. heapq.heapreplace(heap, record) # Replace smallest with current record
  26. # Extract sorted records from the heap
  27. while heap:
  28. sorted_records.append(heapq.heappop(heap))
  30. return sorted_records[::-1] # Reverse to get ascending order
  34. if __name__ == '__main__':
  35. # Example usage
  36. log_streams = [
  37. [1, 5, 2, 8],
  38. [3, 7, 4, 9],
  39. [6, 10, 0, 11]
  40. ]
  41. max_memory = 5
  42. sorted_log = sort_log_streams(log_streams, max_memory)
  43. print(sorted_log)

Add your comment