From: Vladimir V. Zolotych
Subject: Which data structure ?
Date: 
Message-ID: <3AFAA369.CE8FBEC2@eurocom.od.ua>
Suppose I have a class

(defclass log ()
  ((time :initarg :log-time :accessor log-time :type integer)
   (user :initarg :log-user :accessor log-user :type string)

   ;; other slots...
))

Several objects of that class can have the identical
values in USER slot or in TIME slot, but their
combination is unique, e.g. no objects can have
identical pairs of USER,TIME. I'd like to have
collection of LOG objects (roughly hundreds of thousands
of them) and quickly determine does object with
particular USER,TIME values exists among them.

Is it possible to achieve that using hash tables ?

-- 
Vladimir Zolotych                         ······@eurocom.od.ua

From: Tim Bradshaw
Subject: Re: Which data structure ?
Date: 
Message-ID: <nkjlmo5uu9u.fsf@tfeb.org>
"Vladimir V. Zolotych" <······@eurocom.od.ua> writes:

> 
> Several objects of that class can have the identical
> values in USER slot or in TIME slot, but their
> combination is unique, e.g. no objects can have
> identical pairs of USER,TIME. I'd like to have
> collection of LOG objects (roughly hundreds of thousands
> of them) and quickly determine does object with
> particular USER,TIME values exists among them.
> 
> Is it possible to achieve that using hash tables ?
> 

Yes, make an EQUAL hashtable with keys that are a cons of the values
in the two slots.  This may not be the best approach - for instance if
there are not many USERs for instance, and they are comparable with
EQ, you mgiht want to have a table hashed on USER whose elements are
tables hashed on TIME.  You can only know by measuring, I think.

--tim
From: Jochen Schmidt
Subject: Re: Which data structure ?
Date: 
Message-ID: <9de917$hnlnr$1@ID-22205.news.dfncis.de>
Vladimir V. Zolotych wrote:

> Suppose I have a class
> 
> (defclass log ()
>   ((time :initarg :log-time :accessor log-time :type integer)
>    (user :initarg :log-user :accessor log-user :type string)
> 
>    ;; other slots...
> ))
> 
> Several objects of that class can have the identical
> values in USER slot or in TIME slot, but their
> combination is unique, e.g. no objects can have
> identical pairs of USER,TIME. I'd like to have
> collection of LOG objects (roughly hundreds of thousands
> of them) and quickly determine does object with
> particular USER,TIME values exists among them.
> 
> Is it possible to achieve that using hash tables ?

You could use CONS-Pairs containing the time in the CAR and the user
in the CDR as the Keys into your Hashtable.

Regards
Jochen
From: Vladimir V. Zolotych
Subject: Re: Which data structure ?
Date: 
Message-ID: <3AFBA5F0.D701AEEF@eurocom.od.ua>
Thanks for help.

Although I can use cons for two values or list 
if I have three or more of them (as I learn from
your letters) to organize key of the hash table 
I choose to use just USER as keys. Set of users 
is rather big, but each has only small number 
of distinguished values of TIME slots. So each
entry of a hash is just a list. It is gives 
acceptable efficiency.

-- 
Vladimir Zolotych                         ······@eurocom.od.ua