buscando en la lista jerárquica

Question

Tengo una clase simple definida como:

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

ahora tengo que buscar a través de una lista para encontrar el elemento que tiene su propiedad establecida en HighScore cierto. Dado que no es una lista plana, sino una jerarquía que puede tener un número desconocido de niveles profundos y dado que el elemento que estoy buscando podría estar contenido en cualquiera de las listas de SubEnties, no puedo hacer un Lambda simple como esto:

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

Aquí está el código que tengo. Sé que es feo (al menos me parece así). Funciona, pero es lento como el pecado en una lista remotamente grande y estoy seguro de que debe haber una manera mejor.

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; 
} 

Tengo creen que hay una mejor manera de utilizar un poco más complejo lambda o con LINQ para limpiar el código y hacerlo más performante.

Gracias de antemano por su ayuda.

Answer 1

Todos con las soluciones publicadas hasta ahora están especializados - que no son de carácter genérico o general, y por lo tanto, la próxima vez que tenga una lista jerárquica, tendrá que codificar una nueva solución. Yuck.

Aquí es una solución general y genérico que funcione para todas sus necesidades jerárquicas:

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); 
      } 
     } 
    } 
} 

Así es como debería usar este recurso:

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

Fácil como el queso.

Este método de extensión se puede utilizar para convertir cualquier información jerárquica en una lista plana, que se puede buscar utilizando LINQ.

Otra gran ventaja de esta solución es que utiliza la evaluación diferida, por lo tanto, solo hace todo el trabajo que exige la persona que llama. Por ejemplo, en el código anterior, Flatten dejará de producir artículos tan pronto como se encuentre un HighScore.

Esta solución también evita la recursión, que puede ser una operación costosa para jerarquías anidadas profundamente, evitando las muchas asignaciones de pila en las que incurren las soluciones recursivas.

Answer 2

Se podría reducir significativamente su búsqueda hacia abajo con una expresión lambda algo como:

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 

actualización

En realidad, la primera solución no va a recorrer a través correctamente. No creo que haya una solución solo lambda para esto, tendrás que hacer alguna forma de función recursiva. De la parte superior de mi cabeza la siguiente iba a funcionar, cómo se haría frente a rendimiento no estoy seguro:

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

La recursividad es su amigo.

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); 
}