c# - オブジェクトを使用した値によるC＃ソートリスト

Question

C# でオブジェクトの "順序付けされた" キャッシュを作成しようとしています。この順序は、アクセスされた回数によって決定されます。

Dictionary、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

score 2 · Accepted Answer

このようなものが必要になったとき、と呼ばれるものを作成しましたMruDictionary。LinkedList<T>、および a で構成されていましたDictionary<string, LinkedListNode<T>>(Tはオブジェクトのタイプであり、オブジェクトキーは type でしたstring)。

アクセスは辞書経由です。アイテムがアクセスされると、リストの先頭に移動されます。アイテムが追加されると、リストの先頭に追加されます。リストのサイズが設定された最大値を超えた場合、リストの最後のノードが削除されます。

これは非常にうまくいきました。アイテムは使用回数順ではなく、厳密な MRU 順で保管されていました。これにより、通常、最も頻繁に使用されるアイテムがキャッシュに保持されますが、人気のあるアイテムが長期間使用されていない場合、フラッシュされます。私の目的では、これは非常にうまく機能しました。

私はそれについて記事を書きました。説明付きの完全なソースはhttp://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626で入手できます。

本当に必要な場合は、ヒット数を簡単に追加できます。

score 2 · Accepted Answer

Building upon your pseudo code, this seems to be working:

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

score 1 · Accepted Answer

このようなものを求めているのだろうか。

2 セットのリレーションシップを保存できます。検索を高速化するためのキーごとのすべてのオブジェクトと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));
            }
         }

      }
    }

}

score 1 · Accepted Answer

以下の 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
}

score 0 · Accepted Answer

このようなものが欲しいですか。

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

score 0 · Accepted Answer

これはどうですか：

var MyCache = new SortedDictionary<string, int?>();
MyCache['My result 2'] = (MyCache['My result 2'] ?? 0) + 1;

score 0 · Accepted Answer

これを行う「適切な」方法は、MyCache クラスにIComparable ( http://msdn.microsoft.com/en-us/library/system.icomparable.aspx ) インターフェイスを実装することです。

これにより、コードに記述する必要がある CompareTo というメソッドが公開されます。

そのメソッドを作成し、このオブジェクトが渡されたオブジェクトより大きい、小さい、または等しいかどうかを示すロジックをそこに配置するだけです。

次に、クライアントコードで次のように使用しますint result = MyCache1.ComparTo(MyCache2);

結果は、大きいか小さいか等しいかに基づいて、-1 0 または 1 になります。

score -2 · Accepted Answer

従来の 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 つの構造を持つことができます。1 つは高速アクセス用、もう 1 つは並べ替えられたデータを保持するためのものです。

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

c# - オブジェクトを使用した値によるC＃ソートリスト

9 に答える 9

Related

Reference