5

在 C# 中进行查找表的最有效方法是什么

我有一个查找表。有点像

0 "Thing 1"
1 "Thing 2"
2 "Reserved"
3 "Reserved"
4 "Reserved"
5 "Not a Thing"

因此，如果有人想要“Thing 1”或“Thing 2”，他们会传入 0 或 1。但他们也可能会传入其他内容。我有 256 个这类东西，其中可能有 200 个是保留的。

那么最有效的设置是什么？

  • 获取所有值的字符串数组或字典变量。然后取整数并返回该位置的值。

我对这个解决方案的一个问题是所有的“保留”值。我不想创建那些多余的“保留”值。否则我可以针对所有“保留”的不同位置使用 if 语句，但它们现在可能只是 2-3、可能是 2-3、40-55 以及字节中的所有不同位置。这个 if 语句会很快变得不守规矩

  • 我在想的另一个选择是 switch 语句。而且我将拥有所有 50 个已知值，并且会通过并默认保留值。

我想知道这是否比创建字符串数组或字典并返回适当的值要多得多。

  • 还有什么？有没有其他方法可以考虑？
4

9 回答 9

14

“使用其键检索值非常快，接近 O(1)，因为 Dictionary(TKey, TValue) 类是作为哈希表实现的。”

var things = new Dictionary<int, string>();
things[0]="Thing 1";
things[1]="Thing 2";
things[4711]="Carmen Sandiego";
于 2009-12-06T16:48:57.470 回答
6

在 C# 中查找整数值的绝对最快方法是使用数组。如果您尝试一次进行数万次查找，这可能比使用字典更可取。在大多数情况下，这是矫枉过正的。您更有可能需要优化开发人员时间而不是处理器时间。

如果保留键不只是所有不在查找表中的键（即，如果对键的查找可以返回找到的值、未找到状态或保留状态），则需要保存某处的保留键。将它们保存为具有魔术值的字典条目（例如，保留值为 null 的任何字典条目的键）是可以的，除非您编写的代码迭代字典的条目而不过滤它们。

解决该问题的一种方法是使用单独HashSet<int>的来存储保留的密钥，并可能将整个内容烘焙到一个类中，例如：

public class LookupTable
{
   public readonly Dictionary<int, string> Table { get; }
   public readonly HashSet<int> ReservedKeys { get; }

   public LookupTable()
   {
      Table = new Dictionary<int, string>();
      ReservedKeys = new HashSet<int>();
   }

   public string Lookup(int key)
   {
      return (ReservedKeys.Contains(key))
         ? null
         : Table[key];
   }
}

你会注意到这仍然存在魔法值问题——Lookup如果键被保留则返回 null，如果它不在表中则抛出异常——但至少现在你可以在Table.Values不过滤魔法值的情况下进行迭代。

于 2009-12-06T19:05:43.123 回答
3

如果您有很多保留（当前未使用）的值，或者整数值的范围可以变得非常大，那么我会使用通用字典（字典）：

var myDictionary = new Dictionary<int, string>();
myDictionary.Add(0, "Value 1");
myDictionary.Add(200, "Another value");
// and so on

否则，如果您有固定数量的值并且当前只有少数未使用，那么我将使用字符串数组 (string[200]) 并将保留的条目设置/保留为空。

var myArray = new string[200];
myArray[0] = "Value 1";
myArray[2] = "Another value";
//myArray[1] is null
于 2009-12-06T16:50:02.227 回答
3

查看 HybridDictionary。它会根据大小自动调整其底层存储机制，以获得最大的效率。

http://msdn.microsoft.com/en-us/library/system.collections.specialized.hybriddictionary.aspx

于 2009-12-06T16:52:12.060 回答
0

内置的Dictionary对象（最好是通用字典）非常适合此操作，并且专门设计用于快速/高效地检索与键相关的值。

从链接的 MSDN 文章：

使用它的键检索一个值非常快，接近 O(1)，因为 Dictionary<(Of <(TKey, TValue>)>) 类是作为哈希表实现的。

就您的“保留”键而言，如果我们只谈论几百个键/值，我根本不会担心。只有当您达到数万甚至数十万个“保留”键/值时，您才会想要实现更高效的东西。

在这些情况下，最有效的存储容器可能是稀疏矩阵的实现。

于 2009-12-06T16:50:06.453 回答
0

我不太确定我是否正确理解了您的问题。你有一个字符串集合。每个字符串都与一个索引相关联。消费者请求提供一个索引，您返回相应的字符串，除非该索引是reserved。对？

你不能简单地将数组中的保留项设置为空。

如果不是，使用不包含保留项的字典似乎是一个合理的解决方案。

无论如何，如果你澄清你的问题，你可能会得到更好的答案。

于 2009-12-06T16:50:11.143 回答
0

将所有值加载到

var dic = new Dictionary<int, string>();

并将其用于检索：

string GetDescription(int val)
{
     if(0 <= val && val < 256)
        if(!dic.Contains(val))
           return "Reserved";
        return dic[val];
    throw new ApplicationException("Value must be between 0 and 255");
}
于 2009-12-06T16:50:56.657 回答
0

我会使用字典来进行查找。这是迄今为止进行查找的最有效方法。使用字符串将在 O(n) 区域的某处运行以查找对象。

如果需要，为所有人提供第二个字典以进行反向查找可能会很有用

于 2009-12-06T16:51:54.823 回答
0

您的问题似乎暗示查询键是一个整数。由于您最多有 256 个项目，因此查询键在 0..255 范围内，对吗？如果是这样，只需有一个包含 256 个字符串的字符串数组，并将键用作数组的索引。

如果您的查询键是一个字符串值，那么它更像是一个真正的查找表。使用 Dictionary 对象很简单，但如果您追求原始速度的一组少至 50 个左右的实际答案，那么使用二分搜索或 trie 等自己动手的方法可能会更快。如果你使用二分搜索，因为项目的数量很少，你可以展开它。

项目列表多久更改一次？如果它只是很少更改，您可以通过生成代码来执行搜索来获得更快的速度，然后您可以编译并执行这些代码来执行每个查询。

另一方面，我假设您已经通过分析或获取 stackshots证明了此查找是您的瓶颈。如果在此查询中花费的 time-when-slow 不到 10%，那么这不是您的瓶颈，因此您最好做最容易编码的事情。

于 2009-12-06T22:28:46.573 回答