0

我需要通过两个整数键来超快速地存储和检索值。

所以我有输入值uint Id1, uint Id2并且需要得到uint Count.

Id1我也知道和的最大值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

一个小的（？）改进，您可以TryGetValue用来避免两次查找字典：

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 回答