多路归并排序-Python实现⼤⽂件排序，合并排序
使⽤python实现多(K)路归并外部排序，解决⼩内存排序⼤⽂件问题
上⼀篇中，我们实现了⼀般的归并排序
在实际⼯作中，多个有序数列合并成⼀个，⼤⽂件或多个⼤⽂件合并成⼀个并排序的需求常见并不少见，⾸先，先来看⼀下多个有序数列情况
合并多个有序数组
⽐如现在有四路：
a0: [1, 3, 6, 7]
a1: []
a2: [3, 5, 7, 19]
a3: [9, 12, 87, 98]
保存每路最⼩值
第⼀步需要知道每⼀路的最⼩值，如果每⼀路⽤数组表⽰的话需要保存对应的下标，并保存为min_map
第0路: 1
第1路: 没有值
第2路: 3
第3路: 9
初始的 min_map:
{0:(1,0),2:(3,0),3:(9,0)}
获取最⼩值中的最⼩值
第⼆部需要将最⼩值取出来然，后检查被取出值的那⼀路是否还剩下。
其他元素如果存在，则修改min_map⾥⾯对应的值，如果不存在，则删除掉min_map⾥⾯对应的记录，以表⽰该路已经没有元素需要遍历了
代码：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 多路归并: 将已经排序好的多个数组合并起来
def nw_merge(arrs):
"""
需要知道每⼀路的最⼩值
第0路: 1
第1路: 没有值
第2路: 3
第3路: 9
"""
result =[]
min_map ={}# ⽤min_map 保存每⼀路的当前最⼩值
for inx, arr in enumerate(arrs):
if arr:
min_map[inx]=(arr[0],0)
print("初始化的每⼀路最⼩值min_map", min_map)
while min_map:
"""
需要知道每⼀路的最⼩值⾥⾯哪⼀路的最⼩值, 以及最⼩值所在的那⼀路的index
"""
min_ =min(min_map.items(), key =lambda m: m[1][0])
way_num,(way_min_v, way_inx)= min_
result.append(way_min_v)
"""
检查被取出值的那⼀路是否还剩下其他元素，如果存在，则修改min_map⾥⾯对应的值，如果不存在，则删除掉min_map⾥⾯对应的记录，以表⽰该路已经没有元素需要遍历了
"""
way_inx +=1
if way_inx <len(arrs[way_num]):
min_map[way_num]=(arrs[way_num][way_inx], way_inx)
else:
del min_map[way_num]
return result
a0 =[1,3,6,7]
a1 =[]
a2 =[3,5,7,19]
a3 =[9,12,87,98]
arrs =[a0, a1, a2, a3]
print("a0:", a0)
print("a1:", a1)
print("a2:", a2)
print("a3:", a3)
result = nw_merge(arrs)
print("最终合并的:", result)
输出
"""
a0: [1, 3, 6, 7]
a1: []
a2: [3, 5, 7, 19]
a3: [9, 12, 87, 98]
初始化的每⼀路最⼩值min_map {0: (1, 0), 2: (3, 0), 3: (9, 0)}
"""
# 最终合并的:
[1,3,3,5,6,7,7,9,12,19,87,98]
对超⼤⽂件排序(10G的⽇志，512M的内存)
绕不开归并核⼼思想，分治，先拆成⼩⽂件，再排序，最后合并所有碎⽚⽂件成⼀个⼤⽂件
拆⽂件
⾸先第⼀步，⼤⽂件拆分成　x　个 block_size ⼤的⼩⽂件，每个⼩⽂件排好序
def save_file(l, fileno):
filepath =f"/home/xxx/{fileno}"
f =open(filepath,'a')
for i in l:
f.write(f"{i}\n")
f.close()
return filepath
def split_file(file_path, block_size):
f =open(file_path,'r')
fileno =1
files =[]
while True:
lines = f.readlines(block_size)
if not lines:
break
lines =[int(i.strip())for i in lines]
lines.sort()
files.append(save_file(lines, fileno))
fileno +=1
return files
合并
将拆分成的⼩⽂件合并起来，然后将归并的东西写到⼤⽂件⾥⾯去，这⾥⽤到的是上⾯的多路归并的⽅法
def nw_merge(files):
fs =[open(file_)for file_ in files]
min_map ={}
out =open("/home/xxx/out","a")
for f in fs:
read = f.readline()
if read:
min_map[f]=int(read.strip())
while min_map:
min_ =min(min_map.items(), key =lambda x: x[1])        min_f, min_v = min_
out.write("{}".format(min_v))
out.write("\n")
nextline = adline()
if nextline:
min_map[min_f]=int(nextline.strip())
else:
del min_map[min_f]
全部代码
import os
from pathlib import Path
def nw_merge(files):
fs =[open(file_)for file_ in files]
min_map ={}# ⽤来记录每⼀路当前最⼩值
out =open(Path(".")/"","a+")
for f in fs:
read = f.readline()
if read:
min_map[f]=int(read.strip())
while min_map:# 将最⼩值取出，　并将该最⼩值所在的那⼀路做对应的更新        min_ =min(min_map.items(), key=lambda x: x[1])
min_f, min_v = min_
out.write(f"{min_v}\n")
nextline = adline()
if nextline:
min_map[min_f]=int(nextline.strip())
else:
del min_map[min_f]
for f in fs:
f.close()
out.close()python数组合并
def save_file(l, fileno):
path = Path(".")/"split"
filepath = path /f"{fileno}"
info ='\n'.join(map(str, l))
with open(filepath,"a+")as f:
f.write(f"{info}")
return filepath
def split_file(file_path, block_size):
fileno =1# ⽂件数
files =[]# ⼩⽂件⽬录
with open(file_path,'r')as f:
while True:
lines = f.readlines(block_size)
if not lines:
break
lines =[int(i.strip())for i in lines]# ⽣成⼀个列表
lines.sort()# 排序
files.append(save_file(lines, fileno))
fileno +=1
return files
if __name__ =="__main__":
# 每⾏单个数字
file_path = Path(".")/""
block_size =500*1024*1024# 500K
num_blocks = os.stat(file_path).st_size / block_size
files = split_file(file_path, block_size)
nw_merge(files)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。