C# отсортированный список по значению с объектом
Я пытаюсь создать "упорядоченный" кэш объектов в C#, где порядок определяется тем, сколько раз к нему обращались.
Я посмотрел на словарь, SortedList и SortedDictionary, которые были очень близки, но не совсем то, что я ищу.
Я хотел бы иметь список, который содержит все ранее кэшированные элементы, эти элементы могут иметь getHits() метод определения порядка кэширования элементов.
Затем я могу получить доступ к этому кешу по имени и увеличить количество просмотров элемента.
Упрощенный пример (в псевдо C#):
class Result {
public int Hits = 0;
public string Name = "";
public void IncreaseHits() {
this.hits++;
}
public Result(String name) {
this.name = name;
}
}
class Program {
public MagicSortableType<string, Result> MyCache; //what structure to use?
public main() {
MyCache.Add(new Result("My result 1"));
MyCache.Add(new Result("My result 2"));
MyCache.Add(new Result("My result 3"));
MyCache['My result 2'].IncreaseHits();
MyCache['My result 2'].IncreaseHits();
MyCache['My result 3'].IncreaseHits();
MyCache.SortDesc(); //what is the real C# equivalent?
foreach(Result result in MyCache) {
Console.Write(result.Name + " - hits " + result.Hits);
}
}
}
Выходы:
My result 2 - hits 2
My result 3 - hits 1
My result 1 - hits 0
9 ответов
Когда мне нужно что-то вроде этого, я создал то, что я назвал MruDictionary, Он состоял из LinkedList<T>и Dictionary<string, LinkedListNode<T>> (где T это тип объекта, а ключ объекта был тип string).
Доступ осуществляется через словарь. Когда к элементу обращаются, он перемещается в начало списка. Когда элемент добавлен, он добавляется в начало списка. Если размер списка выходит за пределы установленного максимума, последний узел в списке удаляется.
Это сработало очень хорошо. Пункты не содержались в порядке по количеству использованных раз, а скорее в строгом порядке MRU. Это обычно сохраняло наиболее часто используемые элементы в кеше, но если был длительный период, в течение которого популярный элемент не использовался, он очищался. Для моих целей это работало очень хорошо.
Я написал статью об этом. Полный источник с описанием доступен на http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626.
Это должно быть достаточно просто, чтобы добавить счетчик посещений, если вам это действительно нужно.
Опираясь на ваш псевдокод, похоже, это работает:
var MyCache = new Dictionary<string, Result>
{
{"My result 1", new Result("My result 1")},
{"My result 2", new Result("My result 2")},
{"My result 3", new Result("My result 3")},
{"My result 4", new Result("My result 4")}
};
MyCache["My result 2"].IncreaseHits();
MyCache["My result 2"].IncreaseHits();
MyCache["My result 3"].IncreaseHits();
foreach (var result in MyCache.OrderByDescending(x => x.Value.Hits))
{
Console.WriteLine(result.Value.Name + " - hits " + result.Value.Hits);
}
Я думаю, вам нужно что-то вроде:
SortedDictionary<string,int> MyCache = new SortedDictionary<string, int>();
string strKey = "NewResult";
if (MyCache.ContainsKey(strKey))
{
MyCache[strKey] = MyCache[strKey] + 1;
}
else
{
MyCache.Add(strKey, 1);
}
Но SortedDictionary сортируется по ключу
Представляет коллекцию пар ключ / значение, которые отсортированы по ключу.
Вы можете извлечь словарь для List<KeyValuePair<string,int>> а затем сортировать их по значению, например:
List<KeyValuePair<string, int>> list = MyCache.ToList();
foreach (var item in list.OrderByDescending(r=> r.Value))
{
Console.WriteLine(item.Key+ " - hits " + item.Value);
}
Таким образом, вы можете иметь:
class Program
{
public static SortedDictionary<string, int> MyCache = new SortedDictionary<string, int>();
static void Main(string[] args)
{
AddToDictionary("Result1");
AddToDictionary("Result1");
AddToDictionary("Result2");
AddToDictionary("Result2");
AddToDictionary("Result2");
AddToDictionary("Result3");
List<KeyValuePair<string, int>> list = MyCache.ToList();
foreach (var item in list.OrderByDescending(r=> r.Value))
{
Console.WriteLine(item.Key+ " - hits " + item.Value);
}
}
public static void AddToDictionary(string strKey)
{
if (MyCache.ContainsKey(strKey))
{
MyCache[strKey] = MyCache[strKey] + 1;
}
else
{
MyCache.Add(strKey, 1);
}
}
}
Тогда результат будет:
Result2 - hits 3
Result1 - hits 2
Result3 - hits 1
Cache ниже предоставляет простой интерфейс Add/Get для добавления и извлечения элементов из кэша, который, очевидно, может быть улучшен. Он реализует IEnumerable, который перечисляет через кеш с требуемым поведением. Очевидно, что здесь есть проблемы с потоками, которые необходимо решить.
public class Cache<T>: IEnumerable<T>
{
//Dictionary to hold the values of the cache
private Dictionary<string, T> m_cacheStore = new Dictionary<string, T>();
//Dictionary to hold the number of times each key has been accessed
private Dictionary<string, int> m_cacheAccessCount = new Dictionary<string, int>();
public T Get(string cacheKey)
{
if (m_cacheStore.ContainsKey(cacheKey))
{
//Increment access counter
if (!m_cacheAccessCount.ContainsKey(cacheKey))
m_cacheAccessCount.Add(cacheKey, 0);
m_cacheAccessCount[cacheKey] = m_cacheAccessCount[cacheKey] + 1;
return m_cacheStore[cacheKey];
}
throw new KeyNotFoundException(cacheKey);
}
public int GetHits(string cacheKey)
{
return m_cacheAccessCount.ContainsKey(cacheKey) ? m_cacheAccessCount[cacheKey] : 0;
}
public void Add(string cacheKey, T cacheValue)
{
if(m_cacheStore.ContainsKey(cacheKey))
throw new ArgumentException(string.Format("An element with the key {0} already exists in the cache", cacheKey));
m_cacheStore.Add(cacheKey, cacheValue);
}
#region Implementation of IEnumerable
public IEnumerator<T> GetEnumerator()
{
foreach (var source in m_cacheAccessCount.OrderBy(kvp => kvp.Value))
{
yield return m_cacheStore[source.Key];
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
}
Интересно, если вы после чего-то вроде этого.
Вы можете хранить два набора отношений; все объекты, по ключу для быстрого поиска, и все объекты по Hits хранить заказ. Это имеет дополнительное преимущество ускорения доступа - вы можете получить Result, Hitsи поэтому это текущий и следующий индекс довольно быстро.
Получая результат, мы блокируем доступ, чтобы гарантировать, что мы изменим его порядок атомарно, затем возвращаем объект. Мы также обманываем, записывая количество попаданий; мы знаем, что является самым популярным, и затем мы можем просто пройтись назад по этой коллекции - могли бы даже извлечь ключи к List<Int32>Сортируйте это, затем повторите это.
public class PopularityContest{
private Dictionary<int, List<Result>> PopularityContainer { get; set; }
private Dictionary<String, Result> ResultContainer { get; set; }
private int MaxPopularity = 0;
public PopularityContest(){
PopularityContainer = new Dictionary<int, List<Result>>();
ResultContainer = new Dictionary<String, Result>();
}
private Object _SyncLock = new Object();
public Result GetResult(string resultKey)
{
Result result = ResultContainer[resultKey];
lock(_SyncLock)
{
int currentHits = result.Hits;
if(PopularityContainer.ContainsKey(currentHits) && PopularityContainer[currentHits].Contains(result))
{
PopularityContainer[currentHits].Remove(result);
}
if(!PopularityContainer.ContainsKey(currentHits + 1))
{
PopularityContainer.Add(currentHits + 1, new List<Result>());
}
PopularityContainer[currentHits + 1].Add(Result);
if((currentHits + 1) > MaxPopularity) { MaxPopularity = currentHits + 1;}
}
return result;
}
public void WritePopularity()
{
//Here could also extract the keys to a List<Int32>, sort it, and walk that.
//Note, as this is a read operation, dependent upon ordering, you would also consider locking here.
for(int i = MaxPopularity; i >= 0; i--)
{
if(PopularityContainer.Contains(i) && PopularityContainer[i].Count > 0)
{
//NB the order of items at key[i] is the order in which they achieved their popularity
foreach(Result result in PopularityContainer[i])
{
Console.WriteLine(String.Format("{0} has had {1} hits", result.ToString(), i));
}
}
}
}
}
"Правильный" способ сделать это - реализовать интерфейс IComparable ( http://msdn.microsoft.com/en-us/library/system.icomparable.aspx) в вашем классе MyCache.
Это предоставит метод CompareTo, который вам нужно будет написать в вашем коде.
Вы просто создадите этот метод и поместите туда некоторую логику, которая говорит, что этот объект больше, меньше или равен переданному объекту.
Затем вы используете его в своем клиентском коде, говоря int result = MyCache1.ComparTo(MyCache2);
Результат будет равен -1 0 или 1, если он больше или меньше или равен.
Как насчет этого:
var MyCache = new SortedDictionary<string, int?>();
MyCache['My result 2'] = (MyCache['My result 2'] ?? 0) + 1;
Хочешь что-нибудь подобное?
public class Result {
public int Hits = 0;
public string Name = "";
public void IncreaseHits() {
this.hits++;
}
public Result(String name) {
this.name = name;
}
}
class Program {
public Dictionary<string, Result> MyCache; //what structure to use?
public main() {
MyCache.Add("My result 1", new Result("My result 1"));
MyCache.Add("My result 2", new Result("My result 2"));
MyCache.Add("My result 3", new Result("My result 3"));
MyCache["My result 2"].IncreaseHits();
MyCache["My result 2"].IncreaseHits();
MyCache["My result 3"].IncreaseHits();
foreach(Result result in MyCache.Values.OrderByDesc(x => x.Hits)) {
Console.Write(result.Name + " - hits " + result.Hits);
}
}
}
альтернативно
public class MyCacheClass {
private Dictionary<string,Result> cache = new Dictionary<string, Result>();
public void IncreaseHits(string name) {
Result cached;
if (!cache.TryGetValue(name, out cached)) {
cached = cache.Add(new Result(name));
}
cached.IncreaseHits();
}
public string Add(string name) {
// Need to block duplicates....
cache.Add(name, new Result(name));
}
public IEnumerable<Result> SortDesc {
get { return cache.Values.OrderByDesc(x => x.Hits); }
}
}
class Program {
MyCacheClass MyCache = new MyCacheClass();
MyCache.Add("result1");
MyCache.IncreaseHits("My result 2");
MyCache.IncreaseHits("My result 2");
MyCache.IncreaseHits("My result 3");
foreach(Result result in MyCache.SorDesc) {
Console.WriteLine(string.Format("{0} - hits {1}",result.Name,result.Hits);
}
}
Почему бы не использовать классический List и отсортировать его, используя метод sort, и написать свой собственный файл сравнения?
MyCache.Sort(delegate(Result a, Result b)
{
if (a.hits > b.hits) return -1;
if (a.hits < b.hits) return 1;
return 0;
});
Если вам нужен доступ по ключу, вы можете иметь 2 структуры. Один для быстрого доступа, второй для хранения отсортированных данных.
Dictionary<String, Result> accessMap;
List<Result> MyCache;
accessMap["Object 1"] = obj1;
MyCache.add(obj1);
accessMap[Object 1].Increase();
//sort MyCache
foreach(Result result in MyCache) {
Console.Write(result.Name + " - hits " + result.Hits);
}