开发者

Which is best way to Find the max value in a delphi TDictionary?

i have a TDictionary declared like so TDictionary<String,Integer>, Now i want to get the max of the value stored in the TDictionary. i can do this iterating over the TDictionary and comparing the values, but I'm wondering exist a better way to do this? exist any function or maybe the dictionary can be sorted by the values to retrieve the max value stored?

this is which i'am doing now

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开发者_如何学Go MaxValue:=i;

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


I haven't used this particular class, but the excellent Delphi Collections 1.1.1. has a class TDoubleSortedBidiDictionary which has sorted values.

When to use: This bidirectional dictionary implementation uses two AVL trees. Use it if you care about keys and values being sorted.

btw, if you are "storing the number of occurences of each word", have a look at TBag from Delphi Collections. It is a Delphi implementation of MultiSet.


There are no ordering guarantees on a TDictionary so iterating is the only solution.

Any performance improvement by necessity would have to involve a different data structure.


Are you ever deleting items or decrementing an item's count? If not, you might consider creating a new descendant of TDictionary where you override the Add() method and keep track of the largest item added thus far. The code below is pseudo-code and not quite correct. (For example, I think that Add() should probably be overriding a function, but I coded it like a procedure). But it gives the general idea. Of course this code only keeps track of one item: the most recently added item that is largest. If you needed to have a list of all items that have the largest count, you could keep a string list rather than fLargestWordSoFar and fLargestCountSoFar .

Even if you were incrementing items' counts after they were added, you could extend the code below to easily handle that in a similar way that the Add() does.

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;


Dictionary is the correct datastructure if the main purpose is to quickly look up a string and update the count. Usually for this kind of algorithms you spend more time counting the words than finding the max value. When looping through millions of words it could mean significant performance benefits over a tstringlist because of faster lookup.

You can use MaxIntValue(MyDict.ToArray) from Math-unit for more elegant code but it will still be sequential. If you find that finding the max value is a performance bottleneck then you can consider alternate data structures.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜