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

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 .

Up vote 5 down vote favorite share g+ share fb share tw.

I have a TDictionary declared like so TDictionary, 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; MaxValue, I : Integer; begin MyDict:=TDictionary. 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. ToArray0. 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; delphi generics dictionary delphi-xe link|improve this question asked May 4 '11 at 2:21Salvador3,282845 93% accept rate.

There is no max in a TDictionary. Are you sure you're using the right datastructure? Iterating through it or looking for min/max isn't how a dictionary is designed to work.

Think about an actual dictionary - you find a word and want to know it's associated definition. You don't look to see what the highest "word" is... – Ken White May 4 '11 at 2:34 1 @Ken I'm using the TDictionary to store the number of ocurrences for each word. The code is just a simplified sample.

– Salvador May 4 '11 at 2:43 2 @Salvador: Then you're using the wrong data type. Use a TStringList, storing the string as usual and the count in the Objects array. Then you can do a custom sort and order them by the count.

As I said, think of a real dictionary and how you'd use it. – Ken White May 4 '11 at 2:51 2 @Ken, maybe not. A TDictionary is a very good data structure to gather the information (ie: check if word exists in list, increment number of occurrences).

Once the data is gathered one might want to swap to a different kind of data structure in order to obtain different algorithmic properties. Or simply suffer through the inefficiency of walking the list in random order in order to find the maximum. If finding the maximum is a one-time-job, it's not a problem at all.

– Cosmin Prund May 4 '11 at 8:26 @Cosmin: Maybe, if there's a lot of data. However, I'm not convinced it is if you're dealing with a moderate amount of data and you want to be able to sort or find the max occurrences, especially when you're dealing with a string key and integer counter. I guess to me it would depend on the amount of data and what else you're using the TDictionary for; in the case of counting occurrences, unless you're dealing with a very large number of words, I'm not sure I'd choose a dictionary.

– Ken White May 4 '11 at 16:22.

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.

Salvador: One comment to my answer above. Make sure that you really need to do this kind of optimization. I'm always surprised at how fast I can read through an entire list.

Do some benchmarks to confirm that that the brute-force "read every element"-approach is too slow. You may find that it's satisfactory, which will allow you to avoid taking the time and risk of implementing the code above. Remember Knuth: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil" – Robert Frank May 5 '11 at 2:14.

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.

1 As far as data structures are concerned, an AVL tree is not a Dictionary (ie: it's not a "hash map"). Depending on the number of words in the list, using a simple TDictionary to gather the data and then swapping to a different data structure once the data is collected might be the best approach. – Cosmin Prund May 4 '11 at 8:24 @Cosmin It is a Dictionary; implemented using AVL trees.

Sorry if this wasn't clear. – awmross May 4 '11 at 9:02 @Cosmin If you think you have a good solution, why not add it as a separate answer? – awmross May 4 '11 at 9:10 @awmross, I can't provide a better solution because I don't fully understand the problem.

If the whole purpose of the program is to display the word with the maximum occurrence then the program is optimal as is. I wanted to point out the different statistical properties of the alternative implementations: A hash-map based dictionary as Delphi's TDictionary offers O(1) insert and update, very good for the initial half of the OP's algorithm (gathering data). An AVL-based Dictionary offers O(Log(N)) updates and slightly more for inserts, not so good for the same algorithm ... – Cosmin Prund May 4 '11 at 10:02 ... an TDoubleSortedBidiDictionary is going to be much worst, since I assume it makes use of two AVL trees, one for the values, one for the keys.

The problem is, with each iteration of the data gathering algorithm you're going to do a lookup in the Keys dictionary followed by two AVL tree inserts (if the "key" is not found) or followed by one delete and one insert (if the "key" is found and the value needs to be updated. – Cosmin Prund May 4 '11 at 10:05.

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.

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.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.

Related Questions