Cách nhanh/hiệu quả để lấy chỉ mục giá trị tối thiểu trong Danh sách <T>?

Question

Có cách nào để tìm chỉ số giá trị tối thiểu hiệu quả hơn/nhanh hơn điều này không?

int minimumValueIndex = List.IndexOf(List.Min()); 

Answer 1

Có, bạn có thể xóa phí trên List.IndexOf() bằng cách tạo tiện ích mở rộng tùy chỉnh Min(). (Thực sự, Enumerable.Min() nên có một phần mở rộng lựa chọn ban đầu yếu tố bằng phím thay vì chọn một chuyển đổi. Giám sát Điều này đặc biệt đau đớn trong những tình huống như thế này.)

public static int IndexOfMin(this IList<int> self) 
{ 
    if (self == null) { 
     throw new ArgumentNullException("self"); 
    } 

    if (self.Count == 0) { 
     throw new ArgumentException("List is empty.", "self"); 
    } 

    int min = self[0]; 
    int minIndex = 0; 

    for (int i = 1; i < self.Count; ++i) { 
     if (self[i] < min) { 
      min = self[i]; 
      minIndex = i; 
     } 
    } 

    return minIndex; 
} 

Answer 2

Min tính: Tìm giá trị Min trong một bộ sưu tập không thể được thực hiện nhanh hơn so với O (n) để nó có thể là không có cách nào tốt hơn nhưng chỉ là một khác nhau trong phong cách mã.

Tìm bước: tùy thuộc vào sự cố của bạn, bạn có thể sử dụng một số cấu trúc dữ liệu đặc biệt (như cây nhị phân, cây heap, ...) để bạn có thể tìm chỉ mục nhanh hơn.

Sử dụng thứ gì đó như cây min-heap bạn có thể nhận giá trị tối thiểu bằng O (1) trong một số chức năng Add, Remove đặc biệt.

Answer 3

Theo kinh nghiệm của riêng tôi, các phương pháp tổng hợp LINQ như Array.Max() và Array.Min() thường chậm hơn hướng dẫn sử dụng cho vòng lặp. Vì vậy, bạn có thể xem xét một cái gì đó như thế này như một cách tiếp cận khác:

int minima=0; 
int mindex=0; 

for(int i=0;i<List.Count;i++) 
{ 
    if (List[i]<minima) 
     {minima=List[i]; mindex=i;} 
} 

Bạn luôn có thể kiểm tra tốc độ của cả hai phương pháp trên môi trường của bạn bằng cách sử dụng System.Diagnostics.StopWatch.

Answer 4

Chắc chắn. Chỉ cần viết hàm Min của riêng bạn, thay vì sử dụng LINQ, theo dõi chỉ mục của giá trị tối thiểu hiện tại. Bằng cách đó, bạn có thể tránh phải tìm chỉ mục của mục dựa trên giá trị tối thiểu của nó.

Answer 5

Nếu có thể, theo dõi các giá trị min/index là các giá trị được đặt trong danh sách, vì vậy bạn không cần lặp qua danh sách đầy đủ. Sau đó, nếu các giá trị mới được thêm vào danh sách, hãy kiểm tra chúng dựa vào giá trị tối thiểu mà bạn đã lưu và thay đổi giá trị tối thiểu mới nếu cần.

Tất nhiên điều đó có thể không phù hợp với hoàn cảnh của bạn.

Answer 6

Có vấn đề với câu trả lời được đăng bởi @cdhowie ở chỗ nó giả định rằng một IList<T> có thể truy cập hiệu quả một mục cụ thể thông qua chỉ mục của nó. Trong khi nó đúng với các mảng và List[T], nó được bảo đảm theo cách không đảm bảo (lấy ví dụ, một danh sách được liên kết đơn lẻ thực hiện Ilist<T>).

Nếu tôi đã đi để làm điều này trong một, LINQy cách chung chung, tôi muốn làm một cái gì đó như:

public static IndexOfMinValue<T>(this IList<T> list) where T:IComparable 
{ 
    if (list == null) throw new ArgumentNullException("list") ; 
    int? offset = null ; 
    T min = default(T) ; 

    int i = 0 ; 
    foreach (T item in list) 
    { 
    if (!offset.HasValue || item.CompareTo(min) < 0) 
    { 
     offset = i ; 
     min = item ; 
    } 
    ++i ; 
    } 

    if (!offset.HasValue) throw new ArgumentOutOfRangeException("list","list is empty") ; 
    return offset.Value ; 
} 

Hoặc, cho là sạch hơn, vì chúng ta thoát khỏi khởi tạo không liên quan và không liên quan một so sánh trong thân của vòng lặp:

public static int IndexOfMin<T>(this IList<T> list) where T:IComparable 
{ 
    if (list == null) throw new ArgumentNullException("list") ; 

    IEnumerator<T> enumerator = list.GetEnumerator() ; 
    bool   isEmptyList = ! enumerator.MoveNext() ; 

    if (isEmptyList) throw new ArgumentOutOfRangeException("list","list is empty") ; 

    int minOffset = 0 ; 
    T minValue = enumerator.Current ; 
    for (int i = 1 ; enumerator.MoveNext() ; ++i) 
    { 
    if (enumerator.Current.CompareTo(minValue) >= 0) continue ; 
    minValue = enumerator.Current ; 
    minOffset = i ; 
    } 

    return minOffset ; 
} 

Bạn cũng có thể sử dụng chứng khoán LINQ Aggregate() quá tải, mặc dù nó không có bụi hoặc đơn giản hơn so với phương pháp brute force (có thể là kém hiệu quả, quá, IMHO):

IList<int> = GetSomeIntegers() ; 

int minIndex = list.Aggregate((Tuple<int,int,int>)null, 
    (acc , item) => { 
    int offset  = 0 ; 
    int minValue = item ; 
    int minOffset = 0 ; 
    if (acc != null) 
    { 
     offset = acc.Item3 + 1 ; 
     minValue = item < acc.Item1 ? item : acc.Item1 ; 
     minOffset = item < acc.Item1 ? offset : acc.Item2 ; 
    } 
    return new Tuple<int, int, int>(minValue , minOffset , offset) ; 
    }).Item2 ; 

Answer 7

Tôi đã cải thiện @ cdhowie answer một chút để làm cho nó mạnh mẽ hơn. Nếu có nhiều hơn một phần tử tối thiểu, thì phương thức này sẽ trả về phần tử đầu tiên.

public static T GetMin<T, TOrder>(this IEnumerable<T> self, Func<T, TOrder> orderFunc, 
            out int minIndex, IComparer<TOrder> cmp = null) 
{ 
    if (self == null) throw new ArgumentNullException("self");    

    IEnumerator<T> selfEnumerator = self.GetEnumerator(); 
    if (!selfEnumerator.MoveNext()) throw new ArgumentException("List is empty.", "self"); 

    if (cmp == null) cmp = Comparer<TOrder>.Default; 

    T min = selfEnumerator.Current; 
    minIndex = 0; 
    int intCount = 1; 
    while (selfEnumerator.MoveNext()) 
    { 
     if (cmp.Compare(orderFunc(selfEnumerator.Current), orderFunc(min)) < 0) 
     { 
      min = selfEnumerator.Current; 
      minIndex = intCount; 
     } 
     intCount++; 
    } 

    return min; 
} 

Answer 8

tôi là lười biếng vì vậy tôi sẽ sử dụng:

List.Sort();/* sorts the values least to greatest */ 
List[0];/* first item has the least value */