当前位置:首页 > 模式算法 > 正文内容

归并排序,外排序,10G文件500M内存的排序

phpmianshi7年前 (2015-04-13)模式算法564

归并排序可以是一种外排序, 外排序是指利用外存也就是磁盘进行排序的一种简称。

典型的应用是hadoop 的 mapreduce 的merge 阶段

归并排序的: 假设有n 个元素, 将n 个元素分程x 组, 然后对每一组的元素进行排序, 然后将这 x 组已经排好序的序列合并起来。

说一下分成x 组的方式, 大概有两种:

  第一种: 递归的方式,  这种情况你可能都不会去关心 x 大小。

  第二种: 每组 m 个元素, x =  n/m。这种方法常用在内存不够的情况下。

 

所以归并排序的步骤分两步:

  第一步: 分x 组, 对每组的元素进行排序

  第二部: 合并, 将已经排序好的 x 组元素合并起来。

 

先说第一种递归的方式吧, 就是你可能会做到的归并排序的题目:

  我们先写第二步的代码:合并已经排序好的数组

复制代码
def merge_sorted_list(l1, l2):
    i, j = 0, 0
    result = []    while i < len(l1) and j < len(l2):        if l1[i] <= l2[j]:
            result.append(l1[i])
            i += 1        else:
            result.append(l2[j])
            j += 1
    result += l1[i:]
    result += l2[j:]    return result
复制代码

  再说第一步:

  

复制代码
def merge_sort(l):    if len(l) <= 1:        return l
    num = len(l) / 2
    l1 = merge_sort(l[:num])
    l2 = merge_sort(l[num:])    return merge_sorted_list(l1, l2)
复制代码

全部代码:

复制代码
def merge_sort(l):    if len(l) <= 1:        return l
    num = len(l) / 2 
    l1 = merge_sort(l[:num])
    l2 = merge_sort(l[num:])    return merge_sorted_list(l1, l2) 
  
def merge_sorted_list(l1, l2):
    i, j = 0, 0
    result = []    while i < len(l1) and j < len(l2):        if l1[i] <= l2[j]:
            result.append(l1[i])
            i += 1        else:
            result.append(l2[j])
            j += 1
    result += l1[i:]
    result += l2[j:]    return result
  
a = [219, 9527, 211, 9218]print a
b = merge_sort(a)print b
复制代码

总的来说这种归并排序理解起来以及代码写起来都是很简单的。

 

接下来说一下第二种吧,纯粹的外排序。用栗子的方式理解起来比较简单。

问题: 假设有2G的文件,里面是数字,一行一个数字,内存只有500M。让你排序,咋整?

其实思路很简单,一次只读一点点,排序好,然后再将将文件合并起来。然后最终保存为一个大文件。

先说下python open(filepath).readline(),一次只会返回一行,不必担心大文件,相信各个语言都有对应的方式。

首先第一步,大文件拆分成 x 个 block_size 大的小文件,每个小文件排好序

复制代码
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
复制代码

第二部:将拆分成的小文件合并起来,然后将归并的东西写到大文件里面去, 这里用到的是多路归并的方法。多路归并在我的这篇文章里面有写到:http://www.cnblogs.com/dream-of-cambridge/articles/8046031.html

复制代码
def nw_merge(files):
    fs = [open(file_) for file_ in files]
    min_map = {}
    out = open("/home/hrs/demo/files/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 = min_f.readline()        if nextline:
            min_map[min_f] = int(nextline.strip())        else:            del min_map[min_f]
复制代码

全部代码:

 

复制代码
= = open(filepath,  i = [open(file_)  file_ == open(,  f === min(min_map.items(), key =  x: x[1==== open(file_path, = 1== = [int(i.strip())  i += 1      == = = 500*1024*1024 
    num_blocks = os.stat(file_path).st_size/=
复制代码


版权声明:本文由PHP面试资料网发布,如需转载请注明出处。
分享给朋友:

相关文章

php中的门面模式Facade

概念门面模式又叫外观模式,用来隐藏系统的复杂性,提供一个统一的接口去访问多个子系统的多个不同的接口,它为子系统中的一组接口提供一个统一的高层接口。使用子系统更容易使用。这种类型的设计模式属于结构型模式...

适配器模式与装饰器模式的区别

概念适配器与装饰器模式的别名都是包装模式(Wrapper)。区别适配器模式的意义将一个接口转变成另一个接口,目的是通过改变接口来达到重复使用的目的。装饰器模式的意义不改变被装饰对象的接口,而是保持原有...

php中的迭代器模式

概念迭代器:类继承PHP的Iterator接口,批量操作。1. 迭代器模式,在不需要了解内部实现的前提下,遍历一个聚合对象的内部元素。2. 相比传统的编程模式,迭代器模式可以隐藏遍历元素的所需操作。示...

代理模式、桥接模式、中介者模式区别和联系

联系    在现实生活中,如房屋中介、买房人、卖房人,房屋中介是一个中介,因为它担任买房人和卖房人之间的相同;房屋中介也是一个代理,它在卖房人眼前是买房人的代理,在卖房人...

php中责任链模式

概念又叫职责链模式。包含了一些命令对象和一些处理对象,每个处理对象决定它能处理那些命令对象,它也知道应该把自己不能处理的命令对象交下一个处理对象,该模式还描述了往该链添加新的处理对象的方法。示例情景一...

php中介者模式

概念中介者模式用于开发一个对象,这个对象能够在类似对象相互之间不直接相互的情况下传送或者调解对这些对象的集合的修改。一般处理具有类似属性,需要保持同步的非耦合对象时,最佳的做法就是中介者模式。PHP中...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。