Я хочу иметь структуру данных с (начало, конец) в качестве ключа, а затем иметь возможность искать целое число во всей структуре данных и получить соответствующее значение

Question

Я хотел бы получить

data structure with <Key, Value> where
  Key = (start, end), 
  Value = string

После чего я смогу оптимально найти целое число в структуре данных и получить соответствующее значение.

Пример:

var lookup = new Something<(int, int), string>()
{
  {(1,100),"In 100s"},
  {(101,200),"In 100-200"},
}

var value1 = lookup[10]; //value1 = "In 100s"
var value2 = lookup[110]; //value2 = "In 100-200"

Кто-нибудь может предложить?

Answer 1

Если вы хотите иметь возможность использовать что-то вроде lookup[10], как вы упомянули, вы можете создать свой собственный класс, который реализует какой-то тип данных ключ / значение.Какой тип данных вы в конечном итоге решите использовать, зависит от того, как ваши данные выглядят.

Вот простой пример того, как реализовать Dictionary<>:

public class RangeLookup : Dictionary<(int Min, int Max), string>
{
    public string this[int index] => this.Single(x => x.Key.Min <= index && index <= x.Key.Max).Value;
}

. Это позволяет вамопределить пользовательский индексатор поверх словаря, чтобы инкапсулировать ваш поиск диапазона.Использование этого класса будет выглядеть следующим образом:

var lookup = new RangeLookup
{
    { (1, 100), "In 100s" },
    { (101, 200), "In 101-200s" },
};

Console.WriteLine($"50: {lookup[50]}");

, который производит вывод как:

---

В терминахНиже приведен пример некоторых тестов (использующих Win10 с процессором Intel i7-4770) для получения производительности из словаря с 10 000 000 записей:

var lookup = new RangeLookup();

for (var i = 1; i <= 10000000; i++)
{
    var max = i * 100;
    var min = max - 99;
    lookup.Add((min, max), $"In {min}-{max}s");
}

var stopwatch = new Stopwatch();

stopwatch.Start();
Console.WriteLine($"50: {lookup[50]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

stopwatch.Restart();
Console.WriteLine($"5,000: {lookup[5000]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

stopwatch.Restart();
Console.WriteLine($"1,000,000,000: {lookup[1000000000]} (TimeToLookup: {stopwatch.ElapsedMilliseconds})");

, который дает следующие результаты:

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

Answer 2

Здесь у вас есть структура Dictionary<>, например:

var lookup = new Dictionary<(int, int), string>()
{
  {(1,100),"In 100s"},
  {(101,200),"In 100-200"},
};

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

var searchValue = 10;
var value1 = lookup.First(l => l.Key.Item1 <= searchValue && l.Key.Item2 >= searchValue);

searchValue = 110;
var value2 = lookup.First(l => l.Key.Item1 <= searchValue && l.Key.Item2 >= searchValue);

НоКак предположил Ли в комментариях, вы можете получить лучшую производительность, используя SortedDictionary, ваш пробег может отличаться, что означает, что вам нужно проверить производительность обоих.