在字典中查找差异最小的键

Question

说，我有这个集合，它是通用字典

var items = new Dictionary<int, SomeData>
{
    { 1  , new SomeData() },
    { 5  , new SomeData() },
    { 23 , new SomeData() },
    { 22 , new SomeData() },
    { 2  , new SomeData() },
    { 7  , new SomeData() },
    { 59 , new SomeData() }
}

在这种情况下，键之间的最小距离(差)= 1，例如，23和22之间或1和2之间

23 - 22 = 1 or 2 - 1 = 1

问题:如何在通用字典中找到键之间的最小差异?是否有一行LINQ解决方案?

目的:如果有几个匹配，那么我只需要一个-最小的，这是需要填补项目之间的缺失键(空白)

Answer 1

我不知道如何在LINQ中一行完成，但这是针对此问题的多行解决方案。

         var items = new Dictionary<int, string>();
         items.Add(1, "SomeData");
         items.Add(5, "SomeData");
         items.Add(23, "SomeData");
         items.Add(22, "SomeData");
         items.Add(2, "SomeData");
         items.Add(7, "SomeData");
         items.Add(59, "SomeData"); 
         var sortedArray = items.Keys.OrderBy(x => x).ToArray();
         int minDistance = int.MaxValue;
         for (int i = 1; i < sortedArray.Length; i++)
         {
             var distance = Math.Abs(sortedArray[i] - sortedArray[i - 1]);
             if (distance < minDistance)
                 minDistance = distance;
         }
         Console.WriteLine(minDistance);

Answer 2

不确定Linq是最合适的，但是(大致)沿着这个应该可以工作:

var smallestDiff = (from key1 in items.Keys
                    from key2 in items.Keys
                    where key1 != key2
                    group new { key1, key2 } by Math.Abs (key1 - key2) into grp
                    orderby grp.Key
                    from keyPair in grp
                    orderby keyPair.key1
                    select keyPair).FirstOrDefault ();

Answer 3

我不会给你一个LinQ查询，因为已经有答案了。我知道这不是你想要的，但我想向你展示如何以一种非常快速和易于理解/维护的方式解决它，如果性能和易读性是你关心的任何问题。

int[] keys;
int i, d, min;
keys = items.Keys.ToArray();
Array.Sort(keys); // leverage fastest possible implementation of sort
min = int.MaxValue;
for (i = 0; i < keys.Length - 1; i++)
{
  d = keys[i + 1] - key[i]; // d is always non-negative after sort
  if (d < min)
  {
    if (d == 2)
    {
      return 2; // minimum 1-gap already reached
    } else if (d > 2) // ignore non-gap
    {
      min = d;
    }
  }
}
return min; // min contains the minimum difference between keys

因为只有一种类型，这个非linq解决方案的性能执行得非常快。我并不是说这是最好的方法，只是说您应该衡量两种解决方案并比较性能。

EDIT:根据您的目的，我添加了这一段:

    if (d == 2)
    {
      return 2; // minimum 1-gap already reached
    } else if (d > 2) // ignore non-gap
    {
      min = d;
    }

这是什么意思?

假设具有1-gap的概率很高，如果您已经达到最小差距，则可能更快地检查min的每次变化。根据概率，当您完成for循环的1%或10%时可能会发生这种情况。因此，对于非常大的集合(例如，超过100万或10亿)，一旦你知道预期的概率，这种概率方法可能会给你带来巨大的性能提升。

相反，对于小集合或当1-gap的概率很低时，这些额外的CPU周期被浪费了，您最好不要进行检查。

对于非常大的数据库(考虑概率索引)，概率推理变得相关。

问题是你必须事先估计概率效应是否以及何时开始，这是一个相当复杂的话题。

EDIT 2: 1-gap实际上索引差为2。且1的索引差为非间隙(中间不存在插入索引的间隙)。

所以之前的解决方案是完全错误的，因为只要两个索引是连续的(比如34,35)，最小值将是1，这根本不是一个间隙。

由于这个间隙问题，内部if()是必要的，在这一点上，概率方法的开销是无效的。您最好使用正确的代码和概率方法!

Answer 4

我认为LINQ是最简单的

首先，从你的字典中创建diff pair

var allPair = items.SelectMany((l) => items.Select((r) => new {l,r}).Where((pair) => l.Key != r.Key));

然后求diff的最小值

allPair.OrderBy((pair) => Math.Abs(pair.l.Key - pair.r.Key)).FirstOrDefault();

但是您可能有多个具有相同差值的对，因此您可能需要在使用OrderBy之前使用GroupBy，然后自己处理多个对

Answer 5

答案中未列出的单行解决方案:

items.Keys.OrderBy(x => x).Select(x => new { CurVal = x, MinDist = int.MaxValue }).Aggregate((ag, x) => new { CurVal = x.CurVal, MinDist = Math.Min(ag.MinDist, x.CurVal - ag.CurVal) }).MinDist