Учитывая список постоянных значений, какой поиск наиболее эффективен?
У вас есть список пар ключ-значение, известных во время компиляции. Мы не хотим выполнять поиск во время выполнения, а предпочитаем создать таблицу поиска. Например, мы могли бы сделать это (из фрагмента кода, который я написал вчера):
(defun mod-mask (char)
(case char
(#\A #.(ash 1 22))
(#\s #.(ash 1 23))
(#\H #.(ash 1 24))
(#\S #.(ash 1 25))
(#\C#.(ash 1 26))
(#\M #.(ash 1 27))))
(defun mask-mod (mask)
(case mask
(#.(ash 1 22) #\A)
(#.(ash 1 23) #\s)
(#.(ash 1 24) #\H)
(#.(ash 1 25) #\S)
(#.(ash 1 26) #\C)
(#.(ash 1 27) #\M)))
Но вы предпочитаете не повторяться, а этот аккуратный, простой код, который все понимают, что он делает, просто очень скучен!
Если отбросить шутки, приведенный выше пример короткий, но вариантов может быть много, очень большое. Мы не хотим печатать много, потому что это чревато ошибками и утомительно. Кроме того, у списка есть преимущество поиска в другом месте: например, мы можем увидеть, какие элементы определены, но мы не можем получить их из скомпилированной формы случая. Список также может быть сгенерирован во время выполнения, а также в виде кода, в отличие от операторов Case, вводимых вручную.
Вместо вышеперечисленного составляем список:
(defvar *modifier-masks*
`((#\A . ,(ash 1 22))
(#\s . ,(ash 1 23))
(#\H . ,(ash 1 24))
(#\S . ,(ash 1 25))
(#\C . ,(ash 1 26))
(#\M . ,(ash 1 27))))
И создайте макрос для генерации двух вышеуказанных случаев:
(defmacro mod-lookup-gen (&optional bit)
`(lambda (mask)
(case mask
,@(mapcar (lambda (e)
(if bit
`(,(car e) ,(cdr e))
`(,(cdr e) ,(car e))))
*modifier-masks*))))
Что мы можем использовать в простых обертках:
(defun mask-mod (mask)
(let ((get-char (mod-lookup-gen)))
(funcall get-char mask)))
(defun mod-mask (modifier)
(let ((get-char (mod-lookup-gen 'bit)))
(funcall get-char modifier)))
Вопрос: какой вариант и какой код, генерируемый во время компиляции, будет лучшим и более эффективным, эквивалентным двум приведенным выше определениям? Есть ли способ избавиться от лямбда-выражение, обертывающее оператор case, чтобы пропустить дополнительный вызов функции? Кроме, возможно, встраивания?
В общем, каков наиболее эффективный способ поиска пар ключ-значение в Common Lisp? Являются ли выражения «переключения» самым быстрым способом поиска значений, поскольку компилятор может разместить статический код для поиска во время компиляции? Я думаю, это зависит от реализации, но, возможно, можно дать какие-то общие рекомендации?
Также обратите внимание, что разница между хэш-картой и списком заключается в том, что список и, следовательно, сгенерированный из него оператор переключения заботятся о порядке операторов, т. е. они сопоставляются в порядке объявлений, тогда как хэш-карта представляет собой неупорядоченный поиск. Это может быть важно или не важно, в зависимости от варианта использования.
Кстати, это идиома «перечисления». Я видел несколько CL-библиотек для генерации перечислений, но я их не использовал, поэтому не знаю, какой код они генерируют. Возможно, кто-то может порекомендовать тот, который генерирует хороший поиск во время компиляции?
Ответы 1
Ответ на этот вопрос: напишите код и измерьте его. (Возможно) ясно, что в предельном случае очень большого количества ключей что-то, основанное на хеш-таблице, будет быстрее, чем что-то, основанное на case. Но где находится эта точка останова, зависит от мелких деталей реализации. И, конечно же, достаточно агрессивный компилятор всегда может превратить case в хеш-таблицу, если захочет.
Для вашего примера я написал код ниже и обнаружил, что в одной реализации реализация case была в несколько раз быстрее, чем реализация хеш-таблицы, а реализация списка находилась где-то посередине. В другой реализации реализация case была самой быстрой, хеш-таблица — медленнее, а список — самой медленной.
Если вы хотите знать что-то о производительности, вам необходимо проводить измерения.
(eval-when (:compile-toplevel :load-toplevel :execute)
(defvar *modifier-masks*
`((#\A . ,(ash 1 22))
(#\s . ,(ash 1 23))
(#\H . ,(ash 1 24))
(#\S . ,(ash 1 25))
(#\C . ,(ash 1 26))
(#\M . ,(ash 1 27)))))
(declaim (inline modifier-case-map mask-case-map))
(defun modifier-case-map (c)
(declare (type character c))
(macrolet ((cmap (v)
`(ecase ,v
,@(mapcar (lambda (m)
`(,(car m) ,(cdr m)))
*modifier-masks*))))
(cmap c)))
(defun mask-case-map (m)
(declare (type fixnum m))
(macrolet ((mmap (v)
`(ecase ,v
,@(mapcar (lambda (m)
`(,(cdr m) ,(car m)))
*modifier-masks*))))
(mmap m)))
(declaim (inline modifier-hash-map mask-hash-map))
(defun modifier-hash-map (c)
(declare (type character c))
(or (gethash c (load-time-value (let ((h (make-hash-table
:size (length *modifier-masks*))))
(dolist (m *modifier-masks* h)
(setf (gethash (car m) h) (cdr m))))))
(error "not present")))
(defun mask-hash-map (m)
(declare (type fixnum m)) ;?
(or (gethash m (load-time-value (let ((h (make-hash-table
:size (length *modifier-masks*))))
(dolist (m *modifier-masks* h)
(setf (gethash (cdr m) h) (car m))))))
(error "not present")))
(declaim (inline modifier-alist-map mask-alist-map))
(defun modifier-alist-map (c)
(declare (type character c))
(or (cdr (assoc c (load-time-value *modifier-masks* t)))
(error "not present")))
(defun mask-alist-map (m)
(declare (type fixnum m)) ;?
(or (gethash m (load-time-value *modifier-masks* t))
(error "not present")))
;;; All the setfery is to try to make sure things do not get optimized
;;; away
(defun tsc (n)
(let ((r nil))
(dotimes (i n r)
(dolist (c (load-time-value (mapcar #'car *modifier-masks*)))
(setf r (modifier-case-map c))))))
(defun tsh (n)
(let ((r nil))
(dotimes (i n r)
(dolist (c (load-time-value (mapcar #'car *modifier-masks*)))
(setf r (modifier-hash-map c))))))
(defun tsa (n)
(let ((r nil))
(dotimes (i n r)
(dolist (c (load-time-value (mapcar #'car *modifier-masks*)))
(setf r (modifier-alist-map c))))))
В любом случае, у меня не было конкретного примера для сравнения, и мне было немного лень строить синтетический пример. Этот вопрос скорее любопытство и побочная мысль, пока я занимался чем-то другим. Я вижу, что вы использовали макролет вместо генерации лямбды, что отвечает на мой вопрос об отказе от использования лямбды. Однако, когда я сравниваю дизассемблирование как для моей версии на основе лямбда, так и для вашей версии макролета в SBCL, сгенерированная сборка почти идентична, с небольшой разницей, поскольку вы использовали ecase вместо регистра. Спасибо, что посмотрели на это и за хороший ответ, это было очень информативно.
Просто добавлю, что SBCL уже несколько лет может конвертировать некоторые вызовы (TYPE)CASE/FIND в таблицы переходов.
Еще раз спасибо за очень подробный и информативный ответ. Я надеялся, что вы его увидите и у вас будет время и интерес ответить на него. Я согласен, всегда нужно измерять, я сам так говорю, однако это была скорее мысль, которая пришла мне в голову после написания вышеприведенных масок и осознания, что я все равно предпочел бы список, чтобы я мог спросить систему, какие маски мне нужны. (вместо того, чтобы читать документ), потому что я знаю, что рано или поздно забуду их. Я удивлен, узнав, что в некоторых реализациях поиск по хеш-карте выполняется быстрее, чем в списке для таких небольших входных данных. Возможно, они оптимизированы для малых и больших входов.