znajdź przedmiot w kolekcji z najbliższą datą

Question

, jeśli mam kolekcję dat i wartości. Chcę uzyskać wartość, która jest albo:

1. Associated do tej pory w kolekcji
2. jeśli ona nie istnieje, chcę interpolacji liniowej pomiędzy dwoma punktami, które są wokół punktu szukam

ao, oto prosty przykład. Jeśli zbiór jest:

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

jeśli szukam 6/1/2010 chciałbym uzyskać wartość z powrotem 250. mogę użyć dowolnego kolekcję jeśli jeden jest lepszy w rozwiązywaniu niż inne (słownik, tablica, etc ..)

Answer 1

Wystarczy posortowana lista (na datę). Po prostu znajdź ostatnią datę (nazwijmy ją: d1), która jest mniejsza lub równa niż data, której szukasz (nazwijmy to: d). Następna data będzie późniejsza: d, przy założeniu, że nie ma duplikatów.

Teraz, jeśli wartość v1 odpowiada d1 i v2 odpowiada d2 wówczas wartość szukasz jest v1 + (v2 - v1)/(d2 - d1) * (d - d1).

Answer 2

Możesz spróbować SortedDictionary. Zrób coś takiego:

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

Answer 3

Możesz użyć typu Lista do przechowywania par, Sortowania i korzystania z List.BinarySearch.

Na przykład można mieć coś jak następuje:

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; 

Oczywiście kod nie jest najlepsza, ale masz pomysł: użyj listy, sortować i następnie zrobić BinarySearch.

Wyszukaj MSDN, aby uzyskać więcej informacji.

listy: 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

Answer 4

Biorąc pod uwagę "lista terminów" i "dzień referencyjny", dostaje "najbliżsi numery n" . Sprawdzono kod C#.

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