sắp xếp dữ liệu văn bản lớn

Question

Tôi có một tệp lớn (100 triệu dòng giá trị được phân cách bằng tab - kích thước khoảng 1,5 GB). Cách nhanh nhất để sắp xếp điều này dựa trên một trong các trường là gì?

Tôi đã thử hive. Tôi muốn xem nếu điều này có thể được thực hiện nhanh hơn bằng cách sử dụng python.

Answer 1

Bạn đã cân nhắc sử dụng chương trình * nix sort? về nguyên tắc, nó có thể sẽ nhanh hơn hầu hết các tập lệnh Python.

Sử dụng -t $'\t' để xác định rằng nó phân tách bằng tab -k n để xác định các lĩnh vực, nơi n là số lĩnh vực, và -o outputfile nếu bạn muốn đầu ra kết quả vào một tập tin mới là. Ví dụ:

sort -t $'\t' -k 4 -o sorted.txt input.txt 

sẽ sắp xếp input.txt trên sân thứ 4, và đầu ra kết quả để sorted.txt

Answer 2

tôi sẽ lưu trữ các tập tin trong một cơ sở dữ liệu quan hệ tốt, index nó trên các lĩnh vực bạn quan tâm và sau đó đọc các mục đã đặt hàng.

Answer 3

bạn muốn xây dựng một chỉ số trong bộ nhớ cho các tập tin:

1. tạo ra một danh sách trống
2. open file
3. đọc nó từng dòng (sử dụng f.readline(), và lưu trữ trong danh sách một bộ bao gồm giá trị mà bạn muốn sắp xếp (được trích xuất với line.split('\t').strip()) và độ lệch của dòng trong tệp (mà bạn có thể nhận được bằng cách gọi f.tell() trước khi gọi f.readline())
4. close file
5. sort danh sách

Sau đó, để in các tập tin được sắp xếp, mở lại tập tin và cho mỗi phần tử của danh sách, sử dụng f.seek(offset) để di chuyển con trỏ tập tin đến đầu dòng, f.readline() đọc dòng và print dòng.

Tối ưu hóa: bạn có thể muốn lưu trữ độ dài của dòng trong danh sách, để bạn có thể sử dụng f.read(length) trong giai đoạn in.

Mẫu mã (tối ưu hóa cho dễ đọc, không phải tốc độ):

def build_index(filename, sort_col): 
    index = [] 
    f = open(filename) 
    while True: 
     offset = f.tell() 
     line = f.readline() 
     if not line: 
      break 
     length = len(line) 
     col = line.split('\t')[sort_col].strip() 
     index.append((col, offset, length)) 
    f.close() 
    index.sort() 
    return index 

def print_sorted(filename, col_sort): 
    index = build_index(filename, col_sort) 
    f = open(filename) 
    for col, offset, length in index: 
     f.seek(offset) 
     print f.read(length).rstrip('\n') 

if __name__ == '__main__': 
    filename = 'somefile.txt' 
    sort_col = 2 
    print_sorted(filename, sort_col) 

Answer 4

chia ra thành các file có thể được sắp xếp trong bộ nhớ. Sắp xếp từng tệp trong bộ nhớ. Sau đó hợp nhất các tập tin kết quả.

Hợp nhất bằng cách đọc một phần của từng tệp được hợp nhất. Cùng một số tiền từ mỗi tệp để lại đủ không gian trong bộ nhớ cho kết quả đã hợp nhất. Sau khi hợp nhất lưu điều này. Lặp lại việc thêm khối dữ liệu đã hợp nhất vào tệp.

Điều này giảm thiểu tệp i/o và di chuyển xung quanh tệp trên đĩa.