Cách truy cập trực tiếp và hiệu quả vào tệp văn bản rất lớn?

Question

Tôi có một tệp văn bản rất lớn (+ 10GB) mà tôi muốn đọc cho một số kỹ thuật khai thác dữ liệu. Để làm điều đó, tôi sử dụng kỹ thuật song song với MPI vì vậy nhiều quá trình có thể truy cập cùng nhau vào cùng một tệp.
Thực tế, tôi muốn mỗi quá trình đọc N số dòng. Vì tệp không được cấu trúc (cùng số trường nhưng mỗi trường có thể chứa số ký tự khác nhau), tôi có nghĩa vụ phân tích cú pháp tệp và điều đó không song song và phải mất rất nhiều thời gian. Có cách nào để truy cập trực tiếp vào một số dòng cụ thể với tính năng phân tích cú pháp và đếm các dòng không? Cảm ơn sự giúp đỡ của bạn.

Answer 1

Nếu tệp của bạn không được lập chỉ mục khác, không có cách nào trực tiếp.

Lập chỉ mục có thể đáng giá (quét tìm một lần để tìm tất cả các kết thúc dòng và lưu trữ bù của mỗi dòng hoặc đoạn đường). Nếu bạn cần xử lý tệp nhiều lần và không thay đổi, chi phí lập chỉ mục có thể được bù đắp bằng cách sử dụng chỉ mục để chạy tiếp.

Nếu không, nếu bạn không cần tất cả các công việc để có chính xác cùng một số dòng/mục, bạn chỉ có thể giả mạo nó.
Tìm kiếm một giá trị đã cho (ví dụ 1G) và tìm dấu tách dòng gần nhất. Lặp lại tại offset 2G, vv cho đến khi bạn đã tìm thấy đủ điểm break.

Sau đó, bạn có thể kích hoạt các tác vụ song song của mình trên từng khối bạn đã xác định.

Answer 2

Không có không: cho đến khi bạn không đọc qua dữ liệu không xác định của bạn, không ai biết có bao nhiêu ký tự dòng mới. Độ phức tạp của vấn đề này là O (n) do đó có nghĩa là ít nhất một lần là bạn sẽ phải đọc toàn bộ tệp. Sau đó, bạn có thể muốn xây dựng một bảng chỉ mục nơi bạn ghi lại nơi có các ký tự dòng mới trong tệp của bạn: điều này có thể được sử dụng bởi tất cả quy trình và với fseek bạn có thể tăng tốc truy cập đáng kể hơn nữa.

Answer 3

Một vài lựa chọn khác ngoài những gì đã được đề cập ở đây rằng sẽ không yêu cầu quét toàn bộ file:

1. làm cho một quá trình tổng thể đẩy dòng qua ống/FIFOs để tiến trình con mà làm việc xử lý thực tế. Điều này có thể là một chút chậm hơn nhưng nếu nói 90% thời gian dành cho các quy trình con là việc crunching văn bản thực tế, nó sẽ ổn.

2. Bí quyết ngu ngốc nhưng hiệu quả: giả sử bạn có N quy trình và bạn có thể nói với từng quá trình bằng argv hoặc một số "số sê-ri", ví dụ: processor -serial_number [1|2|3...N] -num_procs N, tất cả chúng đều có thể đọc cùng một dữ liệu nhưng chỉ xử lý các dòng có lineno % num_procs == serial_number. nó kém hiệu quả hơn một chút bởi vì tất cả chúng sẽ đọc toàn bộ dữ liệu, nhưng một lần nữa, nếu chúng chỉ hoạt động trên mọi dòng Nth, và đó là những gì tiêu thụ phần lớn thời gian, bạn sẽ ổn thôi.