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.
精彩评论