Как найти точку между двумя ключами в отсортированном словаре - PullRequest
Новая
       16

Как найти точку между двумя ключами в отсортированном словаре

2 голосов
/ 14 марта 2011

У меня есть отсортированный словарь, который содержит измеренные точки данных в виде пар ключ / значение. Чтобы определить значение для неизмеренной точки данных, я хочу экстраполировать значение между двумя известными ключами, используя линейную интерполяцию их соответствующих значений. Я понимаю, как рассчитать неизмеримую точку данных, когда у меня есть две пары ключ / значение, между которыми она лежит. Чего я не знаю, так это как выяснить, между какими ключами он лежит. Есть ли более элегантный способ, чем цикл for (я думаю, функция / запрос LINQ), чтобы выяснить, между какими двумя ключами находится моя точка данных?

Ответы [ 5 ]

6 голосов
/ 14 марта 2011

Примерно так будет работать: 

 dic.Keys.Zip(dic.Keys.Skip(1), 
              (a, b) => new { a, b })
         .Where(x => x.a <= datapoint && x.b >= datapoint)
         .FirstOrDefault();

Это обходит их ключи, используя тот факт, что они упорядочены, и сравнивает все два ключа по порядку - так как LINQ ленив, когда вы найдете первое совпадениеОбход прекратится.

2 голосов
/ 13 октября 2012

Стандартные ответы C # все O (N) сложности. Иногда вам просто нужно небольшое подмножество в довольно большой отсортированной коллекции. (так что вы не перебираете все ключи) Стандартные коллекции C # здесь вам не помогут. И решение заключается в следующем: http://www.itu.dk/research/c5/ Используйте IntervalHeap в библиотеке коллекций C5. Этот класс поддерживает метод GetRange () и ищет ключ запуска со сложностью O (log N) и выполняет итерацию диапазона со сложностью O (N). Что, безусловно, будет полезно для больших наборов данных, если производительность критична. например Пространственное разбиение в играх

1 голос
/ 14 марта 2011

обычный цикл должен быть в порядке: 

IEnumerable<double> keys = ...; //ordered sequence of keys
double interpolatedKey = ...;

// I'm considering here that keys collection doesn't contain interpolatedKey

double? lowerFoundKey = null;
double? upperFoundKey = null;

foreach (double key in keys)
{
    if (key > interpolatedKey)
    {
        upperFoundKey = key;
        break;
    }
    else
        lowerFoundKey = key;
}

Вы можете сделать это в C # с помощью LINQ с более коротким, но менее эффективным кодом: 

double lowerFoundKey = key.LastOrDefault(k => k < interpolatedKey);
double upperFoundKey = key.FirstOrDefault(k => k > interpolatedKey);

Для того, чтобы сделать это эффективно с LINQу него должен быть метод, который называется оконным в F # с параметром 2. Он вернет IEnumerable соседних пар в коллекции keys.Хотя эта функция отсутствует в LINQ, обычный цикл foreach должен быть в порядке.

1 голос
/ 14 марта 2011

Возможно, вы спрашиваете о следующем: 

myDictionary.Keys.Where(w => w > start && w < end)
0 голосов
/ 14 марта 2011

Я не думаю, что в SortedDictionary есть функция, которая позволяет вам находить элементы вокруг того, что вам нужно, быстрее, чем итерация элементов. (+1 к решению BrokenGlass)

Чтобы быстрее находить предметы, вам нужно переключиться на другую структуру. То есть SortedList предоставляет аналогичную функциональность, но позволяет индексировать свою коллекцию ключей, и, следовательно, вы можете использовать двоичный поиск, чтобы найти диапазон.

...