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

ProgramBox

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

Post author:admin
Запись опубликована:10 мая, 2023
Post category:Вопросы по программированию

#delphi #generics #dictionary #delphi-xe

#delphi #общие сведения #словарь #delphi-xe

Вопрос:

у меня есть 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;

1. В TDictionary нет max . Вы уверены, что используете правильную структуру данных? Итерация по нему или поиск min / max — это не то, как словарь предназначен для работы. Подумайте о реальном словаре — вы находите слово и хотите узнать, какое определение с ним связано. Вы не смотрите, какое самое высокое «слово»…

2. @Ken Я использую TDictionary для хранения количества совпадений для каждого слова. код представляет собой всего лишь упрощенный образец.

3. @Salvador: Тогда вы используете неправильный тип данных. Используйте TStringList, сохраняя строку как обычно и количество в массиве Objects. Затем вы можете выполнить пользовательскую сортировку и упорядочить их по количеству. Как я уже сказал, подумайте о реальном словаре и о том, как вы бы его использовали.

4. @Ken, может быть, нет. TDictionary — это очень хорошая структура данных для сбора информации (т.Е.: проверить, существует ли word в списке, увеличить количество вхождений). После сбора данных может потребоваться перейти на другой тип структуры данных, чтобы получить другие алгоритмические свойства. Или просто страдать от неэффективности обхода списка в случайном порядке, чтобы найти максимальное. Если поиск максимального значения является одноразовой задачей, это вообще не проблема.

5. @Ken White, это простая проблема свойств структуры данных: TDictionary предлагает O (1) вставить и обновить, где «1» на самом деле является константой «c». Другие структуры, такие как сбалансированное дерево, могут предлагать O(Log(n)) поиск, и для достаточно большого «c» и достаточно маленького «n» у нас будет Log(n) < c . Как всегда, "jack of all trades" структуры данных нет, нужно понимать свойства предлагаемых структур данных и выбирать ту, которая лучше подходит для рассматриваемой проблемы.

Ответ №1:

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

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

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

1. Что касается структур данных, дерево AVL не является словарем (т. Е. это не «хэш-карта»). В зависимости от количества слов в списке, лучшим подходом может быть использование простого TDictionary для сбора данных, а затем переход к другой структуре данных после сбора данных.

2. @Cosmin Это словарь; реализован с использованием деревьев AVL. Извините, если это было непонятно.

3. @Cosmin Если вы считаете, что у вас есть хорошее решение, почему бы не добавить его в качестве отдельного ответа?

4. @awmross, я не могу предложить лучшего решения, потому что я не до конца понимаю проблему. Если вся цель программы — отобразить слово с максимальным вхождением, то программа оптимальна как есть . Я хотел указать на различные статистические свойства альтернативных реализаций: словарь на основе хэш-карты, который TDictionary предлагает O(1) Delphi для вставки и обновления, очень хорош для начальной части алгоритма OP (сбор данных). Словарь на основе AVL предлагает O(Log(N)) обновления и немного больше для вставок, что не так хорошо для того же алгоритма […]

5. […] TDoubleSortedBidiDictionary будет намного хуже, поскольку я предполагаю, что он использует два дерева AVL, одно для значений, другое для ключей. Проблема в том, что при каждой итерации алгоритма сбора данных вы собираетесь выполнять поиск в Keys словаре, за которым следуют две вставки дерева AVL (если «ключ» не найден) или одно удаление и одна вставка (если «ключ» найден и значение необходимо обновить.

Ответ №2:

В TDictionary нет гарантий упорядочения, поэтому единственным решением является повторение.

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

Ответ №3:

Вы когда-нибудь удаляли элементы или уменьшали количество элементов? Если нет, вы могли бы рассмотреть возможность создания нового потомка TDictionary, где вы переопределяете метод Add () и отслеживаете самый большой элемент, добавленный на данный момент. Приведенный ниже код является псевдокодом и не совсем корректен. (Например, я думаю, что Add (), вероятно, должна переопределять функцию, но я закодировал ее как процедуру). Но это дает общую идею. Конечно, этот код отслеживает только один элемент: самый последний добавленный элемент, который является самым большим. Если вам нужно иметь список всех элементов с наибольшим количеством, вы могли бы сохранить список строк, а не FLARGESTWORDSFAR и FLARGESTCOUNTSFAR .

Даже если вы увеличивали количество элементов после их добавления, вы могли бы расширить приведенный ниже код, чтобы легко обрабатывать это аналогично тому, как это делает 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;

1. Сальвадор: Один комментарий к моему ответу выше. Убедитесь, что вам действительно нужно выполнить такого рода оптимизацию. Я всегда удивляюсь тому, как быстро я могу прочитать весь список. Проведите несколько тестов, чтобы подтвердить, что метод «чтения каждого элемента» методом перебора слишком медленный. Возможно, вы сочтете его удовлетворительным, что позволит вам избежать затрат времени и риска на реализацию приведенного выше кода. Помните Кнута: «Мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация — корень всего зла»

2. Определенно неправильный синтаксис. И наследование здесь является катастрофой. Есть много способов изменить контейнер, чем добавить.

Ответ №4:

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

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