Какой лучший способ найти максимальное значение в delphi TDictionary? - PullRequest
Новая
       55

Какой лучший способ найти максимальное значение в delphi TDictionary?

5 голосов
/ 04 мая 2011

У меня есть TDictionary, объявленный примерно так TDictionary<String,Integer>, Теперь я хочу получить максимум значения, хранящегося в TDictionary.я могу сделать это, перебирая TDictionary и сравнивая значения, но мне интересно, существует ли лучший способ сделать это?exist any function or maybe the dictionary can be sorted by the values to retrieve the max value stored?

это то, что я делаю сейчас 

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;

Ответы [ 4 ]

3 голосов
/ 04 мая 2011

Я не использовал этот конкретный класс, но превосходный Delphi Collections 1.1.1 .имеет класс TDoubleSortedBidiDictionary , который имеет отсортированные значения.

Когда использовать: В этой реализации двунаправленного словаря используются два дерева AVL.Используйте его, если вам важно, чтобы ключи и значения были отсортированы.

btw, если вы «храните количество вхождений каждого слова», взгляните на TBag от DelphiКоллекции.Это Delphi реализация MultiSet .

3 голосов
/ 04 мая 2011

На TDictionary нет гарантий упорядочения, поэтому итерация - единственное решение.

Любое улучшение производительности по необходимости должно включать другую структуру данных.

2 голосов
/ 04 мая 2011

Вы когда-нибудь удаляли предметы или уменьшали их количество? Если нет, вы можете рассмотреть возможность создания нового потомка 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;
2 голосов
/ 04 мая 2011

Словарь - это правильная структура данных, если основной целью является быстрый поиск строки и обновление счетчика.Обычно для такого рода алгоритмов вы тратите больше времени на подсчет слов, чем на поиск максимального значения.При циклическом просмотре миллионов слов это может означать существенное повышение производительности по сравнению со списком tstring из-за более быстрого поиска.

Вы можете использовать MaxIntValue (MyDict.ToArray) из Math-модуля для более элегантного кода, но он все равно будет последовательным.Если вы обнаружите, что нахождение максимального значения является узким местом производительности, то вы можете рассмотреть альтернативные структуры данных.

...