Tôi có phương pháp không thực hiện, làm cách nào để cải thiện hiệu quả của nó?

Question

Tôi có một phương pháp đơn giản để so sánh một mảng các đối tượng FileInfo với danh sách tên tệp để kiểm tra xem tệp nào đã được xử lý. Danh sách chưa xử lý sau đó được trả về.

Vòng lặp của phương thức này lặp lại cho khoảng 250.000 đối tượng FileInfo. Điều này đang dành một lượng thời gian khiêu dâm để cạnh tranh.

Tính không hiệu quả rõ ràng là lệnh gọi Chứa phương thức trên bộ sưu tập processedFiles.

Trước tiên làm cách nào để kiểm tra để chắc chắn rằng sự nghi ngờ của tôi là đúng về nguyên nhân và thứ hai, làm cách nào tôi có thể cải thiện phương pháp để tăng tốc quá trình?

public static List<FileInfo> GetUnprocessedFiles(FileInfo[] allFiles, List<string> processedFiles) 
{ 
List<FileInfo> unprocessedFiles = new List<FileInfo>(); 
foreach (FileInfo fileInfo in allFiles) 
{ 
    if (!processedFiles.Contains(fileInfo.Name)) 
    { 
     unprocessedFiles.Add(fileInfo); 
    } 
    } 
    return unprocessedFiles; 
} 

Answer 1

Một List<T> 's chạy trong thời gian tuyến tính, vì nó có khả năng phải liệt kê toàn bộ danh sách để chứng minh sự tồn tại/không sự tồn tại của một mục. Tôi khuyên bạn nên sử dụng một số HashSet<string> hoặc tương tự thay thế. Phương pháp Contains của HashSet<T> được thiết kế để chạy trong thời gian O(1) không đổi, tức là nó không phụ thuộc vào số lượng mục trong bộ này.

thay đổi nhỏ này sẽ làm cho các phương pháp toàn bộ chạy trong thời gian tuyến tính:

public static List<FileInfo> GetUnprocessedFiles(FileInfo[] allFiles, 
             List<string> processedFiles) 
{ 
    List<FileInfo> unprocessedFiles = new List<FileInfo>(); 
    HashSet<string> processedFileSet = new HashSet<string>(processedFiles); 

    foreach (FileInfo fileInfo in allFiles) 
    { 
     if (!processedFileSet.Contains(fileInfo.Name)) 
     { 
      unprocessedFiles.Add(fileInfo); 
     } 
    } 

    return unprocessedFiles; 
} 

tôi sẽ đề nghị 3 cải tiến, nếu có thể:

1. Đối thêm hiệu quả, lưu trữ các tập tin xử lý một tập hợp tại nguồn, để phương thức này có một tham số ISet<T>. Bằng cách này, bạn sẽ không phải xây dựng lại bộ này mỗi lần.
2. Cố gắng không trộn lẫn và khớp với các biểu tượng khác nhau của cùng một thực thể (string và FileInfo) theo cách này. Chọn một và đi với nó.
3. Bạn cũng có thể muốn xem xét phương pháp HashSet<T>.ExceptWith thay vì tự làm vòng lặp. Hãy nhớ rằng điều này sẽ làm thay đổi bộ sưu tập.

Nếu bạn có thể sử dụng LINQ, và bạn có thể đủ khả năng để xây dựng một bộ trên tất cả các cuộc gọi, đây là một cách khác:

public static IEnumerable<string> GetUnprocessedFiles 
(IEnumerable<string> allFiles, IEnumerable<string> processedFiles) 
{ 
    // null-checks here 
    return allFiles.Except(processedFiles);  
} 

Answer 2

1. Sắp xếp mảng tìm kiếm theo tên file
2. employ Array.BinarySearch<T>() để tìm kiếm mảng. Điều này sẽ xuất hiện ở mức hiệu suất O (logN).

Answer 3

để kiểm tra xem một danh sách chứa một phần tử là nhanh hơn với một danh sách được sắp xếp Contains phương pháp

Answer 4

tôi sẽ cố gắng để chuyển đổi danh sách processedFiles đến một HashSet. Với một danh sách, nó cần phải lặp lại danh sách mọi lúc bạn gọi chứa. Một HashSet là một hoạt động O (1).

Answer 5

Bạn có thể sử dụng từ điển/hastable như lớp để tăng tốc quá trình tra cứu đáng kể. Ngay cả dịch danh sách gửi vào một hashtable một lần, sau đó sử dụng một trong đó sẽ được nhanh hơn nhiều so với những gì bạn đang sử dụng.

Answer 6

Chỉ cần được quá pedantic ...

Nếu bạn biết rằng cả hai danh sách đều được sắp xếp (FileInfo liệt kê thường đến trước sắp xếp, vì vậy phương pháp này có thể áp dụng đối với bạn), sau đó bạn có thể đạt được hiệu suất tuyến tính đúng mà không tốn thời gian và bộ nhớ của một hashset. Hashset xây dựng vẫn yêu cầu thời gian tuyến tính để xây dựng, vì vậy phức tạp là gần gũi hơn với O (n + m); hashset phải phân bổ nội bộ các tham chiếu đối tượng bổ sung cho tối đa 250k chuỗi trong trường hợp của bạn và điều đó sẽ có giá bằng các thuật ngữ GC.

Something như nửa nướng tổng quát này có thể giúp:

public static IEnumerable<string> GetMismatches(IList<string> fileNames, IList<string> processedFileNames, StringComparer comparer) 
    { 
     var filesIndex = 0; 
     var procFilesIndex = 0; 

     while (filesIndex < fileNames.Count) 
     { 
      if (procFilesIndex >= processedFileNames.Count) 
      { 
       yield return files[filesIndex++]; 
      } 
      else 
      { 
       var rc = comparer.Compare(fileNames[filesIndex], processedFileNames[procFilesIndex]); 
       if (rc != 0) 
       { 
        if (rc < 0) 
        { 
         yield return files[filesIndex++]; 
        } 
        else 
        { 
         procFilesIndex++; 
        } 
       } 
       else 
       { 
        filesIndex++; 
        procFilesIndex++; 
       } 
      } 
     } 

     yield break; 
    } 

tôi sẽ đồng ý mạnh mẽ với Ani mà gắn bó với một kiểu generic hay kinh điển là một điều rất tốt Thật vậy. Nhưng tôi sẽ cung cấp cho tôi -1 cho tổng quát chưa hoàn thành và -1 cho sự thanh lịch ...