<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div><br class=""><blockquote type="cite" class="">On 3 Dec 2017, at 12:02, Antoniotti Marco <<a href="mailto:antoniotti.marco@disco.unimib.it" class="">antoniotti.marco@disco.unimib.it</a>> wrote:<br class=""><br class="">Hi<br class=""><br class="">I am fooling around with a problem that eventually will have to use a hash table on “triples” of “integers” and “structures". Triples I can portably pass to the EQUAL hash table. I cannot use an EQUALP hash table, because I would end up wasting to much time.<br class=""><br class="">Here is the rub: my triples <N, O1, O2> need to use the “object identity” of O1 and O2 (two structs). I could switch to an EQL hash table keyed on (HASH-TRIPLE-KEY N O1 O2). How would you proceed (or write HASH-TRIPLE), while staying as much portable as possible? As you well know SXHASH is practically useless.</blockquote><blockquote type="cite" class=""><div class=""><blockquote type="cite" style="font-family: Menlo-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class=""><br class="Apple-interchange-newline">On Dec 3, 2017, at 12:27 , Jason Cornez <<a href="mailto:jcornez@alum.mit.edu" class="">jcornez@alum.mit.edu</a>> wrote:<br class=""><br class="">Add an integer slot on the structs; hash on that? -Jason<span class="Apple-converted-space"> </span><br class=""></blockquote><br style="font-family: Menlo-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Menlo-Regular; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">I forgot to mention it. THAT is another thing I want to avoid because I need to share subgraphs (DAGs). I need to hash on the “object identity”.</span></div></blockquote><div><br class=""></div><div><br class=""></div><div>The thing is that there’s no conforming way to obtain the “object identity” other than the object itself, and no other conforming way to use it than to use EQ/EQL or other operators using EQL, such as EQL hash-tables.</div><div><br class=""></div><div>If you want to rely on implementation specific behavior, you can extract (a representation of) the object identity using <b class="">print-unreadable-object</b>.</div><div> <span style="font-family: -webkit-standard;" class="">If</span><span style="font-family: -webkit-standard;" class=""> </span><i style="font-family: -webkit-standard;" class="">identity</i><span style="font-family: -webkit-standard;" class=""> </span><span style="font-family: -webkit-standard;" class="">is</span><span style="font-family: -webkit-standard;" class=""> </span><a rel="DEFINITION" href="http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_t.htm#true" style="font-family: -webkit-standard;" class=""><i class="">true</i></a><span style="font-family: -webkit-standard;" class="">, the output from</span><span style="font-family: -webkit-standard;" class=""> </span><i style="font-family: -webkit-standard;" class="">forms</i><span style="font-family: -webkit-standard;" class=""> </span><span style="font-family: -webkit-standard;" class="">is followed by a space character and a representation of the</span><span style="font-family: -webkit-standard;" class=""> </span><i style="font-family: -webkit-standard;" class="">object</i><span style="font-family: -webkit-standard;" class="">'s identity, typically a storage address.</span><span style="font-family: -webkit-standard;" class=""> </span></div><div class="">cf. eg. <a href="https://gitlab.com/com-informatimago/com-informatimago/blob/master/common-lisp/cesarum/utility.lisp#L833" class="">https://gitlab.com/com-informatimago/com-informatimago/blob/master/common-lisp/cesarum/utility.lisp#L833</a></div><div class=""><br class=""></div><div>So a good conforming way to do it, is to add an integer slot to the structure, with a unique integer in it.</div><div>Another way to do it, is to use the structure as a key in a EQL hash-table mapping to the unique integer (with amortized O(1) time to get the object identity).</div><div>If you’re short on memory, you may store the structures in a vector, and use its index as object identity (but if you want to collect structures, it’ll leave holes, and it’s now O(n) to find the object identity).</div><div><br class=""></div><div>So the cheapest way is indeed to add an integer slot to the structures.</div><div><br class=""></div><div>Note that using <b class="">sxhash</b> doesn’t give the object identity. An implementation could very well return 42 for all the structures. So you could use it only to index buckets of structures, but you would still have to build the identifying integers in one of the above ways. </div></div><div class=""><br class=""></div>Obviously, the integer “object identity” slot of your structures would be unique amongst all your identifiable structures, and would not depend on the hash-table you would store them in.<div class=""><br class=""><div class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">-- <br class="">__Pascal J. Bourguignon__<br class=""><br class=""><br class=""></div></div>
</div>
<br class=""></div></body></html>