Словарь С#: более быстрый доступ, но меньший объем памяти

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

Eg. для каждого автомобиля я хочу сохранить модель и имя.

У меня есть некоторые мысли ниже:

Вариант 1:

Dictionary<string, Dictionary<string, string>> values = new Dictionary<string, Dictionary<string, string>>();
Dictionary<string, string> list = new Dictionary<string, string>();
list.Add("2001", "Jetta S");
list.Add("2002", "Jetta SE");
list.Add("2002", "Jetta LE");
values.Add("VolksWagen", list);

Вариант 2:

Dictionary<string, List<KeyValuePair<string, string>>> values2 = new Dictionary<string, List<KeyValuePair<string, string>>>();
<pre lang="xml">List<KeyValuePair<string, string>> list2 = new List<KeyValuePair<string, string>>();
list2.Add(new KeyValuePair<string, string>("2001", "Jetta S"));
list2.Add(new KeyValuePair<string, string>("2002", "Jetta SE"));
list2.Add(new KeyValuePair<string, string>("2002", "Jetta LE"));
values2.Add("VolksWagen", list2);

Вариант 3:

Dictionary<string, List<string>> values1 = new Dictionary<string, List<string>>();
List<string> list1 = new List<string>();
list1.Add("2001:Jetta S");
list1.Add("2002:Jetta SE");
list1.Add("2002:Jetta LE");
values1.Add("VolksWagen", list1);

Вариант 1: более быстрый доступ к марке и имя, но большая часть памяти
Вариант 2: быстрый доступ к марке и имя, но больший объем памяти
Вариант 3: медленный доступ к марке и имя (нужно было бы разобрать его), но меньше занимаемой памяти

было бы более 1500 словарей, как указано выше.

Приветствуются любые предложения для быстрого доступа, но меньше памяти.

Спасибо.

Ответы

Ответ 1

SortedList<TKey,TValue> - это плоский список (поэтому нет огромного увеличения объема памяти), который использует двоичный поиск для доступа - поэтому O(log(n)) - не так быстро, как Dictionary<TKey,TValue> в O(1) - но намного лучше, чем a List<T> (или другой линейный поиск) в O(n).

Если вам нужен быстрый доступ, вам нужно использовать дополнительную память для хеш-таблицы.

В качестве побочного примечания SortedList<TKey,TValue> также обеспечивает эффективный доступ по индексу int, который является трудным для SortedDictionary<TKey,TValue> и практически бессмыслен для Dictionary<TKey,TValue>.

Очевидно, что в вашем сценарии вам может понадобиться объединить SortedList<,> с вложенным или составным ключом, но IMO, который станет вашим лучшим путем для получения баланса памяти и производительности доступа. Вы можете использовать выделенный составной ключ, т.е. iummutable struct с составными ключевыми элементами, переопределяя GetHashCode() и Equals, реализуя IEquatable<T>, и для сортировки: внедрение IComparable и IComparable<T>.

Ответ 2

Вы не должны выбирать свою структуру данных в основном по памяти "footprint", а по шаблону доступа: какие наиболее часто встречающиеся запросы вы хотите делать, как часто структура будет обновляться и т.д.

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

Btw, учитывая тот факт, что несколько моделей могут быть выпущены за один год, вы, вероятно, должны использовать Dictionary<string, Dictionary<string, List<string>>>. И если это действительно годы, которые вы хотите сохранить, вы не должны использовать строки как ключи, а Int16.

Ответ 3

Вы можете использовать Dictionary с NameValueCollection:

var values = new Dictionary<string, NameValueCollection>();
NameValueCollection list = new NameValueCollection();
list.Add("2001", "Jetta S");
list.Add("2002", "Jetta SE");
list.Add("2002", "Jetta LE");
values.Add("VolksWagen", list);

Или с помощью инициализатора коллекции:

var values = new Dictionary<string, NameValueCollection> 
    { 
        { "VolksWagen", new NameValueCollection 
            { 
                { "2001", "Jetta S" }, 
                { "2002", "Jetta SE" }, 
                { "2002", "Jetta LE" } 
            } 
        } 
    };

Хотя я не эксперт в области памяти, IMHO это обеспечит вам лучший шаблон доступа в этом конкретном сценарии.

Ответ 4

Говоря о доступе в структурах данных, важно понять разницу между доступом читать и писать. Что касается словаря, вы получите O(1) доступ к value на key время, но O(log(n)) время записи, если я не ошибаюсь. При использовании простых списков всегда O(1) добавить, но O(n) - доступ к данным. Что касается памяти, то она почти такая же: O(n) в худшем случае.

Сколько значений требуется для хранения/доступа? Согласно вашим образцам кода,

Вариант 1: не подходит:

list.Add("2002", "Jetta SE");
list.Add("2002", "Jetta LE");

Ключи должны быть уникальными, поэтому

Вариант 2: Dictionary<string, List<KeyValuePair<string, string>>> это то, что вам нужно.