Cách hiệu quả để lấy phần tử thiếu đầu tiên trong chuỗi thứ tự?

Question

Tôi có một chuỗi thứ tự như {1, 3, 5, 6, 8, 9} Tôi muốn lấy phần tử thiếu đầu tiên (2 trong ví dụ) hoặc max() nếu chuỗi không chứa phần tử bị thiếu. Bây giờ tôi đang làm như sau:

public static int GetRegisterNumber<T>(this IQueryable<T> enumerable, Func<T, bool> whereFunc, Func<T, int?> selectFunc) 
{ 
    var regNums = enumerable.OrderBy(selectFunc).Where(whereFunc).ToArray(); 

    if (regNums.Count() == 0) 
    { 
     return 1; 
    } 

    for (int i = 0; i < regNums.Count(); i++) 
    { 
     if (i + 1 != regNums[i]) 
     { 
      return regNums[i].Value + 1; 
     } 
    } 

    return regNums.Last().Value + 1; 
} 

Nhưng tôi nghĩ rằng có nhiều phương pháp nhanh hơn. Bất kỳ đề xuất?

Answer 1

Edit: Tôi chỉ nhận thấy rằng enumerable là IQueryable<T> nhưng selectFunc và whereFunc là loại Func<T, _>. Điều này sẽ làm cho các phiên bản Enumerable của OrderBy và Where được gọi thay vì sử dụng các cuộc gọi cơ sở dữ liệu. Bạn có thể muốn chuyển đổi chúng thành Expression<Func<T, _>> thay thế.

Nếu bạn không muốn đặt hàng regNums đầu tiên, đây là một giải pháp O (n) sân golf theo phong cách:

var max = regNums.Max(i => (int?)i) ?? 0; 
return Enumerable.Range(1, max + 1) 
       .Except(regNums) 
       .Min(); 

By dòng:

1. By đúc để int?, Max sẽ trả lại null nếu regNums trống, được kết hợp với 0.

2. Tạo chuỗi các đăng ký có thể có, bao gồm giá trị tiếp theo của chúng tôi nếu đầy.

3. Trừ bộ thanh ghi hiện tại.

4. Chọn mức thấp nhất.

Answer 2

Đề xuất: chạy mã của bạn thông qua trình hồ sơ. Sau đó, bạn sẽ biết nó ở đâu chậm. Trực giác, OrderBy là điều chậm nhất trong chương trình này. Nhưng trực giác về điều chậm nhất thường rất, rất sai. Sử dụng một hồ sơ.

Tất nhiên, bạn cũng nên loại bỏ sự thiếu hiệu quả lớn trong chương trình này. Hãy nhớ rằng, Count() đếm chuỗi bằng cách liệt kê lại nó. Count() không biết rằng bạn đã không thay đổi trình tự kể từ lần cuối bạn đếm nó! Bạn có thể muốn lưu trữ số thay vì tính toán lại nó mỗi lần, hoặc sử dụng Độ dài, vì bạn có một mảng.

Answer 3

Tôi có thể xem xét một số thứ như dưới đây; các Where có thể được thực hiện bên ngoài (như có thể chọn để được trung thực):

Nếu bạn mong muốn bắt đầu từ 1:

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable, 
    Func<T, int> selectFunc) 
{ 
    int expected = 1; 
    foreach (T item in enumerable) { 
     if (selectFunc(item) != expected) return expected; 
     expected++; 
    } 
    return expected; 
} 

Để bắt đầu với mục đầu tiên trong danh sách:

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable, 
    Func<T, int> selectFunc) 
{ 
    bool first = true; 
    int prev = -1; 
    foreach (T item in enumerable) 
    { 
     int val = selectFunc(item); 
     if(first) { 
      prev = val; 
      first = false; 
     } else if (val != prev + 1) { 
      return prev + 1; 
     } 
     prev = val; 
    } 
    return first ? 1 : prev + 1; 
} 

Nó không phải là rõ ràng như thế nào bạn muốn xử lý nulls, vì vậy tôi đã không. Lưu ý rằng điều này chỉ lặp lại sau khi và không đệm mọi thứ.

Answer 4

Như đã đề cập, trước tiên hãy sử dụng trình thu thập thông tin để tìm vị trí chậm. Nếu trình tự thực sự lớn, và thứ tự là chậm, bạn có thể sử dụng radix sort, đó là O (kn), trong đó k là số chữ số tối đa và n là số phần tử trong chuỗi. Các thuật toán sắp xếp dựa trên so sánh thường là O (n logn).

Bằng cách này, toàn bộ thuật toán sẽ là O (kn), tùy thuộc vào n, nhanh hơn tiệm cận và do đó có khả năng mở rộng hơn.

Answer 5

Giả sử rằng các chuỗi đến các giá trị đã được sắp xếp, làm thế nào về:

var upperBoundValue = values.Last() + 1; 
var firstMissingItem = Enumerable.Range(1, upperBoundValue).Except(values).First(); 

Nếu bạn đang thực hiện hoạt động này lặp đi lặp lại, bạn có thể tối ưu hóa quá trình này bằng cách lưu trữ một chỉ số để nơi cuối cùng mà bạn đang ở trong trình tự mà bạn tìm thấy một khoảng trống và bắt đầu lặp lại tiếp theo từ đó.

Answer 6

Tại sao không làm điều gì đó như tìm kiếm nhị phân?

Giả sử bạn có danh sách 10 thành phần dài. Đọc phần tử đầu tiên. Sau đó đọc phần tử thứ năm. Nếu phần tử thứ năm không phải là phần tử đầu tiên + 4 thì bạn biết có một số bị thiếu, nếu không bạn biết không có. Sau đó, chỉ cần lặp lại như thế này cho đến khi bạn tìm thấy phần tử bị thiếu đầu tiên hoặc đến cuối danh sách.

Điều này tất nhiên giả định bạn biết kích thước (không được đề cập rõ ràng trong câu hỏi), nhưng bạn đã chuyển đổi thành một mảng, vì vậy bạn nên biết.

O (log N) thay vì O (n)

Answer 7

Giả sử rằng OrderBy của bạn và Where đã được áp dụng:

int firstMissing = collection.TakeWhile((x, i) => x == ++i).LastOrDefault() + 1; 

Answer 8

Bạn đặt một thẻ LinqToSql trong câu hỏi của bạn. Tôi đoán bạn đang tìm kiếm một id "có sẵn đầu tiên", để bạn có thể tạo một bản ghi mới bằng cách sử dụng id này. Thay vào đó, hãy cân nhắc chuyển IDENTITY trong cơ sở dữ liệu.