Какова лучшая структура данных в.NET для поиска строковым ключом или числовым индексом?
Это можно сделать с помощью коррелированного подзапроса, например:
SELECT u.*
FROM usertrack u
WHERE NOT EXISTS (
SELECT 1 FROM usertrack u1 WHERE u1.ts > u.ts AND u1.uid = u.uid
) AND ts >= NOW() - INTERVAL 43830 MINUTE
7 ответов
Вы хотите класс OrderedDictionary. Необходимо будет включать Систему. Наборы. Специализированное пространство имен:
OrderedDictionary od = new OrderedDictionary();
od.Add("abc", 1);
od.Add("def", 2);
od.Add("ghi", 3);
od.Add("jkl", 4);
// Can access via index or key value:
Console.WriteLine(od[1]);
Console.WriteLine(od["def"]);
Существует Система. Наборы. ObjectModel. KeyedCollection <строка, TItem>, который происходит из Набора <TItem>. Извлечение является O (1).
class IndexableDictionary<TItem> : KeyedCollection<string, TItem>
{ Dictionary<TItem, string> keys = new Dictionary<TItem, string>();
protected override string GetKeyForItem(TItem item) { return keys[item];}
public void Add(string key, TItem item)
{ keys[item] = key;
this.Add(item);
}
}
Одно слово предупреждения. OrderedDictionary имеет действительно плохие рабочие характеристики для большинства операций кроме вставки и поиска: И удаление и модификация значения могут потребовать линейного поиска целого списка, приводящего ко времени выполнения O (n). (Для модификации это зависит от того, произошел ли доступ индексом или ключом.)
Для большинства операций с разумными объемами данных это абсолютно неприемлемо. Кроме того, структура данных хранит элементы и в линейном векторе и в хеш-таблице, приводящей к некоторой памяти наверху.
Если извлечения индексом не происходит слишком часто, a SortedList или SortedDictionary будет иметь намного лучшие рабочие характеристики (доступ индексом может быть достигнут через ElementAt дополнительный метод).
Если с другой стороны, доступ индексом является нормой, то прекратите использовать структуры данных словаря в целом и просто сохраните свои значения в a List<KeyValuePair<TKey, TValue>>. Хотя это означает линейный поиск доступа по ключу, все другие операции являются очень дешевыми, и общую производительность трудно разбить на практике.
/ РЕДАКТИРОВАНИЕ: Конечно, последний является также структурой данных словаря в теоретическом смысле. Вы могли даже инкапсулировать его в классе, реализовывая соответствующий интерфейс.
Вы ищете что-то как класс SortedList (вот универсальная версия также).
Словарь мог работать с linq. Хотя я не знаю о возможных проблемах производительности. Словарь. ElementAt (индекс);
Основанные на хеше наборы (Словарь, Хеш-таблица, HashSet) отсутствуют, потому что у Вас не будет индекса, так как Вы хотите индекс, я использовал бы вложенный дженерик:
List<KeyValuePair<K,V>>
Конечно, Вы теряете O (1) Ключевой поиск, который Вы получаете с хешами.
Я рекомендую использовать SortedDictionary <строка, TValue> или SortedList <строка, TValue>. У обоих есть O (зарегистрируйте n), поисковая производительность.
Различия, как заключено в кавычки из библиотеки MSDN:
SortedList <(<(TKey, TValue>)>) использует меньше памяти, чем SortedDictionary <(<(TKey, TValue>)>).
SortedDictionary <(<(TKey, TValue>)>) имеет более быструю вставку и операции удаления для неотсортированных данных: O (регистрируют n) в противоположность O (n) для SortedList <(<(TKey, TValue>)>).
Если список заполняется внезапно от отсортированных данных, SortedList <(<(TKey, TValue>)>) быстрее, чем SortedDictionary <(<(TKey, TValue>)>).
По моему опыту, SortedDictionary больше достаточен для большинства типичных бизнес-сценариев, так как данные обычно первоначально не сортируются при использовании структур как это, и память наверху SortedDictionary редко очень важна. Но если производительность является ключевой для Вас, я предлагаю, чтобы Вы реализовали обоих и сделали измерения.