当前位置： 移动技术网 > IT编程>脚本编程>Python > python3利用归并算法对超过内存限制的超大文件进行排序

python3利用归并算法对超过内存限制的超大文件进行排序

2020年07月20日  | 移动技术网IT编程  | 我要评论

上一篇文章《python3实现归并排序算法图文详解》中，我们了解了归并排序算法的基本使用逻辑。这一篇文章我们对这个逻辑进行一个延伸，从内存延伸到对硬盘上的文件进行排序，也就是所谓的外部排序。

文章目录

操作场景

所谓的大文件就是无法一次性全部读到内存中的文件。

为了操作不真的把我机器的内存都榨干，这里假设机器的内存是300MB，刨除一些系统占用，规定每次读到内存的文件大小不能超过200MB。

我又用下面的程序创建了一个1GB大小的文件

with open('bigfile.txt','a') as f:
    for i in range(100000000):
        f.write(str(random.randint(100000000,999999999))+'\r\n')

这个文件一共有1亿行，每一行以字符串格式存储着一位9位数，并在末尾加上了换行符，所以每行占据10B，算下来一共有10亿B也就是1GB。

下面要实现的就是在内存占用每次不超过200MB的情况下将这个1GB的文件进行排序。硬盘空间很大，随意使用。

思路分析

大家应该还记得《python3实现归并排序算法图文详解》中的两张图

1-cursor.png

针对一个长列表，我们先分割为两个小列表，并将小列表排好序。利用两个游标从左到右移动，我们对两个已经各自排好序的列表合并成了一个新的有序列表。

2-finish.png

这里的小技巧就是利用了递归的思路，对每一个小的列表都进行了归并排序。

但是我们这个问题不需要这么麻烦。首先将1GB的大文件分解为5个200MB的小文件，这里的小文件就是可以直接读进内存一次性排序。

然后直接对这5个小文件读进内存进行排序。

最后再利用归并的思路，通过5个游标分别在5个文件中逐行从左往右移动，将每次最小的一行读到新文件中，达到排序的效果，如下图

3-files.png

代码实现

文件分割

首先来对文件进行分割，每次从原文件读200MB的整行数，然后保存到一个新文件。

这里要补充下python中读取文件的几个方法。f.readlines(n)可以接一个参数n，注意这里的n并不是行数，而是以字节为单位的大小，表示当读到某行时总大小超过了n就不再读下一行。同理，f.readline(n)也可以传递n，表示读取下一行的前n个字节，如果下一行总大小少过n就读取整行。而在某些没有换行符的文件中就不能用这两种读取的方法了，因为无论如何都是直接读取所有内容，只能采用f.read(n)的方式，这里的n也同样是字节数

def splitFile(path, chunk):
    baseDir, baseFile = os.path.split(path)
    fileIndex = 1
    files = []
    with open(path, 'r') as f:
        while True:
            lines = f.readlines(chunk)
            lines.sort()
            if lines:
                newFileName = os.path.join(baseDir, str(fileIndex))
                with open(newFileName, 'a') as sf:
                    sf.write(''.join(lines))
                files.append(newFileName)
                fileIndex += 1
            else:
                break
    return files

if __name__ == '__main__':
    path = '/home/fuhx/python_projects/datanalgo/linkedlist/bigfile.txt'
    chunk = 1024 * 1024 * 200
    files = splitFile(path, chunk)
    print(files)

这里会将新文件保存到和原文件相同的目录，所以首先获取baseDir用来和后面的文件名拼接。新的文件名也很简单，从数字1开始一直往上加。

需要注意的就是这里的trunk，是字节数，f.readlines(trunk)表示逐行读取一直到超过trunk大小就不再读下一行。后面对trunk赋值1024*1024*200就是200MB，所以每个新文件的大小大约就是200MB。

lines.sort()是对读进来的200MB内容进行排序，sort()方法并不会生成新的列表所以不会占用更多内存。

之后如果读取到的内容不为空，就用空字符串将内容列表拼接起来写入新文件，否则跳出循环不再读。

空字符串在python中也是False，同样的还有空字典，空列表等

运行完返回如下

['/home/fuhx/python_projects/datanalgo/linkedlist/1',
 '/home/fuhx/python_projects/datanalgo/linkedlist/2',
 '/home/fuhx/python_projects/datanalgo/linkedlist/3',
 '/home/fuhx/python_projects/datanalgo/linkedlist/4',
 '/home/fuhx/python_projects/datanalgo/linkedlist/5']

查看一下每个文件的大小，除了最后一个文件，其余的都是大约200MB

-rw-rw-r-- 1 fuhx fuhx 201M Jul 18 23:50 1
-rw-rw-r-- 1 fuhx fuhx 201M Jul 18 23:52 2
-rw-rw-r-- 1 fuhx fuhx 201M Jul 18 23:53 3
-rw-rw-r-- 1 fuhx fuhx 201M Jul 18 23:53 4
-rw-rw-r-- 1 fuhx fuhx 154M Jul 18 23:54 5

并且这些文件都已经各自排好序了。

归并文件

然后需要将这些文件进行归并法组合成新的文件了。

通过创建一个字典，key为5个文件的指针，value为当前各自文件中游标对应的一行数据。将value最小的值写入新文件，同时对对应的key读取下一行，来达到循环比较的目的。

如果有文件读到的下一行为空，则删除该key，并关闭文件指针。这里因为没有用with open的语法，注意自己主动关闭文件。

def mergeFiles(fileList: list) -> str:
    """

    :param fileList: a list of file absolute path
    :return: a string of merged file absolute path
    """
    fs = [open(file_, 'r') for file_ in fileList]
    tempDict = {}
    mergedFile = open('merged.txt', 'a')
    for f in fs:
        initLine = f.readline()
        if initLine:
            tempDict[f] = initLine
    # print(tempDict)
    while tempDict:
        min_item = min(tempDict.items(), key=lambda x: x[1])
        mergedFile.write(min_item[1])
        nextLine = min_item[0].readline()
        if nextLine:
            tempDict[min_item[0]] = nextLine
        else:
            del tempDict[min_item[0]]
            min_item[0].close()
    mergedFile.close()
    return os.path.join(os.getcwd(), 'merged.txt')

首先从文件名列表通过列表生成器返回文件指针的列表，然后循环读取初始行。之后如果用来比较的字典不为空，则执行上面的逻辑，最后返回文件完整路径。

这里用来比较的语法min(tempDict.items(), key=lambda x: x[1])使用了key参数，不明白的朋友可以参考另一篇博客《python中min和max方法的key参数使用方法详解》。

最后成功返回新文件，通过对比发现比原文件占用硬盘要少，不过总行数是一样的。

[fuhx@testmachine linkedlist]$ cat merged.txt | wc -l
100000000
[fuhx@testmachine linkedlist]$ cat bigfile.txt | wc -l
100000000
[fuhx@testmachine linkedlist]$ ll -h merged.txt bigfile.txt 
-rw-rw-r-- 1 fuhx fuhx 1.1G Jul 17 17:37 bigfile.txt
-rw-rw-r-- 1 fuhx fuhx 954M Jul 19 11:51 merged.txt

内存表现

通过top可以查看，在进行合并的过程中，内存占用了0.2%，我电脑4GB的内存大约就是8MB，但是CPU使用已经接近100%

4-top.png

不过，在进行文件分割的时候，内存飙到了60%。但是这并不代表在任何机器上都会占用这么高的内存，因为Linux有一套自己的内存使用规则。

说到Linux中的内存管理，这又是一个大话题了，下次再单独写一篇博客，聊一聊free命令查看内存的各个字段，以及如何控制/proc/sys中的内核参数来优化内存使用。

我是T型人小付，一位坚持终身学习的互联网从业者。喜欢我的博客欢迎在csdn上关注我，如果有问题欢迎在底下的评论区交流，谢谢。

本文地址：https://blog.csdn.net/Victor2code/article/details/107443547

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网