在Delphi TDictionary中找到最大值的最佳方法是什么？

Question

我有一个声明如下的 TDictionary： TDictionary<String,Integer>，现在我想获取存储在 TDictionary 中值的最大值。我可以通过遍历 TDictionary 并比较值来实现这一点，但我想知道是否存在更好的方法？ 是否存在任何函数或者字典可以按值进行排序以检索存储的最大值？

以下是我现在所做的：

var
   MyDict       : TDictionary<String,Integer>;
   MaxValue, i  : Integer;
begin
   MyDict:=TDictionary<String,Integer>.Create;
   try    
     MyDict.Add('this',1);
     MyDict.Add('is',7);
     MyDict.Add('a',899);
     MyDict.Add('sample',1000);
     MyDict.Add('finding',12);
     MyDict.Add('the',94);
     MyDict.Add('max',569);
     MyDict.Add('value',991);

     MaxValue:=MyDict.ToArray[0].Value;
     for i in MyDict.Values do
      if i>MaxValue then MaxValue:=i;

     ShowMessage(Format('The max value is %d',[MaxValue]));
   finally
     MyDict.Free;
   end;
end;

- Salvador

---

TDictionary 中没有 max。您确定正在使用正确的数据结构吗？遍历它或查找 min/max 不是字典的设计方式。想象一下实际的词典 - 您查找一个单词并想知道它的相关定义。您不会查看最高的“单词”是什么... - Ken White

@Ken 我正在使用TDictionary来存储每个单词出现次数的数量。这段代码只是一个简化的示例。 - Salvador

@Salvador：那么你正在使用错误的数据类型。使用TStringList，像往常一样存储字符串和对象数组中的计数。然后，您可以进行自定义排序并按计数对它们进行排序。正如我所说，想象一下真正的字典以及您将如何使用它。 - Ken White

@Ken，也许不是。TDictionary是一种非常好的数据结构来收集信息（即：检查单词是否存在于列表中，增加出现次数）。一旦收集到数据，人们可能希望切换到另一种数据结构以获取不同的算法特性。或者只需忍受在随机顺序遍历列表以找到最大值时的低效率。如果找到最大值只是一次性工作，那就没有问题。 - Cosmin Prund

@Cosmin：也许，如果有大量的数据。然而，如果你处理的是适度数量的数据，并且想要能够排序或查找最大出现次数，特别是当你处理字符串键和整数计数器时，我并不认为它是必要的。我想这取决于数据量和你使用TDictionary做什么；在计算出现次数的情况下，除非你处理的单词数量非常大，否则我不确定我会选择字典。 - Ken White

@Ken White，这是一个简单的数据结构属性问题：TDictionary提供O(1)的插入和更新，其中“1”实际上是一个常数“c”。其他结构，如平衡树，可能会提供O(Log(n))的查找，对于足够大的“c”和足够小的“n”，我们将有Log(n) < c。像往常一样，没有“万能”的数据结构，需要了解所提出的数据结构的属性并选择最适合手头问题的那个。 - Cosmin Prund

Answer 1

TDictionary没有任何排序保证，因此迭代是唯一的解决方案。

任何必要的性能提升都必须涉及不同的数据结构。

- David Heffernan

Answer 2

我没有使用过这个特定的类，但出色的Delphi Collections 1.1.1有一个名为TDoubleSortedBidiDictionary的类，具有排序值。

何时使用：这个双向字典实现使用了两个AVL树。如果您关心键和值被排序，请使用它。

顺便说一下，如果您正在“存储每个单词的出现次数”，请查看Delphi Collections中的TBag。它是MultiSet的Delphi实现。

- awmross

---

就数据结构而言，AVL树不是字典（即它不是“哈希映射”）。根据列表中单词的数量，使用简单的TDictionary来收集数据，然后在收集完数据后切换到不同的数据结构可能是最好的方法。 - Cosmin Prund

@Cosmin 这是一个字典；使用 AVL 树实现。如果没有表述清楚，我很抱歉。 - awmross

[...] 一个 TDoubleSortedBidiDictionary 将会更糟糕，因为我假设它使用了两个 AVL 树，一个用于值，一个用于键。问题是，在 每次 数据收集算法的迭代中，您将在 Keys 字典中进行查找，然后进行两个 AVL 树插入（如果未找到“键”），或者进行一次删除和一次插入（如果找到“键”并且需要更新值）。 - Cosmin Prund

@Cosmin 我同意。原始解决方案听起来不错（虽然我会用真实数据对其进行剖析以确保）。如果您将其编写为单独的答案，我可以点赞它。 - awmross

“字典”就是键和值之间的映射。并不要求O(1)的性能。 - awmross

Answer 3

如果主要目的是快速查找字符串并更新计数，则字典是正确的数据结构。通常，对于这种算法，您花费的时间更多的是计算单词而不是查找最大值。当循环遍历数百万个单词时，与tstringlist相比，它可能意味着显着的性能优势，因为查找速度更快。

您可以使用Math-unit中的MaxIntValue(MyDict.ToArray)来获得更加优雅的代码，但它仍然是顺序的。如果发现查找最大值是性能瓶颈，则可以考虑使用其他数据结构。

- Ville Krumlinde

Answer 4

您是否曾经删除过项目或者减少过一个项目的数量？如果没有，您可以考虑创建TDictionary的一个新子类，在其中重写Add()方法并跟踪到目前为止添加的最大项。以下代码是伪代码，不完全正确（例如，我认为Add()应该覆盖一个函数，但我将其编码为过程）。但它给出了一般的想法。当然，这段代码只跟踪一个项目：最近添加的最大项。如果您需要有一个包含所有计数最大的项目列表，您可以使用字符串列表而不是fLargestWordSoFar和fLargestCountSoFar。

即使您在添加后递增项目的计数，您也可以扩展下面的代码以类似于Add()的方式轻松处理它。

type
  MyTDictionary = object(TDictionary) // almost definitely not correct syntax here...
  private
    fLargestCountSoFar: Integer;
    fLargestWordSoFar: String;   
  public
    procedure Add( S: String; I:Integer); override;   
  end;

implementation

procedure MyTDictionary.Add( S: String; I:Integer); 
begin
  if (I > fLargesteCountSoFar) then
  begin
    fLargestCountSoFar := I;
    fLargestWordSoFar  := S;    
  end;
  inherited Add( S, I);
 end;

- RobertFrank

---

Salvador：对我上面的回答有一个评论。确保您真的需要进行这种优化。我总是惊讶于我可以多快地阅读整个列表。进行一些基准测试以确认暴力“读取每个元素”的方法太慢了。您可能会发现它是令人满意的，这将使您避免花费时间和实施上述代码的风险。记住 Knuth：“我们应该忘记小效率，大约97%的时间：过早的优化是万恶之源”。 - RobertFrank

绝对不是正确的语法。而且继承在这里是一场灾难。有很多修改容器的方法，而不仅仅是添加。 - David Heffernan