C# 查找字典

Question

我正在尝试创建一个基于信号强度估算位置的程序。信号强度值是一个整数，然后我需要一个包含范围的查找字典。

因此，我需要像这样的东西：

Signal Strenth             Position
0-9                            1
10-19                          2
20-29                          3

然后我想查找信号强度与位置的关系，例如15会对应位置2。

我知道我可以使用一堆if语句，但是是否有一种好的方法可以使用某种查找字典来完成呢？

- DNN

Answer 1

怎么样：

int position = signalStrength / 10 + 1;

善良之情，

Dan

- Daniel Elliott

---

假设范围确实是以10个为一组，而这不仅仅是一个样本异常，那么这是一个非常优秀的答案。 - Adam Robinson

随着强度的增加，它们不总是以10为单位。我喜欢这个答案。 - DNN

Answer 2

如果您有任意但连续的范围，可以使用上限数组并执行二分搜索以获取位置：

// Definition of ranges
int[] ranges = new int[] { 9, 19, 29 };

// Lookup
int position = Array.BinarySearch(ranges, 15);
if (position < 0)
    position = ~position;

// Definition of range names
string[] names = new string[] { "home", "street", "city", "far away" };

Console.WriteLine("Position is: {0}", names[position]);

Array.BinarySearch 会返回数组中元素的索引（前提是数组已排好序），如果该元素存在，否则它将返回按位反转的索引值，以表示应该将该项插入以保持数组排序。

- dtb

---

更详细的解释会使这个答案更完美。 - Adam Robinson

好的答案。适用于任何没有间隙的任意范围集合。 - jrista

谢谢，如果位置不仅仅是一个递增的数字，而是有命名的话，是否可以使用类似的方法？ - DNN

@DNN：这是一种情况，你可以使用一个字典，其中包含一个单独的 int 键，该键对应于此方法返回的数字。 - Adam Robinson

@DNN：只需将位置映射到字符串中，例如使用数组。只需确保在要查找的值大于最大范围时定义一个比您的范围数量多的项。 - dtb

Answer 3

当您想使用字典时，您需要至少一些特殊的键类型来处理范围。KeyType可以是抽象的，有两个派生类型KeyTypeRange（int int）和KeyTypeSearch（int）。必须实现一些特殊的比较逻辑，以便将KeyTypeSearch与KeyTypeRange进行比较。

SortedDictionary<KeyType,int>  lookup = new Dictionary<int,int>();
lookup.Add( new KeyTypeRange(1,10),1);
lookup.Add( new KeyTypeRange(11,20),2);
lookup.Add( new KeyTypeRange(21,30),3);
lookup.TryGetValue( new KeyTypeSearch(15) );

这段文字展示了在字典中使用不同的搜索键和键值的可能解决方案。但是，对于这个问题来说，这似乎有些过度。最好通过二分查找方法来解决此问题。

- Thomas Maierhofer

---

提及这种方法是很好的。我更喜欢二分查找，但指出使用KeyTypeRange而不是像之前提到的那样加载一个包含所有可能值的Dictionary<int,int>也是很好的。 - Steve

@Thomas：听起来很有趣。你能详细说明一下你的想法吗？Dictionary<T,U> 是以哈希表实现的。你如何实现 KeyTypeRange 和 KeyTypeSearch 的 GetHashCode，使得 new KeyTypeSearch(15) 产生 new KeyTypeRange(1,10) 的结果呢？ - dtb

实际上，你不能使用Dictionary<T,U>，必须使用SortedDictionary<T,U>，因为无法为此问题提供哈希函数。 SortedDictionary的键是通过int IComparer<T>.Compare(T x,T y)进行比较的，这很容易实现。 - Thomas Maierhofer

Answer 4

好的功能是目的的体现。以上所有解决方案都适用于假定任何给定范围都是少量整数的情况。否则，您可能需要使用真实世界的数学函数来确定您的组。例如，对于给定的示例，您的答案函数将是x％10 + 1；这比使用字典运行得快得多。

- Russell Steen

Answer 5

你可以使用字典，其中第一个整数是信号强度，第二个整数是位置。您需要为范围内的每个值添加一个条目（因此，对于信号强度0、位置1，信号强度1、位置1等，都需要添加一个条目），但这将是非常快速的单行查找。

类似以下代码：

Dictionary<int, int> values;

values = new Dictionary<int, int>();

values[0] = 1;
values[1] = 1;
...
values[29] = 3;

然后，要访问它：

Console.WriteLine(values[27].ToString());

- Michael Todd

Answer 6

为了未来的扩展，我会建立2个字典。以防万一这些费率发生变化。

dictionary<string,dictionary<int,int>>

或者使用自定义类，字符串将是静态字符串，如低、中、高，然后您可以在foreach初始化初始值时更改范围。

- Brandon Grossutti

Answer 7

一种解决方案是使用简单列表，其中列表中的每个位置代表您正在扫描的不同位置。在代码中，它可能看起来像这样（假设所有位置号码都是顺序的）：

**注意：我实际上没有运行此代码以确保它按原样工作...您还可能需要在Range上实现IEqualityComparer，以便IndexOf操作返回正确的位置：

public class Controller
{
   List m_positions = new List();

   public void LoadPositions()
   {
      m_positions.Add(new Range(0, 9));
      m_positions.Add(new Range(10, 19));
      m_positions.Add(new Range(20, 29));
   }

   public int GetPosition (int signal)
   {
      Range range = m_positions.Single(a => IsBetween(signal, a.Min, a.Max));

      return m_positions.IndexOf(range);
   }

   private static bool IsBetween (int target, int min, int max)
   {
      return min = target;
   }
}

这可能是相当不言自明的，但为了避免任何混淆，这就是 Range 类可能看起来像什么：

public class Range
{
   public Range(int min, int max)
   {
      this.Min = min;
      this.Max = max;
   }

   public int Min
   {
      get;
      private set;
   }

   public int Max
   {
      get;
      private set;
   }
}

- jeremyalan

Answer 8

如果信号范围和位置之间存在直接关系，则使用@agileguy建议的方法。

如果您的位置在信号强度上呈非线性分布，则一种方法是：

class SignalStrengthPositionMapper
{
    private static readonly int[] signalStrength = { Int32.MinValue, 0, 5, 11, 15, 20, 27, 35 };
    public static int GetPosition(int strength)
    {
        return StrengthSearch(0, signalStrength.Length, strength);
    }

    // modified binary search
    private static int StrengthSearch(int start, int end, int strength)
    {
        int mid = 0;
        while (start <= end)
        {
            mid = (start + end) / 2;

            if (strength >= signalStrength[mid])         // lower bound check
            {
                start = mid + 1;
                if (strength < signalStrength[start])    // upper bound check
                    return mid;
            }
            else if (strength < signalStrength[mid])     // upper bound check
            {
                end = mid - 1;
                if (strength >= signalStrength[end])     // lower bound check
                    return mid;
            }
        }
        return 0;
    }
}

- Vivek

Answer 9

尝试使用泛型：

Dictionary<int,int>  lookup = new Dictionary<int,int>();
lookup.Add(0,1);
lookup.Add(1,1);
lookup.Add(2,1);
lookup.Add(3,1);
...
lookup.Add(9,1);
lookup.Add(10,2);
lookup.Add(11,2);

然后，lookup[22]将返回值3。我建议使用一组循环来创建您的“范围”。使用此方法，您可以保证O(1)的访问时间。

- Charlie Salts

---

你是认真建议他为范围内的每个整数值添加不同的值到字典中吗？ - Adam Robinson

是的。对于少量范围，这可能是OP正在寻找的。您有更好的解决方案吗？如果有，请发表。 - Charlie Salts

@Charlie：我不需要重复回答已经由dtb和agileguy提交的答案。 - Adam Robinson