Estructura de datos "Historial de edad"

Question

He estado buscando una estructura de datos que funcione como una lista de registro de edad. Usted tiene un registro de edad si nadie más joven tiene una calificación más alta.

Así que quiero una lista de pares (a, b), donde para todos los pares de pares (a1, b1) y (a2, b2) siguiente implicación tiene a1> a2 => b1> b2.

Debe haber un inserto de método de inserción (a_new, b_new) que inserta (a_new, b_new) si no existe un par (a_k, b_k) tal que a_k < a_new pero b_k> b_new. Si se cumple este criterio, se insertará el nuevo par y se eliminarán todos los pares de la lista, de modo que se elimine a_k> a_new pero b_k < b_new.

La estructura de datos no necesita ser compatible con la eliminación.

Answer 1

Aquí hay una solución genérica que creo que hará el trabajo por usted. No está optimizado para el rendimiento, ni está particularmente bien probado.

public class AgePair<T, Y> 
    where T : IComparable<T> 
    where Y : IComparable<Y> 
{ 
    public T A { get; set; } 

    public Y B { get; set; } 
} 

public class AgeRecordList<T, Y> : IEnumerable<AgePair<T,Y>> 
    where T : IComparable<T> 
    where Y : IComparable<Y> 
{ 
    private List<AgePair<T, Y>> m_List = new List<AgePair<T, Y>>(); 

    public void Add(T a, Y b) 
    { 
     AgePair<T, Y> newPair = new AgePair<T, Y> { A = a, B = b }; 

     // Get all elements that are younger 
     var younger = GetYounger(newPair.A); 

     // Find any of the younger with a higher score 
     // If found, return without inserting the element 
     foreach (var v in younger) 
     { 
      if (v.B.CompareTo(newPair.B) >= 0) 
      { 
       return; 
      } 
     } 

     // Cache elements to delete 
     List<AgePair<T, Y>> toDelete = new List<AgePair<T, Y>>(); 

     // Find all the elder elements  
     var elder = GetElder(newPair.A); 

     // Find all elder elements with a lower B 
     foreach (var v in elder) 
     { 
      if (v.B.CompareTo(newPair.B) <= 0) 
      { 
       // Mark for delete 
       toDelete.Add(v); 
      } 
     } 

     // Delete those elements found above 
     foreach (var v in toDelete) 
     { 
      m_List.Remove(v); 
     } 

     // Add the new element 
     m_List.Add(newPair); 

     // Sort the list (ascending by A) 
     m_List.Sort(CompareA); 
    } 

    private List<AgePair<T, Y>> GetElder(T t) 
    { 
     List<AgePair<T, Y>> result = new List<AgePair<T, Y>>(); 

     foreach (var current in m_List) 
     { 
      if (t.CompareTo(current.A) <= 0) 
      { 
       result.Add(current); 
      } 
     } 

     return result; 
    } 

    private List<AgePair<T, Y>> GetYounger(T t) 
    { 
     List<AgePair<T, Y>> result = new List<AgePair<T, Y>>(); 

     foreach (var current in m_List) 
     { 
      if (t.CompareTo(current.A) > 0) 
      { 
       result.Add(current); 
      } 
     } 

     return result; 
    } 

    private static int CompareA(AgePair<T,Y> item1, AgePair<T,Y> item2) 
    { 
     return item1.A.CompareTo(item2.A); 
    } 


    public IEnumerator<AgePair<T, Y>> GetEnumerator() 
    { 
     return m_List.GetEnumerator(); 
    } 

} 

Edición 1: visión general de nivel alto del algoritmo

1. Buscar Todos los elementos más jóvenes o iguales,
2. Para todos los elementos más jóvenes o iguales, ver si alguno tienen un mayor B
3. Si (2) return
4. Buscar todos los elementos antiguos
5. Si algún elemento anterior tiene una puntuación más baja, elimine
6. ordenar la lista en orden ascendente (de A)

Edición 2: La velocidad se puede incrementar fácilmente por a) una vez que encontramos los elementos más jóvenes, puede continuar desde ese punto en la búsqueda de elementos mayores en lugar de iterando sobre todo otra vez, yb) en lugar de ordenarlo usando el método Sort de List, puede usar InsertAt (0 o índice de primer élder)

Answer 2

Este AgeList realiza un seguimiento del mejor registro para cada edad, luego ignora el edades que no tienen agerecords cuando se les pregunta por los ganadores.

Si bien no todos los perdedores se eliminan en la inserción (no estoy seguro si ese es un requisito fuerte), debería ahorrar tiempo en general por ser flojo. El punto débil más grande es la llamada a OrderBy. Si ese tipo es demasiado caro mientras hay espacio disponible, uno podría saltar para una SortedList para mantener todas las A insertadas.

Si el espacio es escaso mientras el tiempo está disponible, es fácil escribir un método de limpieza similar al método GetWinners. Incluso se podría llamar desde InsertMethod para limpiar después de cada inserción.

public class AgeList<T, U> where T:IComparable<T> where U:IComparable<U> 
{ 
    Dictionary<T, U> store = new Dictionary<T, U>(); 

    public void Insert(T a, U b) 
    { 
     if (!store.ContainsKey(a) || store[a].CompareTo(b) < 0) 
     { 
      store[a] = b; 
     } 
     //else discard by doing nothing 
    } 

    public IEnumerable<KeyValuePair<T, U>> GetWinners() 
    { 
     bool first = true; 
     U record = default(U); 
     foreach(T key in store.Keys.OrderBy(t => t)) 
     { 
      U newValue = store[key]; 
      if (first) 
      { 
       first = false; 
       record = newValue; 
       yield return new KeyValuePair<T, U>(key, record); 
      } 
      else if (record.CompareTo(newValue) < 0) 
      { 
       record = newValue; 
       yield return new KeyValuePair<T, U>(key, record); 
      } 
     } 
    } 
}