使用构造键进行高效的哈希表访问

Common Lisp允许任何lisp对象充当散列表键。但是如果你只想使用对象的一部分作为关键。例如，在使用构造键进行高效的哈希表访问

(defstruct action 
    (name nil :type symbol) 
    (parameters nil :type list) 
    (time 0 :type fixnum) 
    (database nil :type hash-table))

该时隙不适合equalp哈希情况。使用（部分）lisp对象作为关键字访问散列表的好方法是什么？一种方法可能使用像(list (action-name act1) (action-parameters act1) (action-database act1))这样的密钥，但这看起来相当低效。另一种方法可能会创建一个只有三个适当时隙的动作子结构，并将该子结构用作关键字，但这似乎只是为了散列表访问的目的而特设的。还有其他方法可以更好地工作吗？

来源

2016-12-04 davypough

参见：http://stackoverflow.com/q/33828408/124319。至于效率低下，你不能说没有适当的时间。看起来这是一个很小的分配，可以马上收集垃圾。 – coredump

我认为''（数据库无：类型散列表）'应该是'（数据库（make-hash-table）：类型散列表）'而不是。否则当创建一个'action'时会引发一个错误。 – tsikov

@coredump：你是对的，一个快速测试显示时间差异可以忽略不计，使用结构作为关键与插槽列表。另外，引用中的实习方式虽然不适用于我的应用程序，但在某些情况下可能会有用。另一个想法是暂时将不合适的插槽设置为空值，仅用于散列表访问，并将整个结构保留为关键字。 – davypough

我将使用的Common Lisp库从here，例如

cl-custom-hash-table

然后将你的代码，第一次当您创建一个这样的动作：

CL-USER> (setq action-1 (make-action 
    :parameters '(1 2 3) 
    :time 45))

产生此错误：

The value NIL is not of the expected type HASH-TABLE. 
    [Condition of type TYPE-ERROR]

所以你需要c焊割你的定义是这样的：

CL-USER> (defstruct action 
    (name nil :type symbol) 
    (parameters nil :type list) 
    (time 0 :type fixnum) 
    (database (make-hash-table) :type hash-table)) 
ACTION 
CL-USER> (setq action-1 (make-action 
    :parameters '(1 2 3) 
    :time 45)) 

#S(ACTION :NAME NIL :PARAMETERS (1 2 3) :TIME 45 :DATABASE #<HASH-TABLE :TEST EQL size 0/60 #x3020012E708D>)

那么你应该定义一个函数相等的时间，或者您需要如下什么都： accesing的数据

CL-USER> (action-time action-1) 
45

创建另一个动作

CL-USER> (setq action-2 (make-action 
    :parameters '(1 2 3) 
    :time 102)) 

#S(ACTION :NAME NIL :PARAMETERS (1 2 3) :TIME 102 :DATABASE #<HASH-TABLE :TEST EQL size 0/60 #x3020012FE58D>)

创建测试功能

CL-USER> (defun equal-actions-by-time (a1 a2) (= (action-time a1) (action-time a2))) 
EQUAL-ACTIONS-BY-TIME

定义哈希函数：

CL-USER> (defun hash-action (a) (action-time a)) 
HASH-ACTION

创建哈希

CL-USER> (define-custom-hash-table-constructor make-action-hash :test equal-actions-by-time :hash-function hash-action) 
MAKE-ACTION-HASH 
CL-USER> (defparameter *foo-hash* (make-action-hash) "variable for stackoverflow") 
*FOO-HASH*

尝试：

CL-USER> (setf (gethash action-1 *foo-hash*) 1 
      (gethash action-2 *foo-hash*) 10) 
10 

CL-USER> (gethash action-1 *foo-hash*) 
1 
T

你能避免使用库如果分布将在实施工作支持自定义的TEST/HASH功能，如果不支持的话，可以使用with-custom-hash-table

在Optimus的情况下，你可以根据以下工作：

CL-USER> (defparameter *foo-hash* (make-hash-table :test 'equal-actions-by-time :hash-function 'hash-action)) 
*FOO-HASH* 
CL-USER> (setf (gethash action-1 *foo-hash*) 1 
      (gethash action-2 *foo-hash*) 10) 
10 
CL-USER> (gethash action-1 *foo-hash*) 
1 
T

来源

2016-12-13 16:39:05 anquegi

感谢您的见解重新定制散列表。但我仍然不清楚自定义vs标准对于我原来的问题的优势。对于那个3插槽的有效密钥，我假定自定义散列表测试函数将使用（和（eq（动作名称a1）（动作名称a2））（等于（动作参数a1）（动作参数a2））（equalp（action-database a1）（action-database a2））），而标准equalp散列表将简单地使用（list（action-name a1）（action-parameters a1）（action-database a1））作为键。在这种情况下，自定义表格是否比标准表格更高效？ – davypough

好吧，使用哈希表比列表更有效率，看看这里https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node154.html – anquegi

@davypough你可以手动“转换“ACTION实例在使用它们作为哈希表的关键字之前列入列表。使用自定义哈希表的好处是可读性：您不必为所有哈希表调用提及此转换，但在定义哈希表时只需提一次。性能优势是你避免了这些临时列表。 – zut

使用构造键进行高效的哈希表访问

回答

相关问题