K-way merge — பல stream

K-way merge — ஏற்கனவே வரிசைப்படுத்தப்பட்ட K ஓட்டங்களை ஒரு ஓடாக இணைத்தல். K செய்தி ஊட்டங்கள், அல்லது தரவுத்தளத்தில் external merge போன்றவை.

உண்மை உலகில் இது ஏன் முக்கியம்?

LSM tree தரவுத்தளங்கள் sorted run-களை இணைக்கின்றன — k-way merge மையம். MapReduce பல பகிர்வுகள் sorted — reducer முன் இணைப்பு. K அளவு min-heap — ஒவ்வொரு பட்டியலின் தலை; மொத்தம் O(n log K) ஒப்பீடுகள்.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

குவியில் (மதிப்பு, பட்டியல்_id, உள்ளே_index) என வைக்கவும். சிறியதை எடுத்து வெளியீட்டில் சேர்த்து, அந்தப் பட்டியலின் அடுத்த உறுப்பைத் தள்ளவும். K=2 எனில் இரண்டு சுட்டி merge — O(n), எளிய குறியீடு.

Pythonில் முயற்சி செய்வோம்

import heapq

runs = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(list(heapq.merge(*runs)))

அடிக்கடி நேரும் தவறுகள்

• sentinel தவறு — நகல் வெளியீடு.
• index முன்னேற்றம் மறத்தல்.
• K=2 இல் heap தேவையில்லை.

முக்கியச் சுருக்கக் குறிப்புகள்

• heap உடன் O(n log K).
• பெரிய கோப்பு external sort அடித்தளம்.
• Python heapq.merge பயிற்சி.