Phân tích cú pháp một tệp văn bản lớn hiệu quả trong C#

Question

Tôi cần đọc một tệp văn bản được phân cách bằng không gian lớn và đếm số lượng phiên bản của mỗi mã trong tệp. Về cơ bản, đây là kết quả của việc chạy một số thí nghiệm hàng trăm nghìn lần. Hệ thống này spits ra một tập tin văn bản trông giống loại như thế này:

A7PS A8PN A6PP23 ... 

Và có nghĩa là hàng trăm ngàn những mục này và tôi cần phải đếm số lần xuất hiện của mỗi người trong số các mã.

Tôi đoán tôi có thể chỉ cần mở StreamReader và đi qua từng dòng, chia tách ký tự khoảng trắng. Xem mã đã gặp phải chưa và thêm 1 vào số mã đó. Tuy nhiên, đó có lẽ là khá ngây thơ, cho kích thước của dữ liệu.

Bất kỳ ai biết thuật toán hiệu quả để xử lý loại xử lý này?

UPDATE:

OK, vì vậy sự đồng thuận có vẻ là cách tiếp cận của tôi là dọc theo dòng đúng

Những gì tôi muốn được quan tâm để nghe những điều như thế - đó là hiệu quả hơn - StreamReader. TextReader, BinaryReader

Cấu trúc tốt nhất để lưu trữ từ điển kết quả của tôi là gì? HashTable, SortedList, HybridDictionary

Nếu không có ngắt dòng thì tập tin (tôi chưa được đưa ra mẫu) sẽ chỉ tách toàn bộ mọi thứ trên một không gian không hiệu quả?

Về cơ bản, tôi đang xem xét làm cho nó như performant càng tốt

nhờ một lần nữa

Answer 1

Cách tiếp cận của bạn có vẻ ổn.

1. Đọc trong dòng mỗi dòng
2. Chia mỗi dòng bằng không gian
3. Thêm một kỷ lục để một cuốn từ điển nếu nó không tồn tại được nêu và nếu nó không tồn tại, làm giá trị ++

Answer 2

tôi sẽ nói rằng nói chung cách tiếp cận của bạn là đúng, nhưng vẫn có khả năng xử lý song song. Tôi sẽ đề nghị bạn nên bắt đầu nhiều chủ đề hoặc nhiệm vụ (trong .NET 4) mỗi phần phân tích cú pháp/tập tin. Cũng thay vì đọc từng dòng một, đọc theo đoạn byte - sẽ cho hiệu suất tốt hơn từ quan điểm của đĩa IO.

Chỉnh sửa: Đây là phác thảo của giải pháp.

1. Hãy nói rằng chúng tôi sẽ xử lý M khối của N ký tự vào thời điểm đó (vì chúng tôi muốn giới hạn dung lượng bộ nhớ cần thiết và số lượng chủ đề được sử dụng).
2. Phân bổ bộ đệm ký tự N * M. Chúng tôi sẽ sử dụng bộ đệm này theo chu kỳ.
3. Sẽ sử dụng mẫu người tiêu dùng của nhà sản xuất. Nhà sản xuất sẽ lấp đầy bộ đệm. Nó sẽ cố gắng tìm ranh giới từ gần ranh giới đoạn (tức là gần mọi Nth ký tự). Vì vậy, chúng tôi sẽ có M khối của khoảng N ký tự với bắt đầu và chỉ mục kết thúc trong bộ đệm
4. Bây giờ khởi chạy các chuỗi công việc M để xử lý từng đoạn. Mỗi nhân viên sẽ sử dụng từ điển riêng của mình để đếm từ - điều này sẽ loại bỏ nhu cầu đồng bộ hóa luồng.
5. Tổng hợp các kết quả vào cuối lần lặp lại. Quá trình này cần phải được lặp lại cho đến khi toàn bộ tập tin được đọc.

Tất nhiên, tôi giả sử các tệp rất lớn để thực hiện phương pháp này. Tôi có thể sẽ sử dụng tra cứu ký tự kiểu cũ trong bộ đệm để tìm mã đánh dấu ranh giới từ là không an toàn để tránh kiểm tra ràng buộc.

Answer 3

Ở cấp độ rất cơ bản, tôi bắt đầu với một Dictionary<string, int>, string.split tài liệu trên không gian và tiếp tục đếm thông qua phân tích cú pháp đơn giản của dữ liệu đó.

string.split là một phương pháp tương đối mạnh mẽ, và ai đó chắc chắn sẽ sửa tôi nếu tôi sai, được xây dựng để sử dụng cụm từ thông dụng và vô cùng phức tạp hơn những gì bạn cần cho kịch bản này.

Viết phương pháp tách riêng của bạn có thể sẽ là giải pháp khả thi hơn so với giải pháp trong khuôn khổ. Tôi khuyên bạn nên sử dụng phiên bản có sẵn trước tiên như được mô tả ở trên, sau đó viết lại của riêng bạn nếu bạn xác định rằng hiệu suất là một vấn đề.

Ian

Answer 4

Tôi đồng ý với nhận xét của PoweRoy: tại sao bạn không thử? Có lẽ không có vấn đề trong thực tế.

Nếu bạn cần điều gì đó khác, bạn có thể thử viết một số mã có mã số Stream và trả về số IEnumerable<string>. Nó sẽ đọc ký tự từ đầu vào của nó cùng một lúc - nếu bạn cần đệm cho hiệu quả bạn luôn có thể quấn FileStream bạn đang thực sự đem lại mã này trong một BufferStream - (? Hoặc có thể một EOL) và kiểm tra xem đó là một không gian. Nếu không, nó sẽ thêm ký tự vào một bộ đệm chuỗi (có lẽ là StringBuilder?), Nhưng nếu nó là nó sẽ yield return bộ đệm chuỗi hiện tại và xóa nó.

Sau đó, bạn chỉ có thể foreach qua kết quả của việc gọi mã này trên nội dung của tệp và bạn sẽ nhận được mã từ từng tệp một.

Sau đó, bạn có thể sử dụng một số loại cấu trúc dữ liệu như số Dictionary<string,int> để đếm số lần xuất hiện cho mỗi mã, giữ mã là khóa và tính là giá trị. Nhưng bước này sẽ giống nhau nếu bạn đọc từng dòng tệp và sử dụng string.Split để phân tách chúng trên không gian.

Answer 5

Nếu không có giới hạn nào khác, bạn phải đọc qua tệp hoàn chỉnh như bạn đã mô tả.

Để lưu mã và số bạn nên sử dụng cơ sở hạ tầng cho phép tìm kiếm và chèn vào thời gian O (nhật ký n). SortedDictionary sẽ làm điều đó trong C#.

EDIT:

cấu trúc tốt nhất để lưu trữ từ điển của tôi về kết quả là gì? HashTable, SortedList, HybridDictionary

Vì đơn đặt hàng được sắp xếp có vẻ như không được yêu cầu một HybridDictionary hoặc một Dictionary sẽ phí phạm tốt hơn trong hầu hết các trường hợp. SortedList có lẽ sẽ là giải pháp chậm nhất, bởi vì chèn có O (n). Bạn nên làm một số xét nghiệm với các triển khai khác nhau nếu hiệu suất là rất quan trọng.

Answer 6

Nếu bạn muốn thử một thứ gì đó khác, bạn có thể thử sử dụng BinaryReader và đọc byte luồng theo byte và tăng lượt truy cập mỗi lần bạn gặp phải một không gian.

Answer 7

Hàng trăm nghìn bản ghi không quá nhiều. Tôi sẽ sử dụng một số Dictionary<string,int>. Để lưu trữ khóa và số đếm.

Nhưng nếu bạn gặp vấn đề về bộ nhớ, tại sao không sử dụng cơ sở dữ liệu, ngay cả cơ sở dữ liệu như SQL Compact hoặc SQLite. Tạo một bảng có bản ghi chứa khóa và số đếm.

Giữ dữ liệu trong bộ nhớ nhanh nhất cho một lượng nhỏ dữ liệu, nhưng khi bạn đạt tới giới hạn bộ nhớ máy tính, cơ sở dữ liệu sẽ nhanh hơn.

Answer 8

static string LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 
    static string NUMBERS = "1234567890"; 
    static Random rdGen = new Random(); 
    static Dictionary<string, int> myDic = new Dictionary<string, int>(); 
    static void WriteTest(int max) 
    { 
     myDic = new Dictionary<string, int>(); 
     Stopwatch sw = new Stopwatch(); 
     sw.Start(); 
     for (int i = 0; i < max; i++) 
     { 
      string code = LETTERS[rdGen.Next(0, 26)].ToString() + NUMBERS[rdGen.Next(0, 10)].ToString() + LETTERS[rdGen.Next(0, 26)].ToString() + LETTERS[rdGen.Next(0, 26)].ToString(); 
      if (myDic.ContainsKey(code)) myDic[code]++; 
      else 
      { 
       myDic[code] = 1; 
      } 
     } 
     sw.Stop(); 
     Console.WriteLine(max.ToString() + " itérations : " + sw.ElapsedMilliseconds.ToString()); 

    } 

WriteTest (10000000); // Mất 7,5 giây.

Có vẻ như nó khá hiệu quả đối với tôi.