Получить ближайшее доступное значение из словаря

У меня есть словарь
сказать

Dictionary<DateTime, double> MyData  

Теперь я хочу получить значение из словаря. Но в случае, если ключа не существует, мне нужно взять ближайшее значение.

Позволяет вызвать функцию

double GetMyData(Dictionary<DateTime, double> MyData, DateTime Date)  
    {  
      if(MyData.ContainsKey(Date)  
      {
          return MyData[Date];
      }  
      else  
      {  
          //return the nearest available value.  
          // if Date is '2018-01-01', then try to look for next date,  
          // It can be '2018-01-02' or even '2017-12-31'  
          // Here aim is to get the nearest available value.
      }  
    } 

РЕДАКТИРОВАТЬ :
Образец данных :

MyData['2018-01-01'] = 420.0;  
MyData['2018-02-01'] = 220.0;  
MyData['2018-03-01'] = 320.0;  
MyData['2018-05-01'] = 210.0;  
MyData['2018-06-01'] = 220.0;   
MyData['2018-07-01'] = 230.0;  
MyData['2018-08-01'] = 240.0;

Здесь ключ '2018-04-01' недоступен,
Поэтому мне нужно любой ближайшего доступного значения. Это может быть значение 2018-03-01 или 2018-05-01
. Теперь надеюсь прояснилось.
И, пожалуйста, не обижайтесь, английский не мой родной язык.

Словарь - это не та структура данных, которая вам для этого нужна. Вам понадобится упорядоченная и последовательная структура данных. Что-то вроде списка. Или вы можете использовать комбинацию Dictionary + sortedList

thebenman 26.10.2018 06:59

Если я сделаю это списком, то как я смогу получить от этого ценность? Проблема состоит в том, чтобы найти ближайшую доступную дату (ключ), а затем значение этого ключа. В любом случае ключ - это дата, которая уже отсортирована. Мне просто нужно получить значение ближайшего доступного ключа.

Karthik 26.10.2018 07:05

Можете ли вы объяснить вашу актуальную задачу / проблему? Также ближайший в каком направлении?

SᴇM 26.10.2018 07:05

Я бы, наверное, использовал октодерево. В любом случае ваш вопрос, вероятно, слишком широкий

Micky 26.10.2018 07:06

Словари используются для поиска значения, связанного с ключом. Они не структурированы таким образом, чтобы можно было проводить «тщательный» поиск. Прочтите «хеш-таблицы», чтобы понять, почему. Вам нужен какой-то отсортированный список KeyValuePairs, отсортированный по ключу, а затем алгоритм поиска. Вы можете найти в Интернете кого-нибудь с кодом, который это делает.

Flydog57 26.10.2018 07:11
1
5
251
5
Перейти к ответу Данный вопрос помечен как решенный

Ответы 5

Вам понадобится словарь заказал, и не только это, вам понадобится собственный компаратор для найти ближайшую дату к ключу

См. Минимальный пример кода ниже

void Main()
{
    OrderedDictionaryByDateTime<double> data = new OrderedDictionaryByDateTime<double>();
    data.Add(DateTime.Now, 1.1);
    data.Add(DateTime.Now.AddDays(-1), 1.2);
    data.Add(DateTime.Now.AddDays(2), 1.3);
    data.Add(DateTime.Now.AddDays(3), 1.4);
    data.Add(DateTime.Now.AddDays(-5), 1.5);

    var tomorrow = DateTime.Now.AddDays(1);
    var oneHourBefore = DateTime.Now.AddHours(-1);
    var theDayAfterTomorrow = DateTime.Now.AddDays(2);
    var yesterday = DateTime.Now.AddDays(-1);
    var fourDaysInThePast = DateTime.Now.AddDays(-4);

    data.GetValueClosestToTheDateTimeKey(tomorrow); // should be 1.1
    data.GetValueClosestToTheDateTimeKey(oneHourBefore); // should be 1.1
    data.GetValueClosestToTheDateTimeKey(yesterday); // should be 1.2
    data.GetValueClosestToTheDateTimeKey(theDayAfterTomorrow); // should be 1.3
    data.GetValueClosestToTheDateTimeKey(fourDaysInThePast); // should be 1.5
}

public class OrderedDictionaryByDateTime<TValue> : List<KeyValuePair<DateTime, TValue>>
{
    private readonly Dictionary<DateTime, int> _dictionary = new Dictionary<DateTime, int>();

    public void Add(DateTime key, TValue value)
    {
        Add(new KeyValuePair<DateTime, TValue>(key, value));
        _dictionary.Add(key, Count - 1);
    }

    public TValue Get(DateTime key)
    {
        var idx = _dictionary[key];
        return this[idx].Value;
    }

    public TValue GetValueClosestToTheDateTimeKey(DateTime key)
    {
        var closestDate = _dictionary.Keys.OrderBy(t => Math.Abs((t - key).Ticks)).First();

        return Get(closestDate);
    }
}

Если вам нужно ближайшее значение, вам нужно пройти через словарь и взять наименьший временной интервал, запомнить наименьший и вернуть это DateTime.

TimeSpan timeSpan=DateTime.MinValue-DateTime.MaxValue;
double returnDate;
foreach(var key in MyData.Keys)
{
  if(key<Date)
  {
    var dif = Date-key;
    if(dif<timeSpan)
    {
     timeSpan=dif;
     returnDate=MyData[key];
    }
  }
  else
  {
    var dif = key-Date;
    if(dif<timeSpan)
    {
     timeSpan=dif;
     returnDate=MyData[key];
    }
  }
 }
  return returnDate;

Это не имеет никакого отношения к промежутку времени. Мои данные уже отсортированы. Я просто хочу получить доступное значение ключа из словаря. если ключ недоступен, попробуйте взять следующий. А следующая может быть любой датой. Это не просто временной промежуток. Если ключ «2018-02-01» недоступен, я должен взять следующий, ближайший.

Karthik 26.10.2018 07:27

Я понимаю, но я думаю, это помогает !? Потому что это вернет ближайшую дату к вашему параметру Date! Он будет перебирать все ключи и искать ближайший, кстати, я не тестировал это.

J.Memisevic 26.10.2018 07:36

Вы можете использовать код ниже,

Код отсортируйте словарь по ключу (DateTime) и найдите значения даты GreaterOrEqual. Если есть допустимая запись, возвращает первое значение, иначе возвращает -1

    public double? getData(Dictionary<DateTime,double> source, DateTime date) 
    {
        if (source.Where(x => x.Key >= date).OrderBy(x => x.Key).Count() > 0)
            return source.Where(x => x.Key >= date).OrderBy(x => x.Key).FirstOrDefault().Value;
        else
            return -1;
    }

Если вы хотите получить ближайшее значение (вверх или вниз), вы можете использовать код ниже,

    public double? getData(Dictionary<DateTime,double> source, DateTime date) 
    {
        DateTime up = source.Where(x => x.Key >= date).OrderBy(x => x.Key).Count() > 0 ? source.Where(x => x.Key >= date).OrderBy(x => x.Key).FirstOrDefault().Key : DateTime.MinValue;
        DateTime down = source.Where(x => x.Key <= date).OrderByDescending(x => x.Key).Count() > 0 ? source.Where(x => x.Key <= date).OrderByDescending(x => x.Key).FirstOrDefault().Key : DateTime.MinValue;

        long up_difference = -1;
        long down_difference = -1;

        if (up != DateTime.MinValue)
            up_difference = up.Ticks - date.Ticks;

        if (down != DateTime.MinValue)
            down_difference = date.Ticks - down.Ticks;

        // There are no values upper or higher
        if (up_difference == -1 && down_difference == -1)
            return null;
        else if (up_difference != -1 && down_difference != -1)
        {
            if(up_difference < down_difference)
                return source.Where(x => x.Key == up).FirstOrDefault().Value;
            else
                return source.Where(x => x.Key == down).FirstOrDefault().Value;
        }
        else if(up_difference != -1)
        {
            return source.Where(x => x.Key == up).FirstOrDefault().Value;
        }
        else
        {
            return source.Where(x => x.Key == down).FirstOrDefault().Value;
        }

    }

Это ужасно неэффективно

Micky 26.10.2018 08:34

Вы можете просто поместить словарь в отсортированный словарь и выполнить двоичный поиск. Если ключ не существует, то элемент слева - ближайший. Это не подходит для граничных сценариев, где ~ index - 1 становится -1 и т. д.

public static double GetMyData(Dictionary<DateTime, double> MyData, DateTime Date)
{
        var sorted = new SortedDictionary<DateTime, double>(MyData);

        var keys = new List<DateTime>(sorted.Keys);
        var index = keys.BinarySearch(Date);

        if (index >= 0) return sorted[keys[index]];

        else
            return sorted[keys[~index - 1]];
    }

В этом поиске Дата никогда не присутствует. Так что это бесполезно при поиске, но нам нужна ближайшая либо больше, либо меньше заданной даты.

Karthik 26.10.2018 07:46

Кажется, это правильный путь. В чем проблема с этим решением @Karthik? Если возможно, вам следует изменить словарь ввода на SortedDictionary, чтобы вам не приходилось создавать его все время здесь.

Magnus 26.10.2018 07:58

Вы можете указать количество дней с предыдущего и последующего, а затем вернуть значение с меньшего из дней ... сравнить abs (Date - keys [~ index - 1]) и abs (Date-keys [~ index + 1] и т. д.

Gauravsa 26.10.2018 08:08
Ответ принят как подходящий

Думаю, я нашел решение для этого.

Шаг 1: отсортируйте (по убыванию) ключи меньше заданной даты и возьмите FirstOrDefault => PreviousKey
Шаг 2: отсортируйте (по убыванию) ключи больше заданной даты и возьмите FirstOrDefault => NextKey

Шаг 3: Теперь проверьте разницу между ними. Шаг 4: Если (Date-PreviousKey)> (NextKey-Date), тогда возьмите NextKey, иначе PreviousKey => FoundKey
Шаг 5. Теперь верните MyData [FoundKey]

Другие вопросы по теме