Common Lisp permite que cualquier objeto lisp sirva como clave de tabla hash. Pero, ¿qué sucede si solo desea usar parte de un objeto como clave? Por ejemplo, en

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

El intervalo de tiempo no es apropiado para situaciones de hash igual. ¿Cuál es una buena estrategia para acceder a una tabla hash utilizando un objeto lisp (parcial) como clave? Un enfoque podría usar una clave como (list (action-name act1) (action-parameters act1) (action-database act1)), pero esto parece bastante ineficiente. Otro enfoque podría crear una subestructura para la acción defstruct con solo las tres ranuras apropiadas y usar esa subestructura como clave, pero esto parece algo ad-hoc solo con el propósito de acceder a la tabla hash. ¿Existen otros métodos que podrían funcionar mejor?

1
davypough 5 dic. 2016 a las 01:13
1
Consulte: stackoverflow.com/q/33828408/124319. En cuanto a ser ineficiente, no se puede decir sin el tiempo adecuado. Parece que esta es una asignación muy pequeña que se recolecta de forma inmediata.
 – 
coredump
5 dic. 2016 a las 10:15
Creo que (database nil :type hash-table) debería ser (database (make-hash-table) :type hash-table) en su lugar. De lo contrario, se genera un error cuando se crea un action.
 – 
tsikov
5 dic. 2016 a las 18:33
@coredump: Tienes razón, una prueba rápida muestra una diferencia de tiempo insignificante usando la estructura como clave frente a una lista de ranuras. Además, el enfoque de pasantía en su referencia, aunque no es aplicable en mi aplicación, podría ser útil en ciertas circunstancias. Otra idea es establecer temporalmente las ranuras inapropiadas en valores nulos solo para el acceso a la tabla hash y mantener toda la estructura como clave.
 – 
davypough
5 dic. 2016 a las 21:17
@tsikov: Gracias por revisar. Para la creación de prototipos simple, he estado usando Allegro CL Express, que no se queja de muchas cosas similares.
 – 
davypough
5 dic. 2016 a las 21:18

1 respuesta

La mejor respuesta

Usaré la biblioteca Common Lisp de aquí, como por ejemplo

cl-tabla-hash-personalizada

Luego, vaya a su código, primero cuando cree una acción como esta:

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

Producir este error:

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

Por lo que necesita cambiar su definición a algo como esto:

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>)

Luego, debe definir una función por el mismo tiempo o lo que necesite de la siguiente manera: acceder a los datos

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

Crea otra acción

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>)

Crear la función para probar

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

Definir la función hash:

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

Crea tu hash

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*

Pruébalo:

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

Puede evitar el uso de una biblioteca si la distribución funcionará en implementaciones que admitan funciones personalizadas TEST / HASH de forma nativa; de lo contrario, puede usar with-custom-hash-table

En el caso de Optimus, puede trabajar de la siguiente manera:

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
0
anquegi 14 dic. 2016 a las 13:28
Gracias por sus conocimientos sobre tablas hash personalizadas. Pero todavía no tengo clara la ventaja de lo personalizado frente a lo estándar para mi problema original. Para esa clave efectiva de 3 ranuras, supongo que la función de prueba de tabla hash personalizada usaría (y (eq (nombre de acción a1) (nombre de acción a2)) (igual (parámetros de acción a1) (parámetros de acción a2) ) (equalp (action-database a1) (action-database a2))), mientras que la tabla hash de equalp estándar simplemente usaría (list (action-name a1) (action-parameters a1) (action-database a1)) como llave. ¿Es la tabla personalizada significativamente más eficiente que la tabla estándar en este caso?
 – 
davypough
15 dic. 2016 a las 07:04
Bueno, usar una tabla hash es más eficiente que una lista, eche un vistazo aquí cs.cmu.edu/Groups/AI/html/cltl/clm/node154.html
 – 
anquegi
15 dic. 2016 a las 11:57
Podría "convertir" manualmente las instancias de ACTION en una lista antes de usarlas como clave para la tabla hash. Una ventaja de usar una tabla hash personalizada es la legibilidad: no tiene que mencionar esta conversión para todas las llamadas a la tabla hash, sino solo una vez al definir la tabla hash. Una ventaja de rendimiento es que evita estas listas temporales.
 – 
zut
25 ene. 2017 a las 15:27