C# N cách hợp nhất để sắp xếp bên ngoài

Question

Làm cách nào tốt nhất để thực hiện cách hợp nhất N cho N tệp được sắp xếp?

Cho phép nói rằng tôi có 9 tệp được sắp xếp với 10 bản ghi mỗi tệp? Làm cách nào để hợp nhất các tệp này để tạo một tệp lớn với 90 bản ghi được sắp xếp?

Answer 1

Chiến lược có thể phụ thuộc vào lượng dữ liệu.

1. Nếu dữ liệu sẽ phù hợp trong bộ nhớ bạn có thể đọc tất cả các dữ liệu vào một danh sách, sắp xếp nó, và viết nó ra
2. Nếu bạn muốn loại bỏ bản sao sử dụng một HashSet thay vì một danh sách
3. Nếu nó sẽ không vừa với bộ nhớ, mở tất cả các tệp để đọc, so sánh bản ghi đầu tiên của mỗi tệp và ghi ra mức thấp nhất. Sau đó tiến lên tệp bạn đọc. Lặp lại tất cả các tệp cho đến khi tất cả chúng hết và được ghi vào tệp mới.
4. Nếu bạn muốn xóa các bản sao, hãy làm như trên, nhưng bỏ qua bất kỳ bản ghi nào bằng văn bản cuối cùng.

Dưới đây là ví dụ mã đọc N tập tin văn bản được sắp xếp và hợp nhất chúng. Tôi đã không bao gồm kiểm tra trùng lặp, nhưng nó phải dễ thực hiện.

Đầu tiên là lớp trợ giúp.

class MergeFile : IEnumerator<string> 
{ 
    private readonly StreamReader _reader; 

    public MergeFile(string file) 
    { 
     _reader = File.OpenText(file); 
     Current = _reader.ReadLine(); 
    } 

    public string Current { get; set; } 

    public void Dispose() 
    { 
     _reader.Close(); 
    } 

    public bool MoveNext() 
    { 
     Current = _reader.ReadLine(); 
     return Current != null; 
    } 

    public void Reset() 
    { 
     throw new NotImplementedException(); 
    } 

    object IEnumerator.Current 
    { 
     get { return Current; } 
    } 
} 

Và sau đó mã để đọc và sáp nhập (nó nên được refactored cho rõ ràng trong sản xuất):

// Get the file names and instantiate our helper class 
List<IEnumerator<string>> files = Directory.GetFiles(@"C:\temp\files", "*.txt").Select(file => new MergeFile(file)).Cast<IEnumerator<string>>().ToList(); 
List<string> result = new List<string>(); 
IEnumerator<string> next = null; 
while (true) 
{ 
    bool done = true; 
    // loop over the helpers 
    foreach (var mergeFile in files) 
    { 
     done = false; 
     if (next == null || string.Compare(mergeFile.Current, next.Current) < 1) 
     { 
      next = mergeFile; 
     } 
    } 
    if (done) break; 
    result.Add(next.Current); 
    if (!next.MoveNext()) 
    { 
     // file is exhausted, dispose and remove from list 
     next.Dispose(); 
     files.Remove(next); 
     next = null; 
    } 
} 

Answer 2

Tôi giả định rằng có thể có rất nhiều dữ liệu hơn thì bạn đã cho trong ví dụ của bạn . Nếu bạn có thể mở tất cả các tệp cùng một lúc, bạn có thể sử dụng thuật toán này:

• Đọc dòng đầu tiên từ mỗi tệp để bạn có 10 dòng trong bộ nhớ, một dòng từ mỗi tệp.
• Đặt các dòng vào hàng đợi ưu tiên theo thứ tự sắp xếp.
• Lấy phần tử nhỏ nhất (được sắp xếp đầu tiên) ra khỏi hàng đợi ưu tiên và ghi vào tệp đầu ra.
• Đọc thêm một dòng từ tệp tương ứng mà dòng xuất phát và đưa nó vào hàng đợi ưu tiên.
• Lặp lại cho đến khi tất cả các tệp được đọc đến cùng.

Lưu ý rằng bạn không phải đọc tất cả các tệp vào bộ nhớ cùng một lúc, vì vậy điều này sẽ hoạt động tốt nếu bạn có số lượng tệp lớn hợp lý, nhưng không phải nếu bạn có nhiều tệp nhỏ.

Nếu bạn có nhiều tệp nhỏ, bạn nên hợp nhất chúng thành các nhóm để tạo một tệp đầu ra cho mỗi nhóm, sau đó lặp lại quy trình để hợp nhất các nhóm mới này.

Trong C#, bạn có thể sử dụng ví dụ: SortedDictionary để triển khai hàng đợi ưu tiên.

Answer 3

Giải quyết nhận xét trong câu trả lời khác:

Nếu bạn có số lượng tệp thay đổi, dưới đây là những gì tôi muốn làm. Đây chỉ là một phác thảo để có được ý tưởng trên; mã này không biên dịch, tôi đã nhận được tên phương thức sai, v.v.

// initialize the data structures 
var priorityQueue = new SortedDictionary<Record, Stream>(); 
var streams = new List<Stream>(); 
var outStream = null; 
try 
{ 
    // open the streams. 
    outStream = OpenOutputStream(); 
    foreach(var filename in filenames) 
    streams.Add(GetFileStream(filename)); 
    // initialize the priority queue 
    foreach(var stream in streams) 
    { 
    var record = ReadRecord(stream); 
    if (record != null) 
     priorityQueue.Add(record, stream); 
    // the main loop 
    while(!priorityQueue.IsEmpty) 
    { 
    var record = priorityQueue.Smallest; 
    var smallestStream = priorityQueue[record]; 
    WriteRecord(record, outStream); 
    priorityQueue.Remove(record); 
    var newRecord = ReadRecord(smallestStream); 
    if (newRecord != null) 
     priorityQueue.Add(newRecord, smallestStream); 
    } 
} 
finally { clean up the streams } 

Điều đó có hợp lý không? Bạn cứ tiếp tục lấy thứ nhỏ nhất ra khỏi hàng đợi ưu tiên và thay thế nó bằng bản ghi tiếp theo trong luồng đó, nếu có. Cuối cùng, hàng đợi sẽ trống và bạn sẽ hoàn thành.

Answer 4

Tôi có thể nói không sử dụng hàng đợi ưu tiên, không sử dụng IEnumerable. Cả hai đều rất chậm.

Đây là một cách nhanh chóng để sắp xếp hoặc ghép các tập tin được sắp xếp trong bộ nhớ bên ngoài:

http://www.codeproject.com/KB/recipes/fast_external_sort.aspx