Альтернативное тестирование на равенство хеш-таблиц для ключей - PullRequest
Новая
       32

Альтернативное тестирование на равенство хеш-таблиц для ключей

0 голосов
/ 17 февраля 2019

Профилирование SBCL показывает, что одна из моих хеш-таблиц Common Lisp отнимает значительное количество времени.Функция сравнивает две хеш-таблицы, чтобы определить, имеют ли они одинаковые ключи: 

(defun same-keys (ht1 ht2)
  "Returns t if two hash tables have the same keys."
  (declare (hash-table ht1 ht2))
  (when (= (hash-table-count ht1) (hash-table-count ht2))
    (maphash (lambda (ht1-key ht1-value)
               (declare (ignore ht1-value))
               (unless (gethash ht1-key ht2)
                 (return-from same-keys nil)))
             ht1)
    t))

Есть ли способ ускорить это, учитывая, что хеш-таблицы всегда #'eql с fixnum ключами?Я также загружаю библиотеку lparallel, но имеет ли смысл в этом случае каким-либо образом распараллеливать функцию?

Редактировать: Размер хеш-таблиц может варьироваться от 10 до 100 записей.Диапазон клавиш ht простирается от 100 до 999 999 999 999, но общее количество возможных фикснумов, фактически используемых в этом диапазоне, немного.Каждое значение ht - это либо t, либо список.Связи ключ-значение для всех хеш-таблиц устанавливаются во время загрузки.Новые хеш-таблицы создаются во время выполнения путем копирования существующих и добавления или удаления записей постепенно.Обычное чтение, запись и копирование хеш-таблицы, похоже, не являются проблемой.

1 Ответ

0 голосов
/ 18 февраля 2019

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

Если диапазон ключей не намного меньше размера, вы можетеБыстрее с векторами вместо хеш-таблиц.Если размер небольшой (менее 20-50), но большой диапазон (например, UUID), возможно, списки лучше подходят.

Если запись в эти хеш-таблицы не является узким местом, вы можете обернуть ваш хештаблицы с объектами, содержащими также некоторую вспомогательную структуру данных для сравнения ключей.Это может быть некоторый бит-вектор, отмечающий используемые ключи, или полный пользовательский хэш всех используемых ключей, или (если размер и диапазон действительно велики) что-то вроде фильтра Блума.

Распараллеливание может иметь смысл, если вашпроблема достаточно велика в некотором измерении, чтобы оправдать издержки: например, либо частота независимых сравнений очень высока, либо число ключей в хэш-таблице очень велико.

Один возможный низкий уровеньОптимизация заключается в использовании loop вместо maphash, который в большинстве случаев можно скомпилировать в гораздо более быстрый код: 

(loop :for key1 :being :the :hash-keys :of ht1
      :always (nth-value 1 (gethash key1 ht2)))
...