Список С#, отсортированный по значению с объектом

Когда мне нужно было что-то подобное, я создал то, что назвал 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 разбирается по ключу

SortedDictionary — MSDN

Представляет набор пар ключ/значение, отсортированных по ключу.

Вы можете извлечь словарь в 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

Интересно, если вы после чего-то вроде этого.

Вы можете хранить два набора отношений; все объекты по ключу для быстрого поиска и все объекты по 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));
            }
         }

      }
    }

}

Кэш ниже предоставляет простой интерфейс 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
}

«Правильный» способ сделать это — реализовать 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);
   }
}

Почему бы не использовать классический список и не отсортировать его, используя метод сортировки, и не написать свой собственный метод сравнения?

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);
}