2010-02-20 11 views
5

si tengo una colección de fechas y valores. Quiero conseguir el valor que está bien:buscar el elemento en la colección con la fecha más cercana

  1. asociado a la fecha en la colección
  2. si no existe, yo quiero una interpolación lineal entre dos puntos que se encuentran alrededor del punto que estoy buscando

ao, aquí hay un ejemplo simple. Si la colección es:

Date Value 
1/1/2009 100 
1/1/2010 200 
1/1/2011 300 

si busco el 6/1/2010 me gustaría tener un valor de vuelta 250. puedo usar cualquier colección si uno es mejor en la resolución que el otro (diccionario, matriz, etc. ..)

Respuesta

2

Una simple lista ordenada (en fecha) sería suficiente. Simplemente encuentre la última fecha (llamémosla d1) que sea menor o igual a la fecha que está buscando (llamemos a esa d). La siguiente fecha d2 pasará a d, asumiendo que no hay fechas duplicadas.

Ahora bien, si el valor v1 corresponde a d1 y v2 corresponde a d2 entonces el valor que busca es v1 + (v2 - v1)/(d2 - d1) * (d - d1).

+0

quería ver si había alguna forma más rápida de hacerlo, además de una búsqueda lineal – leora

+0

Hay, como alguien aquí menciona: si su lista está ordenada, puede hacer una búsqueda binaria. –

0

Puedes probar SortedDictionary. Haga algo así:

int FindInterpolated(DateTime needle) 
{ 
    try 
    { 
     DateTime lower = haystack.First(key => haystack[key] <= needle); 
     DateTime upper = haystack.Last(key => haystack[key] >= needle); 
     int v1 = haystack[lower]; 
     int v2 = haystack[upper]; 
     long ticksLower = lower.Ticks; 
     long ticksUpper = upper.Ticks; 
     return (v1 * ticksLower + v2 * ticksUpper)/(ticksLower + ticksUpper); 
    } 
    catch (InvalidOperationException) 
    { 
     // thrown if needle is out of range 
     // (not between smallest and biggest keys in the haystack) 
     ... 
    } 
} 
+0

@Vlad - ¿Qué es el contenedor y la aguja aquí? – leora

+0

'needle' es un' DateTime' que está buscando – Vlad

+0

'container' era incorrecto, de hecho tiene que ser' haystack' – Vlad

7

Puede usar el tipo de lista para contener los pares, ordenarlos y usar List.BinarySearch.

Por ejemplo, podría tener algo como lo siguiente:

struct Pair 
{ 
    public Pair(DateTime t, int v) 
    { 
     date = t; 
     value = v; 
    } 
    public DateTime date; 
    public int value; 
} 

    .... 

    List<Pair> pairs = new List<Pair>(); 


    pairs.Add(new Pair(DateTime.Now, 100)); 
    pairs.Add(new Pair(DateTime.Now, 200)); 

    .... 

    // Sort using the time. 
    pairs.Sort(delegate(Pair pair1, Pair pair2) { 
          return pair1.date.CompareTo(pair2.date); 
         } 
      ); 

    // Do binary search. 
    int index = pairs.BinarySearch(new Pair(dateToSearch, 0), 
            delegate(Pair pair1, Pair pair2) { 
             return pair1.date.CompareTo(pair2.date); 
            }); 

    if (index >= 0) { 
     // Found the element! 
     return pairs[index].value; 
    } 

    // If not found, List.BinarySearch returns the complement 
    // of the index where the element should have been. 
    index = ~index; 

    // This date search for is larger than any 
    if (index == pairs.Count) { 
     // 
    } 

    // The date searched is smaller than any in the list. 
    if (index == 0) { 
    } 

    // Otherwise return average of elements at index and index-1. 
    return (pairs[index-1].value + pairs[index].value)/2; 

Por supuesto, el código no es la mejor posible, pero usted consigue la idea: utilizar la lista, clasificar y luego hacer BinarySearch.

Buscar MSDN para obtener más información.

Lista: http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx

list.sort: http://msdn.microsoft.com/en-us/library/3da4abas.aspx

List.BinarySearch: http://msdn.microsoft.com/en-us/library/3f90y839.aspx

+0

Esa es una visión esclarecedora de BinarySearch. Gracias. – Echilon

2

Dada una "lista de fechas" y una "fecha de referencia", recibe el "n números más cercanos" . Código de C# probado.

public class ClosestDate 
{ 
    public void GetClosestDate(DateTime referenceDate, 
           List<DateTime> listDates, int maxResults) 
    { 
     // final ordered date list 
     List<DateTime> finalList = new List<DateTime>(); 

     DateTime selectedDate = DateTime.MaxValue; 

     // loop number of results 
     for (int i = 0; i < maxResults; i++) 
     { 
      // get next closest date 
      int tempDistance = int.MaxValue; 
      foreach (DateTime currentDate in listDates) 
      { 
       int currenDistance = this.DateDiff(currentDate, referenceDate); 

       if (currenDistance < tempDistance) 
       { 
        tempDistance = currenDistance; 
        selectedDate = currentDate; 
       } 
      } 

      // build final list 
      finalList.Add(selectedDate); 
      // remove element from source list 
      listDates.Remove(selectedDate); 
     } 

     // print results 
     foreach (DateTime date in finalList) 
     { 
      Console.WriteLine(date.ToShortDateString()); 
     } 

    } 

    private int DateDiff(DateTime Date1, DateTime Date2) 
    { 
     TimeSpan time = Date1 - Date2; 
     return Math.Abs(time.Days); 
    } 
} 
+0

Editado justo ahora. Algoritmo probado. –

+0

Funciona, pero el rendimiento es O (N) –

+0

@TheodoreZographos ¿Era eso una especificación/requisito? Si funciona; funciona –

Cuestiones relacionadas