Tìm kiếm Hierarchical Danh sách

Question

Tôi đã có một lớp đơn giản định nghĩa là:

public class IndexEntry 
{ 
    public bool HighScore { get; set; } 
    public List<IndexEntry> SubEntries { get; set; } 
    //Other properties, etc... 
} 

bây giờ tôi cần phải tìm kiếm thông qua một danh sách để tìm ra một mục mà có điểm cao tài sản của nó thiết lập để đúng. Vì nó không phải là một danh sách phẳng, nhưng một hệ thống cấp bậc có thể là một số lượng không biết cấp độ sâu và vì mục tôi đang tìm kiếm có thể chứa trong bất kỳ danh sách SubEnties nào, tôi không thể làm một Lambda đơn giản như này:

var foundHighScore = myList.FirstOrDefault(IE => IE.HighScore == true); 

Đây là mã tôi có. Tôi biết nó xấu xí (ít nhất là nó có vẻ như vậy với tôi). Nó hoạt động, nhưng chậm như tội lỗi trên một danh sách thậm chí từ xa lớn và tôi chắc chắn phải có một cách tốt hơn.

private IndexEntry GetHighScoreEntry(IEnumerable<IndexEntry> entryList) 
{ 
    IndexEntry result = null; 
    IndexEntry recursiveResult = null; 
    foreach (IndexEntry currentEntry in entryList) 
    { 
     if (currentEntry.HighScore) 
     { 
      result = currentEntry; 
      break; //Don't need to look anymore, we found our highscore.; 
     } 
     else 
     { 
      if ((currentEntry.SubEntries == null) || (currentEntry.SubEntries.Count < 1)) 
      { 
       continue; 
      } 
      else 
      { 
       recursiveResult = GetHighScoreEntry(currentEntry.SubEntries); 
       if (recursiveResult == null) 
        continue; 
        result = recursiveResult; 
       break; 
      } 
     } 
    } 
    return result; 
} 

Tôi đã tin rằng có cách tốt hơn bằng cách sử dụng lambda phức tạp hơn một chút hoặc LINQ để xóa mã này và làm cho nó hoạt động hiệu quả hơn.

Cảm ơn trước sự giúp đỡ của bạn.

Answer 1

Tất cả các giải pháp được đăng cho đến nay đều chuyên biệt - chúng không phải là chung chung hoặc do đó, lần sau bạn có danh sách phân cấp, bạn sẽ phải mã hóa giải pháp mới. Kinh quá.

Dưới đây là một giải pháp chung chung mà sẽ làm việc cho tất cả các nhu cầu thứ bậc của bạn:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> sequence, Func<T, IEnumerable<T>> childFetcher) 
{ 
    var itemsToYield = new Queue<T>(sequence); 
    while (itemsToYield.Count > 0) 
    { 
     var item = itemsToYield.Dequeue(); 
     yield return item; 

     var children = childFetcher(item); 
     if (children != null) 
     { 
      foreach (var child in children) 
      { 
       itemsToYield.Enqueue(child); 
      } 
     } 
    } 
} 

Đây là cách bạn muốn sử dụng nó:

myList.Flatten(i => i.SubEntries).FirstOrDefault(i => i.HighScore); 

Dễ dàng như pho mát.

Phương pháp mở rộng này có thể được sử dụng để biến bất kỳ dữ liệu phân cấp nào thành danh sách phẳng, chúng có thể được tìm kiếm bằng LINQ.

Một điều tuyệt vời khác về giải pháp này là sử dụng đánh giá lười biếng, vì vậy nó chỉ hoạt động nhiều như yêu cầu của người gọi. Ví dụ, trong đoạn mã trên, Flatten sẽ ngừng tung ra các mục ngay sau khi tìm thấy một HighScore.

Giải pháp này cũng tránh đệ quy, có thể là một hoạt động tốn kém cho các phân cấp lồng nhau sâu, tránh phân bổ nhiều ngăn xếp mà các giải pháp đệ quy phải chịu.

Answer 2

Bạn có thể thu hẹp đáng kể tìm kiếm của bạn xuống với một biểu hiện một cái gì đó lambda như:

var foundHighScore = myList.FirstOrDefault(IE => IE.HighScore or (IE.SubEntries != null && IE.SubEntries.Any(IES => IES.HighScore)); 

var indexEntry = foundHighScore; 
if (!indexEntry.HighScore) 
{ 
    indexEntry = indexEntry.SubEntries.FirstOrDefault(IE => IE.HighScore); 
} 

// do something with indexEntry 

Cập nhật

Thực ra giải pháp đầu tiên sẽ không đi qua thông qua đúng cách. Tôi không nghĩ rằng có một giải pháp lambda chỉ cho điều này, bạn sẽ phải làm một số hình thức chức năng đệ quy. Trên đỉnh đầu của tôi những điều sau đây sẽ hoạt động, cách nó sẽ đối phó với hiệu suất khôn ngoan Tôi không chắc chắn:

public IndexEntry FindHighScore(List<IndexEntry> entries) 
{ 
    var highScore = GetHighScore(entries); 
    if (highScore == null) 
    { 
     // give me only entries that contain sub-entries 
     var entriesWithSub = entries.Where(e => e.SubEntries != null); 
     foreach (var e in entriesWithSub) 
     { 
      highScore = FindHighScore(e.SubEntries); 
      if (highScore != null) 
       return highScore; 
     } 
    } 
    return highScore; 
} 

private IndexEntry GetHighScore(List<IndexEntry> entries) 
{ 
    return entries.FirstOrDefault(IE => IE.HighScore); 
} 

Answer 3

Đệ quy là bạn của bạn ở đây.

public IndexEntry FindHighScore(IEnumerable<IndexEntry> entries) 
{ 
    foreach (IndexEntry entry in entries) 
    { 
    IndexEntry highScore = FindHighScore(entry); 
    if (highScore != null) 
    { 
     return highScore; 
    } 
    } 
    return null; 
} 

private IndexEntry FindHighScore(IndexEntry entry) 
{ 
    return entry.HighScore ? entry : FindHighScore(entry.SubEntries); 
}