Ein Artikel zum Verständnis des Problems der Sortierung großer Dateien/externer Speicher

Frage 1: Eine Datei enthält 500 Millionen Zeilen, jede Zeile ist eine zufällige Ganzzahl und alle Ganzzahlen in der Datei müssen sortiert werden.

Divide and Conquer (pide&Conquer), ReferenzBig-Data-Algorithmus: Sortieren von 500 Millionen Daten

Sortieren Sie diese total.txt mit 500.000.000 Zeilen. Die Dateigröße beträgt 4,6G.

Sortieren und schreiben Sie jedes Mal in eine neue Unterdatei, wenn 10.000 Zeilen gelesen werden (hier verwenden wir Schnellsortierung).

1. Teilen und Sortieren

#!/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(&#39;subfile/subfile{}.txt&#39;.format(count+1),&#39;w&#39;) as wf:
                wf.write(&#39;\n&#39;.join([ str(i) for i in nums ]))
            nums[:] = []
            count += 1
            print count

now = time.time()
split_bfile(&#39;total.txt&#39;)
run_t = time.time()-now
print &#39;Runtime : {}&#39;.format(run_t)

generiert 50.000 kleine Dateien, jede kleine Datei ist etwa 96 KB groß.

Während der Ausführung des Programms lag die Speichernutzung bei 5424 kB ca.

Es dauerte 94146 Sekunden, um die Aufteilung der gesamten Datei abzuschließen.

2. Während der Ausführung des Zusammenführungsprogramms

betrug die Speichernutzung etwa 240M

Es dauerte etwa 38 Stunden, um weniger als 50 Millionen Datenzeilen zusammenzuführen. ..

Obwohl die Speichernutzung reduziert wird, ist die zeitliche Komplexität zu hoch. Die Speichernutzung kann weiter reduziert werden, indem die Anzahl der Dateien verringert wird (die Anzahl der in jeder kleinen Datei gespeicherten Zeilen erhöht sich).

#!/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))

Nach dem Login kopieren

Grundidee: Große Dateien iterativ lesen, die großen Dateien in mehrere kleine Dateien aufteilen und diese kleinen Dateien schließlich zusammenführen.

Aufteilungsregeln:

nach Schlüssel von klein nach groß und schreiben Sie es dann in eine kleine Datei. Jede Zeile ist der Schlüsselwert

Merge-Regeln:

die Dateideskriptoren aller kleinen Dateien ab und lesen Sie dann die erste Zeile (d. h. die Zeichenfolge mit dem kleinsten ASCII-Wert jeder kleinen Dateizeichenfolge) zum Vergleich aus.

Datei eine große Datei, die in aufsteigender Reihenfolge nach dem ASCII-Wert der Zeichenfolge sortiert ist. Der Inhalt jeder Zeile ist die Anzahl der Wiederholungen der Zeichenfolge t,

# 方法一：手动计算
 
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]:

Nach dem Login kopieren

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')

Nach dem Login kopieren

Zusammenführungsergebnisanalyse:

Wörterbuchgröße bleibt während der Aufteilung im Speicher erhaltenAnzahl der kleinen Dateien, die aufgeteilt werden sollenDateibeschreibung, die während der Zusammenführung beibehalten werden soll Anzahl der Symbole Speicherverbrauch beim ZusammenführenZusammenführungszeit Erstes Mal1000090009000 ~ 0200MDie Zusammenführungsgeschwindigkeit ist langsam und die Abschlusszeit nicht wurde schon berechnet Das zweite Mal 100000900900 ~ 027m ist schnell, nur 2572 Sekunden

3. Finden Sie die Zeichenfolge mit den meisten Vorkommen Anzahl der Sekunden Die endgültige Datei hat insgesamt 9999788 Zeilen und ist 256 MB groß. Die Suche dauert 27 Sekunden und belegt 6480 KB Speicher.

Das obige ist der detaillierte Inhalt vonEin Artikel zum Verständnis des Problems der Sortierung großer Dateien/externer Speicher. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!