Cách tốt để lấy chìa khóa của giá trị cao nhất của một từ điển trong C#

Question

Tôi đang cố gắng lấy khóa của giá trị tối đa trong số Dictionary<string, double> results.

Đây là những gì tôi có cho đến nay:

double max = results.Max(kvp => kvp.Value); 
return results.Where(kvp => kvp.Value == max).Select(kvp => kvp.Key).First(); 

Tuy nhiên, vì đây dường như một chút không hiệu quả, tôi đã tự hỏi liệu có một cách tốt hơn để làm điều này.

Answer 1

tôi nghĩ rằng đây là O có thể đọc được hầu hết (n) câu trả lời sử dụng LINQ chuẩn

var max = results.Aggregate((l, r) => l.Value > r.Value ? l : r).Key; 

chỉnh sửa:. giải thích cho CoffeeAddict

Aggregate là LI Tên NQ cho khái niệm chức năng thường được biết Fold

Vòng lặp trên mỗi phần tử của tập hợp và áp dụng bất kỳ chức năng nào bạn cung cấp. Ở đây, hàm tôi cung cấp là hàm so sánh trả về giá trị lớn hơn. Khi vòng lặp, Aggregate ghi nhớ kết quả trả về từ lần cuối cùng nó được gọi là chức năng của tôi. Nó cung cấp thông tin này vào hàm so sánh của tôi dưới dạng biến số l. Biến số r là phần tử hiện được chọn.

Vì vậy, sau khi tổng hợp đã lặp trên toàn bộ tập hợp, nó trả về kết quả từ lần cuối cùng nó được gọi là hàm so sánh của tôi. Sau đó, tôi đọc .Key thành viên từ nó bởi vì tôi biết đó là một mục từ điển

Đây là một cách khác để nhìn vào nó [tôi không đảm bảo rằng đây biên dịch;)]

var l = results[0]; 
for(int i=1; i<results.Count(); ++i) 
{ 
    var r = results[i]; 
    if(r.Value > l.Value) 
     l = r;   
} 
var max = l.Key; 

Answer 2

Đây là phương pháp nhanh. Nó là O (n), là tối ưu. Vấn đề duy nhất tôi thấy là nó lặp qua từ điển hai lần thay vì chỉ một lần.

Bạn có thể làm điều đó lặp qua từ điển một lần bằng cách sử dụng MaxBy từ morelinq.

results.MaxBy(kvp => kvp.Value).Key; 

Answer 3

Tôi nghĩ rằng việc sử dụng Thư viện LINQ chuẩn này nhanh như bạn có thể thực hiện.

Answer 4

Có lẽ đây không phải là cách sử dụng tốt cho LINQ. Tôi thấy 2 bản quét đầy đủ của từ điển bằng cách sử dụng giải pháp LINQ (1 để có được giá trị tối đa, sau đó một giá trị khác để tìm kvp để trả về chuỗi.

Bạn có thể làm điều đó trong 1 lần với mục đích "cũ":

 

KeyValuePair<string, double> max = new KeyValuePair<string, double>(); 
foreach (var kvp in results) 
{ 
    if (kvp.Value > max.Value) 
    max = kvp; 
} 
return max.Key; 
 

Answer 5

Sau khi đọc nhiều gợi ý, tôi quyết định điểm chuẩn cho họ và chia sẻ kết quả.

Mã kiểm tra:

// TEST 1 

for (int i = 0; i < 999999; i++) 
{ 
    KeyValuePair<GameMove, int> bestMove1 = possibleMoves.First(); 
    foreach (KeyValuePair<GameMove, int> move in possibleMoves) 
    { 
    if (move.Value > bestMove1.Value) bestMove1 = move; 
    } 
} 

// TEST 2 

for (int i = 0; i < 999999; i++) 
{ 
    KeyValuePair<GameMove, int> bestMove2 = possibleMoves.Aggregate((a, b) => a.Value > b.Value ? a : b); 
} 

// TEST 3 

for (int i = 0; i < 999999; i++) 
{ 
    KeyValuePair<GameMove, int> bestMove3 = (from move in possibleMoves orderby move.Value descending select move).First(); 
} 

// TEST 4 

for (int i = 0; i < 999999; i++) 
{ 
    KeyValuePair<GameMove, int> bestMove4 = possibleMoves.OrderByDescending(entry => entry.Value).First(); 
} 

Kết quả:

Average Seconds Test 1 = 2.6 
Average Seconds Test 2 = 4.4 
Average Seconds Test 3 = 11.2 
Average Seconds Test 4 = 11.2 

Đây chỉ là để cung cấp cho một ý tưởng về hiệu suất tương đối của chúng.

Nếu tối ưu hóa 'foreach' của bạn là nhanh nhất, nhưng LINQ nhỏ gọn và linh hoạt.

Answer 6

Làm thế nào để thực hiện nó song song bằng cách sử dụng Interlocked.Exchange cho an toàn luồng :) Lưu ý rằng Interlocked.Exchange sẽ chỉ hoạt động với kiểu tham chiếu (ví dụ: struct hoặc cặp giá trị khóa (trừ khi được bọc trong một lớp) không làm việc để giữ giá trị max

Dưới đây là một ví dụ từ mã của riêng tôi:.

//Parallel O(n) solution for finding max kvp in a dictionary... 
ClassificationResult maxValue = new ClassificationResult(-1,-1,double.MinValue); 
Parallel.ForEach(pTotals, pTotal => 
{ 
    if(pTotal.Value > maxValue.score) 
    { 
     Interlocked.Exchange(ref maxValue, new     
      ClassificationResult(mhSet.sequenceId,pTotal.Key,pTotal.Value)); 
    } 
}); 

EDIT (mã cập nhật để tránh tình trạng chủng tộc có thể ở trên):

Dưới đây là một mô hình mạnh mẽ hơn cũng cho thấy việc chọn một giá trị nhỏ nhất song song. Tôi nghĩ rằng đây đề cập đến những mối quan tâm đề cập trong các ý kiến ​​dưới đây liên quan đến một tình trạng chủng tộc có thể:

int minVal = int.MaxValue; 
Parallel.ForEach(dictionary.Values, curVal => 
{ 
    int oldVal = Volatile.Read(ref minVal); 
    //val can equal anything but the oldVal 
    int val = ~oldVal; 

    //Keep trying the atomic update until we are sure that either: 
    //1. CompareExchange successfully changed the value. 
    //2. Another thread has updated minVal with a smaller number than curVal. 
    // (in the case of #2, the update is no longer needed) 
    while (oldval > curVal && oldval != val) 
    { 
    val = oldval; 
    oldval = Interlocked.CompareExchange(ref minVal, curVal, oldval); 
    } 
}); 

Answer 7

Bạn có thể sắp xếp từ điển bằng cách sử dụng OrderBy (cho thấy giá trị min) hoặc OrderByDescending (đối với giá trị max) sau đó nhận được phần tử đầu tiên. Nó cũng giúp khi bạn cần tìm max thứ hai/yếu tố phút

Nhận key từ điển bằng giá trị tối đa:

double min = results.OrderByDescending(x => x.Value).First().Key; 

Nhận key từ điển bằng giá trị min:

double min = results.OrderBy(x => x.Value).First().Key; 

Nhận key từ điển bằng max thứ hai giá trị:

double min = results.OrderByDescending(x => x.Value).Skip(1).First().Key; 

Lấy khóa từ điển theo giá trị phút thứ hai:

double min = results.OrderBy(x => x.Value).Skip(1).First().Key; 

Answer 8

ít phương pháp khuyến nông:

public static KeyValuePair<K, V> GetMaxValuePair<K,V>(this Dictionary<K, V> source) 
    where V : IComparable 
{ 
    KeyValuePair<K, V> maxPair = source.First(); 
    foreach (KeyValuePair<K, V> pair in source) 
    { 
     if (pair.Value.CompareTo(maxPair.Value) > 0) 
      maxPair = pair; 
    } 
    return maxPair; 
} 

Sau đó:

int keyOfMax = myDictionary.GetMaxValuePair().Key;