0

2 つの整数キーによって値を超高速で保存および取得する必要があります。

したがって、入力値uint Id1, uint Id2があり、取得する必要がありますuint Count。

Id1また、 andの最大値も知っていますId2（約5 000 000です）。

私の現在の実装には、アプリケーションの作業時間の約 70% がかかり、数日かかることもあります。

標準の .net 辞書を使用するだけで、もちろん改善できます。しかし、これはコンピューター サイエンスにおいて非常に有用な操作であり、より効率的なアルゴリズムが存在することは間違いないと思います。

これが私の実装です

void Main()
{
    var rep = new Repository();

    var sw = new Stopwatch();

    sw.Start();

    for (uint i = 0; i < 10000; i++)
    {
        for (uint j = 0; j < 1000; j++)
        {
            rep.Add(new DomainEntity(){Id1 = i, Id2 = j, Count = 1});
        }
    }

    for (uint i = 0; i < 10000; i++)
    {
        for (uint j = 0; j < 1000; j++)
        {
            rep.GetDomainEntityByIds(i,j);
        }
    }

    sw.Stop();
    Console.WriteLine ("Elapsed:{0}", sw.Elapsed);
}

public class Repository
{
        private readonly Dictionary<Tuple<UInt32, UInt32>, UInt32> _dictStore;

        public Repository()
        {
            _dictStore = new Dictionary<Tuple<uint, uint>, uint>();
        }

        public uint Add(DomainEntity item)
        {
            var entry = MapToTableEntry(item);
            _dictStore.Add(entry.Key,entry.Value);
            return 0;
        }

        public void Update(DomainEntity item)
        {
            var entry = MapToTableEntry(item);
            _dictStore[entry.Key] = entry.Value;
        }

        public IEnumerable<DomainEntity> GetAllItems()
        {
            return _dictStore.Select(MapToDomainEntity);
        }

        public DomainEntity GetDomainEntityByIds(uint articleId1, uint articleId2)
        {
            var tuple = new Tuple<uint, uint>(articleId1, articleId2);

            if (_dictStore.ContainsKey(tuple))
            {
                return MapToDomainEntity(new KeyValuePair<Tuple<uint, uint>, uint>(tuple, _dictStore[tuple]));
            }

            return null;
        }

        private KeyValuePair<Tuple<uint, uint>, uint> MapToTableEntry(DomainEntity item)
        {
            return new KeyValuePair<Tuple<uint, uint>, uint>(new Tuple<uint, uint>(item.Id1,item.Id2), item.Count);
        }

        private DomainEntity MapToDomainEntity(KeyValuePair<Tuple<uint, uint>, uint> entry)
        {
            return new DomainEntity
            {
                Id1 = entry.Key.Item1,
                Id2 = entry.Key.Item2,
                Count = entry.Value,
            };
        }
}

public class DomainEntity
{
        public uint Id1 { get; set; }
        public uint Id2 { get; set; }
        public uint Count { get; set; }
}
4

3 に答える 3

5

1 つの小さな (?) 改善点としてTryGetValue、辞書を 2 回検索することを回避するために使用できます。

public DomainEntity GetDomainEntityByIds(uint articleId1, uint articleId2)
{
    var tuple = new Tuple<uint, uint>(articleId1, articleId2);
    uint value;
    if (_dictStore.TryGetValue(tuple, out value))
    {
        return MapToDomainEntity(new KeyValuePair<Tuple<uint, uint>, uint>(tuple, value));
    }

    return null;
}
于 2013-03-16T12:24:16.490 に答える
1

やりたいことは、効率的なキーとハッシュを使用して効率的な辞書を作成することです。ディクショナリは常に 32 ビット値を使用し、約 45 ビットのデータがあるため、一意のハッシュを作成することはできませんが、最善を尽くす必要があります。

  • 二重ルックアップではなく、常に TryGetValue() を使用してください。
  • 値型のキーを持つ辞書を使用する場合は、引数として辞書コンストラクターに渡されるカスタム IEqualityComparer を使用します。
  • カスタム ハッシュ コードを使用して、サブキーから最大量の情報を 32 ビット ハッシュに絞り込みます。

例：

public class Storage 
{
   private Dictionary<Key, DomainObject> dict;

   public Storage()
   {
      dict = new Dictionary<Key, DomainObject>(Key.Comparer.Instance)
   }

   public DomainObject Get(uint a, uint b)
   {
      DomainObject obj;
      dict.TryGetValue(new Key(a,b), out obj);
      return obj;
   }

   internal struct Key 
   {
       internal readonly uint a;
       internal readonly uint b;

       public Key(uint a, uint b)
       {
          this.a = a;
          this.b = b;
       }     

       internal class Comparer : IEqualityComparer<Key>
       {
           internal static readonly Comparer Instance = new Comparer();
           private Comparer(){}

           public bool Equals(Key x, Key y)
           {  
               return x.a == y.a && x.b == y.b;
           }  

           public int GetHashCode(Key x)
           {    
              return (int)((x.a & 0xffff) << 16) | (x.b & 0xffff));
           }
       } 
   }  
}
于 2013-03-16T12:50:52.853 に答える
0

そこでは、 との変換など、多くの追加作業を行っていますKeyValuePair。また、 DomainEntity参照型であるため、検索するたびにキーと値から参照を作成するのではなく、それらへの参照を辞書に格納するだけでよいでしょう。

次のように辞書を作成します。

var _dictStore = new Dictionary<Tuple<uint, uint>, DomainEntity>();

それで：

public uint Add(DomainEntity item)
{
    var key = new Tuple<uint, uint>(item.Id1, item.Id2);
    _dictStore.Add(key, item);
    return 0;
}

そしてルックアップ：

public DomainEntity GetDomainEntityByIds(uint articleId1, uint articleId2)
{
    var key = new Tuple<uint, uint>(articleId1, articleId2);
    DomainEntity value;
    if (!_dictStore.TryGetValue(key, out value))
    {
        value = null;
    }
    return value;
}
于 2013-03-16T12:52:12.200 に答える