Линейное хэширование: быстрый метод нахождения «минимум» и «максимум»

я реализовал функции min() и max() для моей линейной хеш-таблицы, но у меня небольшие проблемы с производительностью, потому что я реализовал ее прямо. Я просто предполагаю, что первый найденный элемент — это min/mix, а затем я сравниваю с ним остальные элементы. Есть ли более быстрый способ найти минимум/максимум в хеш-таблице? Я ничего не нашел в своих книгах. Мой второй подход состоял в том, чтобы записать каждое значение в массив, а затем просмотреть его, но я не думаю, что это быстрее.


max min c++11
person Aragok    schedule 25.05.2015    source источник
comment
В качестве альтернативы отслеживайте минимальное и максимальное количество элементов по мере их вставки в таблицу.   -  person AndyG    schedule 25.05.2015
comment
@AndyG: Это сделало бы удаление довольно дорогим.   -  person Bill Lynch    schedule 25.05.2015
comment
@BillLynch: O(n) на удаление по сравнению с O(n) на поиск. В любом случае есть компромиссы, все зависит от вариантов использования.   -  person AndyG    schedule 25.05.2015

Ответы (2)


arrow_upward
1
arrow_downward

Общая хеш-таблица не является отсортированным списком элементов. Таким образом, это будет операция O(n) для поиска min() и max() данной таблицы.

person Bill Lynch    schedule 25.05.2015
comment
Хорошо, поэтому нет более быстрого способа. - person Aragok; 25.05.2015

arrow_upward
0
arrow_downward

По соглашению с Биллом Линчем, нам придется потратить O(n) времени хотя бы один раз, однако мы можем быть настолько ленивыми, насколько это возможно:

  • Храните min и max рядом со столом
  • Пока пользователь выполняет обновления, обновляйте min и max по мере необходимости.
  • После удаления проверьте, является ли удаленный элемент min или max, если да, установите флаг на true, указывающий, что минимальное или максимальное значение изменилось. Если флаг уже установлен, нет необходимости сверяться с текущим минимумом/максимумом.
  • После поиска min/max проверьте свой флаг. Если он не был установлен, вы можете использовать кешированное значение min или max. Если он был установлен, потратьте O(n) времени на его повторную настройку.

Теперь мы будем тратить только O(n) времени, когда нам нужно, а не O(n) времени каждый раз, когда кто-то запрашивает минимум или максимум. Если вставок намного больше, чем удалений, обычно вы увидите O(1) времени поиска.

person AndyG    schedule 25.05.2015
comment
Звучит интересно, попробую. - person Aragok; 25.05.2015