python学习_一文了解大文件排序/外存排序问题

2021-08-09 0 1,019 百度已收录

成绩一:一个文件含有5亿行,每一行是一个随机整数,需求对于该文件一切整数排序。

分治(pide&Conquer),参考年夜数据算法:对于5亿数据停止排序

对于这个一个500000000行的 total.txt 停止排序,该文件巨细 4.6G。

每一读10000行就排序并写入到一个新的子文件里(这里运用的是疾速排序)。

1.联系 & 排序

#!/usr/bin/python2.7

import time

def readline_by_yield(bfile):
    with open(bfile, 'r') as rf:
        for line in rf:
            yield line

def quick_sort(lst):
    if len(lst) < 2:
        return lst
    pivot = lst[0]
    left = [ ele for ele in lst[1:] if ele < pivot ]
    right = [ ele for ele in lst[1:] if ele >= pivot ]
    return quick_sort(left) + [pivot,] + quick_sort(right)

def split_bfile(bfile):
    count = 0
    nums = []
    for line in readline_by_yield(bfile):
        num = int(line)
        if num not in nums:
            nums.append(num)
        if 10000 == len(nums):
            nums = quick_sort(nums)
            with open('subfile/subfile{}.txt'.format(count+1),'w') as wf:
                wf.write('\\n'.join([ str(i) for i in nums ]))
            nums[:] = []
            count += 1
            print count

now = time.time()
split_bfile('total.txt')
run_t = time.time()-now
print 'Runtime : {}'.format(run_t)

会天生 50000 个小文件,每一个小文件巨细约正在 96K摆布。

python学习_一文了解大文件排序/外存排序问题

顺序正在履行进程中,内存占用不断处正在 5424kB 摆布

python学习_一文了解大文件排序/外存排序问题

全部文件联系完耗时 94146 秒。

2.兼并

#!/usr/bin/python2.7
# -*- coding: utf-8 -*-

import os
import time

testdir = '/ssd/subfile'

now = time.time() 

# Step 1 : 获得局部文件描绘符
fds = []
for f in os.listdir(testdir):
    ff = os.path.join(testdir,f)
    fds.append(open(ff,'r'))

# Step 2 : 每一个文件获得第一行,即以后文件最小值
nums = []
tmp_nums = []
for fd in fds:
    num = int(fd.readline())
    tmp_nums.append(num)

# Step 3 : 获得以后最小值放入暂存区,并读取对于应文件的下一行;轮回遍历。
count = 0
while 1:
    val = min(tmp_nums)
    nums.append(val)
    idx = tmp_nums.index(val)
    next = fds[idx].readline()
    # 文件读完了
    if not next:
        del fds[idx]
        del tmp_nums[idx]
    else:
        tmp_nums[idx] = int(next)
    # 暂存区保管1000个数,一次性写入硬盘,而后清空持续读。
    if 1000 == len(nums):
        with open('final_sorted.txt','a') as wf:
            wf.write('\\n'.join([ str(i) for i in nums ]) + '\\n')
        nums[:] = []
    if 499999999 == count:
        break
    count += 1
   
with open('runtime.txt','w') as wf:
    wf.write('Runtime : {}'.format(time.time()-now))

顺序正在履行进程中,内存占用不断处正在 240M摆布

python学习_一文了解大文件排序/外存排序问题

python学习_一文了解大文件排序/外存排序问题

跑了38个小时摆布,才兼并完没有到5万万行数据...

固然低落了内存运用,但工夫庞大度过高了;能够经过增加文件数(每一个小文件存储行数添加)来进一步低落内存运用

成绩二:一个文件有一千亿行数据,每一行是一个IP地点,需求对于IP地点停止排序。

IP地点转换成数字

# 办法一:手动较量争论
 
In [62]: ip
Out[62]: '10.3.81.150'
 
In [63]: ip.split('.')[::-1]
Out[63]: ['150', '81', '3', '10']
 
In [64]: [ '{}-{}'.format(idx,num) for idx,num in enumerate(ip.split('.')[::-1]) ]
Out[64]: ['0-150', '1-81', '2-3', '3-10']
 
In [65]: [256**idx*int(num) for idx,num in enumerate(ip.split('.')[::-1])]
Out[65]: [150, 20736, 196608, 167772160]
 
In [66]: sum([256**idx*int(num) for idx,num in enumerate(ip.split('.')[::-1])])                     
Out[66]: 167989654 
In [67]:
 
# 办法二:运用C扩大库来较量争论
In [71]: import socket,struct
In [72]: socket.inet_aton(ip)
Out[72]: b'\\n\\x03Q\\x96'
 
In [73]: struct.unpack("!I", socket.inet_aton(ip))
# !透露表现运用收集字节挨次剖析, 前面的I透露表现unsigned int, 对于应Python里的integer or long 
Out[73]: (167989654,)
 
In [74]: struct.unpack("!I", socket.inet_aton(ip))[0]
Out[74]: 167989654
 
In [75]: socket.inet_ntoa(struct.pack("!I", 167989654))              
Out[75]: '10.3.81.150'
 
In [76]:

成绩三:有一个1.3GB的文件(共一亿行),外面每行都是一个字符串,请正在文件中找出反复次数至多的字符串。

根本思惟:迭代读年夜文件,把年夜文件拆分红多个小文件;最初再合并这些小文件。

拆分的划定规矩

迭代读年夜文件,内存中保护一个字典,key是字符串,value是该字符串呈现的次数;

当字典保护的字符串品种到达10000(可自界说)的时分,把该字典依照key从小到年夜排序,而后写入小文件,每一行是 key\\tvalue;

而后清空字典,持续往下读,直到年夜文件读完。

合并的划定规矩

起首获得局部小文件的文件描绘符,而后各自读出第一行(即每一个小文件字符串ascii值最小的字符串),停止比拟。

找出ascii值最小的字符串,假如有反复的,这把各自呈现的次数累加起来,而后把以后字符串以及总次数存储到内存中的一个列表。

而后把最小字符串地点的文件的读指针向下移,即从对于应小文件里再读出一前进行下一轮比拟。

当内存中的列表个数到达10000时,则一次性把该列表内容写到一个终极文件里存储到硬盘上。同时清空列表,停止以后的比拟。

不断到读完整部的小文件,那末最初失掉的终极文件便是一个依照字符串ascii值升序排序的年夜的文件,每行的内容便是 字符串\\t反复次数

最初迭代去读这个终极文件,找出反复次数至多的便可。

1. 联系

def readline_by_yield(bfile):
    with open(bfile, 'r') as rf:
        for line in rf:
            yield line

def split_bfile(bfile):
    count = 0
    d = {}
    for line in readline_by_yield(bfile):
        line = line.strip()
        if line not in d:
            d[line] = 0
        d[line] += 1
        if 10000 == len(d):
            text = ''
            for string in sorted(d):
                text += '{}\\t{}\\n'.format(string,d[string])
            with open('subfile/subfile{}.txt'.format(count+1),'w') as wf:
                wf.write(text.strip())
            d.clear()
            count += 1

    text = ''
    for string in sorted(d):
        text += '{}\\t{}\\n'.format(string,d[string])
    with open('subfile/subfile_end.txt','w') as wf:
        wf.write(text.strip())

split_bfile('bigfile.txt')

2. 合并

import os
import json
import time
import traceback

testdir = '/ssd/subfile'

now = time.time() 

# Step 1 : 获得局部文件描绘符
fds = []
for f in os.listdir(testdir):
    ff = os.path.join(testdir,f)
    fds.append(open(ff,'r'))

# Step 2 : 每一个文件获得第一行
tmp_strings = []
tmp_count = []
for fd in fds:
    line = fd.readline()
    string,count = line.strip().split('\\t')
    tmp_strings.append(string)
    tmp_count.append(int(count))

# Step 3 : 获得以后最小值放入暂存区,并读取对于应文件的下一行;轮回遍历。
result = []
need2del = []

while True:
    min_str = min(tmp_strings)
    str_idx = [i for i,v in enumerate(tmp_strings) if v==min_str]
    str_count = sum([ int(tmp_count[idx]) for idx in str_idx ])
    result.append('{}\\t{}\\n'.format(min_str,str_count))
    for idx in str_idx:
        next = fds[idx].readline()  # IndexError: list index out of range
        # 文件读完了
        if not next:
            need2del.append(idx)
        else:
            next_string,next_count = next.strip().split('\\t')
            tmp_strings[idx] = next_string
            tmp_count[idx] = next_count
    # 暂存区保管10000个记载,一次性写入硬盘,而后清空持续读。
    if 10000 == len(result):
        with open('merged.txt','a') as wf:
            wf.write(''.join(result))
        result[:] = []
    # 留意: 文件读完需求删除了文件描绘符的时分, 需求逆序删除了
    need2del.reverse()
    for idx in need2del:
        del fds[idx]
        del tmp_strings[idx]
        del tmp_count[idx]
    need2del[:] = []
    if 0 == len(fds):
        break

with open('merged.txt','a') as wf:
    wf.write(''.join(result))
result[:] = []

合并后果剖析:

联系时内存中保护的字典巨细 联系的小文件个数 合并时需保护的文件描绘符个数 合并时内存占用 合并耗时
第一次 10000 9000 9000 ~ 0 200M 合并速率慢,暂未统计实现工夫
第二次 100000 900 900 ~ 0 27M 合并速率快,只要2572秒

3. 查找呈现次数至多的字符串及其次数

import time

def read_line(filepath):
    with open(filepath,'r') as rf:
        for line in rf:
            yield line

start_ts = time.time()

max_str = None
max_count = 0
for line in read_line('merged.txt'):
    string,count = line.strip().split('\\t')
    if int(count) > max_count:
        max_count = int(count)
        max_str = string

print(max_str,max_count)
print('Runtime {}'.format(time.time()-start_ts))

合并后的文件共9999788行,巨细是256M;履行查找耗时27秒,内存占用6480KB。

以上便是一文理解年夜文件排序/外存排序成绩的具体内容,更多请存眷酷吧易资源网别的相关文章!

收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信/支付宝扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

酷吧易资源网 python教程 python学习_一文了解大文件排序/外存排序问题 https://www.kubayi.com/6797.html

常见问题

相关文章

评论
暂无评论